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

1、四年级秋季班第五讲-简单抽屉原理、最不利原则精品文档第五讲简单抽屉原理、最不利原则知识框架认识一一抽屉原理解决的是存在杵问题操作一一构造抽屉的方法Z从问题出发，相同的即为抽屉: 从数量关系出发；少的就是抽屉演练一一抽屉原理的逆向应用最不利原则最糟的情形就能保i止完成11标一、对抽屉原理两个版本的认识抽屉原理1:将n+1个物品任意放到n个抽屉中，那么至少有一个抽屉中的物品不少于2件。n），（1）当m是n的整数倍时，那么至少有一个抽屉中的物品件数 是不少于m n件；（2）当m不是n的整数倍时，那么至少有一个抽屉中的物品件 数是不少于m n+1件。注：若mn =ab,那么就说mn=a ,也就是只要商

2、，余数不 要了。称这个过程为取整。原理要点：（1）物品数比抽屉数多，抽屉原理1的情形包含于这个原理中；（2）解决的是抽屉的存在性；（3） 在解题时，遇到“有一个抽屉中的物品数不少于A件”，其 中A2时，应使用抽屉原理2。（4） 原理的结论也可以理解为：“总有不少于m n件（或m n +1件）物品在同一个抽屉中。”相同的即为“抽屉”。 原理讲解：最不利的情形就是“平均分”，这样每个抽屉中的物品数都不太 多都是m n个。若mn有余数，那么多出来的余数个物品也按照 最不利的情形来分配，这样就能保证抽屉中的物品尽量地少。也就是说这余数个物品也平均地往抽屉中放，这样有的抽屉会再放入一 个物品，而有的就分

3、不到，那么至少会有一个抽屉中的物品数不少 于m n+1个。这也解释了物品数是不少于m n+1 ,而不是“不少 于m n+余数”。二、如何构造抽屉1. 袋中取球问题练习1在一个口袋中有红色、黄色、蓝色球若干个，小聪明和其它 六个小朋友一起做游戏，每人可以从口袋中任意取出 2个球，那么 不管怎么挑选，总有两个小朋友取出的两个球的颜色完全一样。 分析：（方法1）从问题出发。“总有两个小朋友取出的两个球的颜色完全一 样”，相同的是“取出的两个球的颜色搭配”，这就是“抽屉”。取出的两个球的颜 色，可能的情况有如下六种：红红、黄黄、蓝蓝，红蓝、红黄、蓝黄。也就是 说有6个抽屉。小聪明和其它6个小朋友一起做

4、游戏，共7人，也就是有7个 物品。物品数比抽屉数多1,根据抽屉原理1,总有2个小朋友取出的两个球的 颜色完全一样。（方法2）从条件出发。每人从口袋中任意取出2个球，取出的颜色搭配可能 有6种情形，取球的共有7个小朋友。小朋友数比颜色搭配数多1,那么7小 朋友是“物品”，6种颜色搭配是“抽屉”。根据抽屉原理1,总有两个小朋友取出 的两个球的颜色搭配相同。拓展口袋中放有足够多的红、白、蓝三种颜色的球，现有31人轮流从袋子中取球，每人各取3个。证明：至少有4人取出球的颜色一样。分析：类似练习1,取出球的颜色搭配是抽屉。搭配可能有：红红白、红红蓝、蓝蓝红、蓝蓝白、白白红、白白蓝、红白蓝，红红红、白白白

5、、蓝蓝蓝，共10种。也就是说有10个抽屉。31个人看成是物品。31 10 3 1 ,那么31 1013 14。根据抽屉原理2,至少有4人取出球的颜色是一样的。总结：构造抽屉的两种方法：（1）从问题出发，相同的就是“抽屉”；（2）从数量关系出发，多的是“物品”，少的是“抽屉”。2. 数的整除性与抽屉原理余数的性质:（1）余数相同，差无余数。也就是说，两个数除以同一个数得到的余数相同，那么这两个数的差再去除以这同一个数时没有余数。例：12 5和32 5的余数都是2,那么（32 12）5没有余数。（2）余数的和等于和的余数。也就是说，几个数除以同一个数得到的余数相加所得的和再除以同一个数得到的余数，

