北师大版初一数学下册抽屉原理

1、抽屉原理本节课的基本依据是“抽屉原理”。由于起始布置的任务是制定得到三位或更少位数字的法则。因为在。到999之间有1000个整数，把 这1000个整数看成1000个“抽 屉”，那么按既 定的程序得出的结果看成“苹果”，则苹果必定属于某一个抽屉，所以抽屉原理就保证了程序迟早会产生一个数列前面出现过的数字。因此，必然出现循环！最多也就是运用1000次程序后循环。抽屉原理（名词）桌上有十个苹果，要把这十个苹果放到九个抽屉里，无论怎样放，我们会发现至少会有一个抽屉里面至少放两个苹果。这一现象就是我们所说的抽屉原理”。抽屉原理的一般含义为：如果每个抽屉代表一个集合，每一个苹果就可以代表一个元素，假如有n

2、+1个元素放到n个集合中去，其中必定有一个集合里至少有两个元素。”抽屉原理有时也被称为鸽巢原理。它是组合数学中一个重要的原理。1中文名抽屉原理pigeonhole principle别称鸽巢原理、重叠原理、狄利克雷抽屉原理提出者狄利克雷1834 年应用学科数学”适用领域范围组合数学目录1. 1原理2. ?第一抽屉原理3. ?第二抽屉原理4. 2常见运用1. ?构造抽屉的方法2. ?最差原则.3. ?证明4. 3表现形式1.4 一般表述05趣闻抽屉原理原理编辑抽屉原理第一抽屉原理原理1 :把多于n+1个的物体放到n个抽屉里，则至少有一个抽屉里的东西不少于两件。suhi ,u ft 7 +3 w抽

3、屉原理证明（反证法）：如果每个抽屉至多只能放进一个物体，那么物体的总数至多是 nxi,而不是题设的n+k （k 1）故不可能。原理2 :把多于 mn （m乘n） +1 （n不为0）个的物体放到 n个抽屉里，则至少有一 个抽屉里有不少于（m+1 ）的物体。证明（反证法）：若每个抽屉至多放进m个物体，那么n个抽屉至多放进 mn个物体,与题设不符，故不可能。原理3:把无穷多件物体放入 n个抽屉，则至少有一个抽屉里有无穷个物体。原理1、2、3都是第一抽屉原理的表述。抽屉原理第二抽屉原理把（mn 1）个物体放入n个抽屉中，其中必有一个抽屉中至多有（m 1）个物体（例如，将3x5-1=14个物体放入5个抽

4、屉中，则必定有一个抽屉中的物体数少于等于3-仁2）。抽屉原理常见运用编辑抽屉原理构造抽屉的方法运用抽屉原理的核心是分析清楚问题中，哪个是物件，哪个是抽屉。例如，属相是有12个，那么任意37个人中，至少有几个人属相相同呢？这时将属相看成12个抽屉，则一个抽屉中有37/12,即3余1,余数不考虑，而向上考虑取整数，所以这里是3+1=4个人，但这里需要注意的是，前面的余数1和这里加上的1是不一样的。因此，在问题中，较多的一方就是物件，较少的一方就是抽屉，比如上述问题中的属 相12个，就是对应抽屉，37个人就是对应物件，因为37相对12多。抽屉原理最差原则最差原则，即考虑所有可能情况中，最不利于某件事

5、情发生的情况。例如，有300人到招聘会求职，其中软件设计有100人，市场营销有80人，财务管理有70人，人力资源管理有 50人。那么至少有多少人找到工作才能保证一定有70人找的工作专业相同呢？此时我们考虑的最差情况为：软件设计、市场营销和财务管理各录取69人，人力资源管理的50人全部录取，则此时再录取1人就能保证有70人找到的工作专业相同。因此至少需要69*3+50+1=258 人。一个抽屉里有20件衬衫，其中4件是蓝的，7件是灰的，9件是红的，则应从中随 意取出多少 件才能保证有5件是同颜色的？根据鸽巢原理， n 个鸽巢， kn + 1 只鸽子，则至少有一个鸽巢中有k + 1 只鸽子。若根据

6、鸽巢原理的推论直接求解，此时 k=4 , n=3 ，则应抽取3 x 4 + 1 = 13 件才能保证有5件同色。其实不然，问题的模型和鸽巢原理不尽相同。在解决该问题时，应该考虑最差的 情况，连续抽取过程中抽取出 4 件蓝色的衬衣，即 4 件蓝色，取走后，问题变成有灰色和红色构成相同颜色的情况，这时， n=2 ， k + 1 = 5, k = 4. 故应取 4 + 4 x 2 + 1 = 13 件。问题分析：该情况下鸽巢原理的推论不再适用，由于蓝色的衬衫只有4 件，而题目中要求有 5 件是同色的，导致4 件蓝色衬衫都被抽取出这一最差情况的存在，所以应该先考虑最差情况，然后在此基础上再运用鸽巢原理

7、。抽屉原理证明（反证法）：若每个抽屉都有不少于 m 个物体，则总共至少有mn 个物体，与题设矛盾，故不可能。 2临=|hj （i= 1.7+h 亦世 p胃世叫 冲-叫kla d 1常h?： 1 +叩十f r *耳.% i *1中？ r 呻 pr 甘牛1抽屉原理表现形式编辑把它推广到一般情形有以下几种表现形式。形式一：设把n+1个元素划分至n个集合中（a1 , a2,，an）,用a1 , a2，an分别表 示这 n 个集合对应包含的元素个数，则：至少存在某个集合ai ，其包含元素个数值ai 大于或等于2 。证明：（反证法）假设结论不成立，即对每一个ai 都有ai2 ，则因为ai 是整数，应有 a

