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

《四年级秋季班第五讲 简单抽屉原理、最不利原则》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、四年级秋季班第五讲抽屉原理李拉娜lilana927@hotmail.com第五讲简单抽屉原理、最不利原则知识框架认识——抽屉原理解决的是存在性问题操作——构造抽屉的方法：从问题出发，相同的即为抽屉；从数量关系出发：少的就是抽屉。1.袋中取球；2.数的整除性演练——抽屉原理的逆向应用代数思想最不利原则最糟的情形+1就能保证完成目标一、对抽屉原理两个版本的认识抽屉原理1：将n+1个物品任意放到n个抽屉中，那么至少有一个抽屉中的物品不少于2件。原理要点：（1）物品数比抽屉数多1。只有物品数比抽屉数多时抽屉原理才会成立。（2）物品是“任意放”到抽屉中。（3）其中

2、“物品不少于2件”的抽屉是一定存在的，但是不确定是哪一个。（4）原理的结论是：“至少有一个抽屉中的物品数不少于2件”，也可以这么说，“至少有2件物品在同一个抽屉中”。原理讲解：只要有一个抽屉中的物品数不少于2件，抽屉原理1就是成立的。当我们四年级秋季班第五讲抽屉原理李拉娜lilana927@hotmail.com可以往抽屉中任意放物品时，最不利的情形就是“平均分”，这样所有抽屉中的物品数都不会太多。n+1个物品平均地放入n个抽屉，每个抽屉放一个，由于物品数比抽屉数多，就会余出一个物品。最后，余出的这个物品放入某个抽屉，这个抽屉中就有了2个物品。此外，其它

3、情形，只要有一个抽屉是空的，那么就一定会有另外的抽屉中有2个或2个以上的物品。例子：4只鸽子飞回三个鸟笼，有几种方法？1号鸟笼2号鸟笼3号鸟笼方法一400方法二310方法三220方法四211每种方法中，都会有一个鸟笼中的鸽子数不少于2。在有些地方抽屉原理又叫做“鸽笼原理”。抽屉原理2（加强版的抽屉原理）将m件物品任意放入n个抽屉（m>n），（1）当m是n的整数倍时，那么至少有一个抽屉中的物品件数是不少于m÷n件；（2）当m不是n的整数倍时，那么至少有一个抽屉中的物品件数是不少于[m÷n]+1件。注：若m÷n=a„b，那么就说[m÷n]=a，也就是只要商，

4、余数不要了。称这个过程为取整。原理要点：（1）物品数比抽屉数多，抽屉原理1的情形包含于这个原理中；（2）解决的是抽屉的存在性；四年级秋季班第五讲抽屉原理李拉娜lilana927@hotmail.com（3）在解题时，遇到“有一个抽屉中的物品数不少于A件”，其中A>2时，应使用抽屉原理2。（4）原理的结论也可以理解为：“总有不少于m÷n件（或[m÷n]+1件）物品在同一个抽屉中。”相同的即为“抽屉”。原理讲解：最不利的情形就是“平均分”，这样每个抽屉中的物品数都不太多都是[m÷n]个。若m÷n有余数，那么多出来的余数个物品也按照最不利的情形来分配，这样就能

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

6、“抽屉”。取出的两个球的颜色，可能的情况有如下六种：红红、黄黄、蓝蓝，红蓝、红黄、蓝黄。也就是说有6个抽屉。小聪明和其它6个小朋友一起做游戏，共7人，也就是有7个物品。物品数比抽屉数多1，根据抽屉原理1，总有2个小朋友取出的两个球的颜色完全四年级秋季班第五讲抽屉原理李拉娜lilana927@hotmail.com一样。（方法2）从条件出发。每人从口袋中任意取出2个球，取出的颜色搭配可能有6种情形，取球的共有7个小朋友。小朋友数比颜色搭配数多1，那么7小朋友是“物品”，6种颜色搭配是“抽屉”。根据抽屉原理1，总有两个小朋友取出的两个球的颜色搭配相同。拓展口

7、袋中放有足够多的红、白、蓝三种颜色的球，现有31人轮流从袋子中取球，每人各取3个。证明：至少有4人取出球的颜色一样。分析：类似练习1，取出球的颜色搭配是抽屉。搭配可能有：红红白、红红蓝、蓝蓝红、蓝蓝白、白白红、白白蓝、红白蓝，红红红、白白白、蓝蓝蓝，共10种。也就是说有10个抽屉。31个人看成是物品。311031，那么[3110]1314。根据抽屉原理2，至少有4人取出球的颜色是一样的。总结：构造抽屉的两种方法：（1）从问题出发，相同的就是“抽屉”；（2）从数量关系出发，多的是“物品”，少的是“抽屉”。2．数的整除性与抽屉原理余数的性质：

8、（1）余数相同，差无余数。也就是说，两个数除以同一个数得到的余数相同，那么这两个