6、等于原本几个数的和除以同一个数所得的余数。例：12 5的余数是2，14 5的余数是4，2 4 6，6 5的余数是1 ；（12 14） 5的余数也是1。练习2在任意的4个自然数中，是否其中必有两个数，它们的差能被3整除?分析：一个自然数除以3,其余数只能是0,1,2三种情形。将余数的这三种情形 看做3个抽屉，一个自然数除以3的余数是几，就将自然数放入那个“抽屉” 中。那么任意的4个自然数放入这3个抽屉中，根据抽屉原理，至少有一个抽 屉中有不少于2个自然数。那么这个抽屉中的两个自然数的差就能被 3整除。拓展在任意的5个自然数中，是否必有其中三个数的和是 3的倍数？分析：构造抽屉的方法如练习2。那么

7、可能出现两种情形：（1）每个抽屉中都 至少有一个数。这样，每个抽屉中取出一个数，这三个数的余数分别是0,1,2.，那么余数的和为0 123 ,除以3没有余数，那么取出的这三个数的和除以3也没有余数。（2）有一个抽屉中有不少于3个数。从这样的抽屉中取出3个 数，这三个数的余数相同，那么余数的和是 3余数，除以3没有余数，那么取 出的这三个数的和除以3也没有余数。总结：题目中出现“几个数得和（或差）是某数的倍数”时，就是数的整除性结合了抽屉原理，余数做抽屉。三、抽屉原理的应用1、 求抽屉中物品至多数练习3 17名同学参加一次考试，考试题是三道判断题（答案只有对错之分），每名同学都在答题纸上依次写下

8、三道题的答案。请问至少有几名同学的答案是 一样的？分析：从问题出发找抽屉，相同的是答案，这就是抽屉。求抽屉数时可用乘法原理：每一道题都有2种答案，所以三道题的答案有2 2 2 8种，即有8个抽屉。物品为17名同学。17 821 ,由抽屉原理2,至少有2 1 3名同学的答案是一样的。练习4 （09年希望杯）人的头发平均有12万根。假设最多不超过20万根。13 亿人中至少有多少人的头发根数相同？分析：从问题出发，抽屉就是头发根数。头发根数最多不超20万，那么抽屉数为20万。物品为13亿人。1300000000 200000 6500 ,由抽屉原理2,至少 有6500人的头发根数相同。2、抽屉原理的

9、逆应用练习5（2003年希望杯）新年晚会上，老师让每个同学从一个装有许多玻璃球 的口袋中摸两个球，这些球给人的手感相同。只有红、黄、白、蓝、绿五色之 分（摸时看不到颜色），结果发现总有两个人取的球相同，由此可知，参加取 球的至少有多少人？分析：取两个球，颜色搭配有15种可能。15个抽屉，本题中物品即为取球的人。物品数至少为15 1 16个。拓展有三种图书：科技书、文艺书、故事书，每位同学可任借两本，问至少多少位同学借书，才能保证其中必有 4人借的书类型相同？分析：抽屉就是借的两本书的组合，共有 6种。为保证必有4人借的书类型相 同，物品数（也就是本题中的人数）至少为 3 6 1 19人。总结：

10、结论为“总有a个物品在一个抽屉里”时（a不少于2），物品数至少=（a-1）抽屉数+1。J这是因为将m个物品放入n个抽屉中时，当总有a个物品在一个抽屉中时，最一丿不利情形就是平均分，抽屉中的物品数最多为a,其它抽屉中均有（a-1 ）个物品。此时就是满足结论的物品数最少的情形：物品数=（a-1）抽屉数+1。练习6幼儿园小朋友分200块饼干，无论怎么分都有人至少分到 8块饼干，这 群小朋友至多有多少名？分析：200为物品数，小朋友为抽屉。结论为“无论怎么分都有人至少分到 8块 饼干”。根据抽屉原理2,把小朋友的人数设为n,那么200（8 1） n k，k 1。要求n的最大值。当k最小时，n最大。取k

11、 1，n 199 7 ,整数部分 为28,所以这群小朋友至多有28名。（ 总结：当结论为“总有a个物品在同一个抽屉中”时（a不少于2）,抽屉数至多=（物品总数-1）（a-1）的整数部分。四、最不利原则练习7 口袋中有三种颜色的筷子各10根，问：（1）至少取多少根才能保证三种颜色都能取到？（2）至少取多少根才能保证有2双颜色不同的筷子？（3）至少取多少根才能保证有2双颜色相同的筷子？分析：（1最糟糕的情形就是两种颜色的都取完了，还没有取到第三种颜色 的。这时只要再取一根就能凑足三种颜色，所以至少取 10 10 1 21根。（2）最糟糕的情形就是其中一种颜色的筷子取出来一甩，其它两种颜色筷子各取了 1根，这时只要再取一根就能凑出两双颜色不同的，所