8、i 1 于是有：a1+a2+ +an 1+1+ - +1= n2 即必有一个集合中含有两个或两个以上的元素。形式二：设把nm+1个元素划分至n个集合中（a1 , a2,，an）,用a1 , a2，an表示 这n个集合对应包含的元素个数，则：至少存在某个集合ai,其包含元素个数值ai 大于或等于m+1 。证明：（反证法）假设结论不成立，即对每一个ai 都有 aim+1 , 则因为 ai 是整数，应有ai m,于是有：a1+a2+an m+m+ ? +m=nm m+1知识扩展一一高斯函数x定义：对任意的实数 x,冈表示不大于x的最大整数”。例 如：3.5=3 , 2.9=2， 2.5= 3 , 7

9、=7 ,一般地，我们有：x xx+1形式三：设把n个元素分为k个集合a1 , a2，ak,用al , a2，ak表示这k个集合里 相应的元素个数，需要证明至少存在某个ai大于或等于n/k。证明：（用反证法）假设结论不成立，即对每一个ai都有ain/k,于是有：a1+a2+akn/k+n/k+n/k =k?n/k k? （n/k） =nk个n/k ? a1+a2+- - +akn这与题设相矛盾。所以，必有一个集合中元素个数大于或等于n/k形式四：设把q1+q2+-+qn - n+1个元素分抽屉原理为n个集合a1 , a2 ,，an ,用al , a2,，an表示这n个集合里相应的元素个 数，需要

10、证 明至少存在某个i,使得ai大于或等于qio证明：（用反证法）假设结论不成立，即对每一个ai都有aiqi,因为ai为整数，应有 ai c 1 ,于是有：a1+a2+ +a nw q1+q2+ +qn n qi形式五：证明：（用反证法）将无穷多个元素分为有限个集合，假设这有限个集合中的元素的个数都是有限个，则有限个有限数相加，所得的数必是有限数，这就与题设产生矛盾，所以，假设不成立，故必有一个集合含有无穷多个元素。（借由康托的无穷基数可将鸽巢原理推广到无穷集中。）抽屉原理一般表述编辑在上面的第一个结论中，由于一年最多有366天，因此在367人中至少有2人出生在同月同日。这相当于把367个东西放

11、入366个抽屉，至少有2个东西在同一抽屉里。在第二个结论中，不妨想象将5双手套分别编号，即号码为1 , 2,，5的手套各有两只，同号的两只是一双。任取6只手套，它们的编号至多有5种，因此其中至少有两只的号码相同。这相当于把 6个东西放入5个抽屉，至少有2个东西在同一抽屉里。抽屉原理的一种更一般的表述为：把多于 kn+1 个东西任意分放进n 个空抽屉 (k 是正整数 ) ，那么一定有一个抽屉中 放进了至少k+1 个东西。”利用上述原理容易证明： 任意 7 个整数中，至少有3 个数的两两之差是3 的倍数。” 因为任一整数除以 3 时余数只有0 、 1 、 2 三种可能，所以 7 个整数中至少有3

12、个数除以 3 所得余数相同，即它们两两之差是3 的倍数。如果问题所讨论的对象有无限多个，抽屉原理还有另一种表述：把无限多个东西任意分放进n 个空抽屉 ( n 是自然数 ) ，那么一定有一个抽屉中放进了无限多个东西。”用高斯函数 来叙述一般形式的抽屉原理的是： 将 m 个元素放入n 个抽屉，则在其中一个抽屉里至少会有(m-1)/n+1 个元素。抽屉原理的内容简明朴素，易于接受，它在数学问题中有重要的作用。许多有关存在 性的证明都可用它来解决。这个问题可以用如下方法简单明了地证出：在平面上用 6个点 a、 b、 c、 d、 e、 f 分别代表参加集会的任意6个人。如果两人以前彼此认识，那么就在代表

13、他们的两点间连成一条红线；否则连一条蓝线。考虑 a 点与其余各点间的5条连线ab, ac,，af,它们的颜色不超过2种。根据抽屉原理可知其中至少有3条连线同色，不妨设ab， ac， ad 同为红色。如果bc， bd， cd 3 条连线 中有一条 (不妨设为bc)也为红色，那么三角形 abc即一个红色三角形，a、b、c代表的 3 个人以前彼此相识：如果bc、 bd、 cd 3 条连线全为蓝色，那么三角形 bcd 即一个蓝色三角形， b 、 c 、 d 代表的 3 个人以前彼此不相识。不论哪种情形发生，都符合问题的 结论。六人集会问题是组合数学中著名的 拉姆塞定理的一个最简单的特例，这个简单问题的证明思想可用来得出另外一些深入的结论。这些结论构成了组合数学中的重要内容 拉姆塞理论。从六人集会问题的证明中，我们又一次看到了抽屉原理的应用。抽屉原理趣闻编辑已知 n+ 1 个正整数，它们全都小于或等于 2n ，证明当中一定有两个数是互质的。匈牙利大数学家厄杜斯(paulerdous,1913 - 1996) 向当年年仅11 岁的波萨(louisp dsa) ，而小