四年级秋季班第五讲-简单抽屉原理、最不利原则

四年级秋季班第五讲抽屉原理李拉娜[e-mail]第五讲简单抽屉原理、最不利原则知识框架一、对抽屉原理两个版本的认识原理要点：（1）物品数比抽屉数多1。只有物品数比抽屉数多时抽屉原理才会成立。（2）物品是“任意放”到抽屉中。（3）其中“物品不少于2件”的抽屉是一定存在的，但是不确定是哪一个。（4）原理的结论是：“至少有一个抽屉中的物品数不少于2件”，也可以这么说，“至少有2件物品在同一个抽屉中”。原理讲解：只要有一个抽屉中的物品数不少于2件，抽屉原理1就是成立的。当我们认识——抽屉原理解决的是存在性问题操作——构造抽屉的方法：从问题出发，相同的即为抽屉；从数量关系出发：少的就是抽屉。1.袋中取球；2.数的整除性演练——抽屉原理的逆向应用代数思想最不利原则最糟的情形+1就能保证完成目标抽屉原理1：将n+1个物品任意放到n个抽屉中，那么至少有一个抽屉中的物品不少于2件。四年级秋季班第五讲抽屉原理李拉娜[e-mail]可以往抽屉中任意放物品时，最不利的情形就是“平均分”，这样所有抽屉中的物品数都不会太多。n+1个物品平均地放入n个抽屉，每个抽屉放一个，由于物品数比抽屉数多，就会余出一个物品。最后，余出的这个物品放入某个抽屉，这个抽屉中就有了2个物品。此外，其它情形，只要有一个抽屉是空的，那么就一定会有另外的抽屉中有2个或2个以上的物品。例子：4只鸽子飞回三个鸟笼，有几种方法？1号鸟笼2号鸟笼3号鸟笼方法一400方法二310方法三220方法四211每种方法中，都会有一个鸟笼中的鸽子数不少于2。在有些地方抽屉原理又叫做“鸽笼原理”。原理要点：（1）物品数比抽屉数多，抽屉原理1的情形包含于这个原理中；（2）解决的是抽屉的存在性；抽屉原理2（加强版的抽屉原理）将m件物品任意放入n个抽屉（mn），（1）当m是n的整数倍时，那么至少有一个抽屉中的物品件数是不少于m÷n件；（2）当m不是n的整数倍时，那么至少有一个抽屉中的物品件数是不少于[m÷n]+1件。注：若m÷n=a„b，那么就说[m÷n]=a，也就是只要商，余数不要了。称这个过程为取整。四年级秋季班第五讲抽屉原理李拉娜[e-mail]（3）在解题时，遇到“有一个抽屉中的物品数不少于A件”，其中A2时，应使用抽屉原理2。（4）原理的结论也可以理解为：“总有不少于m÷n件（或[m÷n]+1件）物品在同一个抽屉中。”相同的即为“抽屉”。原理讲解：最不利的情形就是“平均分”，这样每个抽屉中的物品数都不太多都是[m÷n]个。若m÷n有余数，那么多出来的余数个物品也按照最不利的情形来分配，这样就能保证抽屉中的物品尽量地少。也就是说这余数个物品也平均地往抽屉中放，这样有的抽屉会再放入一个物品，而有的就分不到，那么至少会有一个抽屉中的物品数不少于[m÷n]+1个。这也解释了物品数是不少于[m÷n]+1，而不是“不少于[m÷n]+余数”。二、如何构造抽屉1．袋中取球问题练习1在一个口袋中有红色、黄色、蓝色球若干个，小聪明和其它六个小朋友一起做游戏，每人可以从口袋中任意取出2个球，那么不管怎么挑选，总有两个小朋友取出的两个球的颜色完全一样。分析：（方法1）从问题出发。“总有两个小朋友取出的两个球的颜色完全一样”，相同的是“取出的两个球的颜色搭配”，这就是“抽屉”。取出的两个球的颜色，可能的情况有如下六种：红红、黄黄、蓝蓝，红蓝、红黄、蓝黄。也就是说有6个抽屉。小聪明和其它6个小朋友一起做游戏，共7人，也就是有7个物品。物品数比抽屉数多1，根据抽屉原理1，总有2个小朋友取出的两个球的颜色完全四年级秋季班第五讲抽屉原理李拉娜[e-mail]一样。（方法2）从条件出发。每人从口袋中任意取出2个球，取出的颜色搭配可能有6种情形，取球的共有7个小朋友。小朋友数比颜色搭配数多1，那么7小朋友是“物品”，6种颜色搭配是“抽屉”。根据抽屉原理1，总有两个小朋友取出的两个球的颜色搭配相同。拓展口袋中放有足够多的红、白、蓝三种颜色的球，现有31人轮流从袋子中取球，每人各取3个。证明：至少有4人取出球的颜色一样。分析：类似练习1，取出球的颜色搭配是抽屉。搭配可能有：红红白、红红蓝、蓝蓝红、蓝蓝白、白白红、白白蓝、红白蓝，红红红、白白白、蓝蓝蓝，共10种。也就是说有10个抽屉。31个人看成是物品。131031，那么4131]1031[。根据抽屉原理2，至少有4人取出球的颜色是一样的。2．数的整除性与抽屉原理余数的性质：（1）余数相同，差无余数。也就是说，两个数除以同一个数得到的余数相同，那么这两个数的差再去除以这同一个数时没有余数。例：512和532的余数都是2，那么5)1232(没有余数。（2）余数的和等于和的余数。也就是说，几个数除以同一个数得到的余数相加所得的和再除以同一个数得到的余数，等于原本几个数的和除以同一个数所得的余数。例：512的余数是2，514的余数是4，642，56的余数是1；5)1412(的余数也是1。练习2在任意的4个自然数中，是否其中必有两个数，它们的差能被3整除？分析：一个自然数除以3，其余数只能是0,1,2三种情形。将余数的这三种情形总结：构造抽屉的两种方法：（1）从问题出发，相同的就是“抽屉”；（2）从数量关系出发，多的是“物品”，少的是“抽屉”。四年级秋季班第五讲抽屉原理李拉娜[e-mail]看做3个抽屉，一个自然数除以3的余数是几，就将自然数放入那个“抽屉”中。那么任意的4个自然数放入这3个抽屉中，根据抽屉原理，至少有一个抽屉中有不少于2个自然数。那么这个抽屉中的两个自然数的差就能被3整除。拓展在任意的5个自然数中，是否必有其中三个数的和是3的倍数？分析：构造抽屉的方法如练习2。那么可能出现两种情形：（1）每个抽屉中都至少有一个数。这样，每个抽屉中取出一个数，这三个数的余数分别是0,1,2.，那么余数的和为3210，除以3没有余数，那么取出的这三个数的和除以3也没有余数。（2）有一个抽屉中有不少于3个数。从这样的抽屉中取出3个数，这三个数的余数相同，那么余数的和是3×余数，除以3没有余数，那么取出的这三个数的和除以3也没有余数。三、抽屉原理的应用1、求抽屉中物品至多数练习317名同学参加一次考试，考试题是三道判断题（答案只有对错之分），每名同学都在答题纸上依次写下三道题的答案。请问至少有几名同学的答案是一样的？分析：从问题出发找抽屉，相同的是答案，这就是抽屉。求抽屉数时可用乘法原理：每一道题都有2种答案，所以三道题的答案有8222种，即有8个抽屉。物品为17名同学。12817，由抽屉原理2，至少有312名同学的答案是一样的。练习4（09年希望杯）人的头发平均有12万根。假设最多不超过20万根。13亿人中至少有多少人的头发根数相同？分析：从问题出发，抽屉就是头发根数。头发根数最多不超20万，那么抽屉数为20万。物品为13亿人。65002000001300000000，由抽屉原理2，至少有6500人的头发根数相同。总结：题目中出现“几个数得和（或差）是某数的倍数”时，就是数的整除性结合了抽屉原理，余数做抽屉。四年级秋季班第五讲抽屉原理李拉娜[e-mail]2、抽屉原理的逆应用练习5（2003年希望杯）新年晚会上，老师让每个同学从一个装有许多玻璃球的口袋中摸两个球，这些球给人的手感相同。只有红、黄、白、蓝、绿五色之分（摸时看不到颜色），结果发现总有两个人取的球相同，由此可知，参加取球的至少有多少人？分析：取两个球，颜色搭配有15种可能。15个抽屉，本题中物品即为取球的人。物品数至少为16115个。拓展有三种图书：科技书、文艺书、故事书，每位同学可任借两本，问至少多少位同学借书，才能保证其中必有4人借的书类型相同？分析：抽屉就是借的两本书的组合，共有6种。为保证必有4人借的书类型相同，物品数（也就是本题中的人数）至少为19163人。这是因为将m个物品放入n个抽屉中时，当总有a个物品在一个抽屉中时，最不利情形就是平均分，抽屉中的物品数最多为a，其它抽屉中均有（a-1）个物品。此时就是满足结论的物品数最少的情形：物品数=（a-1）×抽屉数+1。练习6幼儿园小朋友分200块饼干，无论怎么分都有人至少分到8块饼干，这群小朋友至多有多少名？分析：200为物品数，小朋友为抽屉。结论为“无论怎么分都有人至少分到8块饼干”。根据抽屉原理2，把小朋友的人数设为n，那么kn)18(200，1k。要求n的最大值。当k最小时，n最大。取1k，7199n，整数部分为28，所以这群小朋友至多有28名。总结：结论为“总有a个物品在一个抽屉里”时（a不少于2），物品数至少=（a-1）×抽屉数+1。总结：当结论为“总有a个物品在同一个抽屉中”时（a不少于2），抽屉数至多=（物品总数-1）÷（a-1）的整数部分。四年级秋季班第五讲抽屉原理李拉娜[e-mail]四、最不利原则练习7口袋中有三种颜色的筷子各10根，问：（1）至少取多少根才能保证三种颜色都能取到？（2）至少取多少根才能保证有2双颜色不同的筷子？（3）至少取多少根才能保证有2双颜色相同的筷子？分析：（1）最糟糕的情形就是两种颜色的都取完了，还没有取到第三种颜色的。这时只要再取一根就能凑足三种颜色，所以至少取2111010根。（2）最糟糕的情形就是其中一种颜色的筷子取出来一甩，其它两种颜色筷子各取了1根，这时只要再取一根就能凑出两双颜色不同的，所以至少取131210根。（3）要取出2双颜色相同的，也就是取出4根颜色相同的。最糟糕的情形就是三种颜色每种都取了三根，这时只要再取一根就能凑出四根颜色相同的。所以至少要取10133根。总结：要保证完成目标，我们要把最糟糕的情形考虑进去，在糟糕情形的基础上再加1就可实现目标。这就是最不利原则！