鸽巢原理查看源代码讨论查看历史

鸽巢原理

原图链接

中文名: 抽屉原理 外文名: Pigeonhole principle 别 名: 鸽巢原理、重叠原理、狄利克雷抽屉原理 提出者: 狄利克雷 提出时间: 1834年 适用领域: 组合数学 应用学科: 数学

桌上有十个苹果，要把这十个苹果放到九个抽屉里，无论怎样放，我们会发现至少会有一个抽屉里面放不少于两个苹果。这一现象就是我们所说的“抽屉原理”。 抽屉原理的一般含义为：“如果每个抽屉代表一个集合，每一个苹果就可以代表一个元素，假如有n+1个元素放到n个集合中去，其中必定有一个集合里至少有两个元素。” 抽屉原理有时也被称为鸽巢原理。它是组合数学中一个重要的原理。

原理1： 把多于n个的物体放到n个抽屉里，则至少有一个抽屉里的东西不少于两件。

证明（反证法）：如果每个抽屉至多只能放进一个物体，那么物体的总数至多是n×1，而不是题设的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）个物体(例如，将3×5-1=14个物体放入5个抽屉中，则必定有一 个抽屉中的物体数少于等于3-1=2)。

运用抽屉原理的核心是分析清楚问题中，哪个是物件，哪个是抽屉。例如，属相是有12个，那么任意37个人中，至少有一个属相是不少于4个人。这时将属相看成12个抽屉，则一个抽屉中有 37/12，即3余1，余数不考虑，而向上考虑取整数，所以这里是3+1=4个人，但这里需要注意的是，前面的余数1和这里加上的1是不一样的。

因此，在问题中，较多的一方就是物件，较少的一方就是抽屉，比如上述问题中的属相12个，就是对应抽屉，37个人就是对应物件，因为37相对12多。

最差原则

最差原则，即考虑所有可能情况中，最不利于某件事情发生的情况。

例如，有300人到招聘会求职，其中软件设计有100人，市场营销有80人，财务管理有70人，人力资源管理有50人。那么至少有多少人找到工作才能保证一定有70人找的工作专业相同呢？

此时我们考虑的最差情况为：软件设计、市场营销和财务管理各录取69人，人力资源管理的50人全部录取，则此时再录取1人就能保证有70人找到的工作专业相同。因此至少需要69*3+50+1=258人。

根据第一抽屉原理之原理2推导：mn+1个人的时候必有m+1个人找到的工作专业相同，所以是要求出mn+1的人数，已知n=3，m+1=70。考虑 到人力资源专业只有50人，得出mn+1=(69*3+50)+1=258人。

一个抽屉里有20件衬衫，其中4件是蓝的，7件是灰的，9件是红的，则应从中随意取出多少件才能保证有5件是同颜色的？

根据鸽巢原理，n个鸽巢，kn + 1只鸽子，则至少有一个鸽巢中有k + 1只鸽子。若根据鸽巢原理的推论直接求解，此时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件蓝色衬衫都被抽取出这 一最差情况的存在，所以应该先考虑最差情况，然后在此基础上再运用鸽巢原理。

证明

（反证法）：若每个抽屉都有不少于m个物体，则总共至少有mn个物体，与题设矛盾，故不可能。

表现形式

把它推广到一般情形有以下几种表现形式。

形式一：设把n+1个元素划分至n个集合中(A1，A2，…，An)，用a1，a2，…，an分别表示这n个集合对应包含的元素个数，则：至少存在 某个集合Ai，其包含元素个数值ai大于或等于2。

证明：（反证法）假设结论不成立，即对每一个ai都有ai<2，则因为ai是整数，应有ai≤1，于是有：

a1+a2+…+an≤1+1+…+1=n<n+1，这与题设矛盾。

所以，至少有一个ai≥2，即必有一个集合中含有两个或两个以上的元素。

形式二：设把nm+1个元素划分至n个集合中(A1，A2，…，An)，用a1，a2，…，an表示这n个集合对应包含的元素个数，则：至少存在某个集合Ai，其包含元素个数值ai大于或等于m+1。

证明：（反证法）假设结论不成立，即对每一个ai都有ai<m+1，则因为ai是整数，应有ai≤m，于是有：

a1+a2+…+an≤m+m+…+m=nm<nm+1，这与题设相矛盾。

所以，至少有存在一个ai≥m+1

知识扩展——高斯函数[x]定义：对任意的实数x，[x]表示“不大于x的最大整数”。例如：[3.5]=3，[2.9]=2，[－2.5]=－3，=7，…… 一般地，我们有：[x]≤x<[x]+1

形式三：设把n个元素分为k个集合A1，A2，…，Ak，用a1，a2，…，ak表示这k个集合里相应的元素个数，需要证明至少存在某个ai大于 或等于[n/k]。

证明：（用反证法）假设结论不成立，即对每一个ai都有ai<[n/k]，于是有：

a1+a2+…+ak<[n/k]+[n/k]+…+[n/k] =k*[n/k]≤k*(n/k)=n

k个[n/k] ∴ a1+a2+…+ak<n 这与题设相矛盾。所以，必有一个集合中元素个数大于或等于[n/k]

形式四：设把q1+q2+…+qn－n+1个元素分为n个集合A1，A2，…，An，用a1，a2，…，an表示这n个集合里相应的元素个数，需要证明至少存在某个i，使得ai大于或等于qi。

证明：（用反证法）假设结论不成立，即对每一个ai都有ai<qi，因为ai为整数，应有ai≤qi－1，

于是有：a1+a2+…+an≤q1+q2+…+qn－n <q1+q2+…+qn－n+1这与题设矛盾。

所以，假设不成立，故必有一个i,在第i个集合中元素个数ai≥qi

形式五：证明：（用反证法）将无穷多个元素分为有限个集合，假设这有限个集合中的元素的个数都是有限个，则有限个有限数相加，所得的数必是有限数，这就与题设产生矛盾，所以，假设不成立，故必有一个集合含有无穷多个元素。（借由康托的无穷基数可将鸽巢原理推广到无穷集中。）

一般表述

在上面的第一个结论中，由于一年最多有366天，因此在367人中至少有2人出生在同月同日。这相当于把367个东西放入 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个数除以3所得余数相同，即它们两两之差是3的倍数。

如果问题所讨论的对象有无限多个，抽屉原理还有另一种表述：

“把无限多个东西任意分放进n个空抽屉（n是自然数），那么一定有一个抽屉中放进了无限多个东西。”

用高斯函数来叙述一般形式的抽屉原理的是：将m个元素放入n个抽屉，则在其中一个抽屉里至少会有

[(m-1)/n]+1个元素。

集合论的表述是：设A和B为同基数的有限集，f:A→B为一个映射，则f为单射的充要条件是f为满射。

抽屉原理的内容简明朴素，易于接受，它在数学问题中有重要的作用。许多有关存在性的证明都可用它来解决。

这个问题可以用如下方法简单明了地证出：

在平面上用6个点A、B、C、D、E、F分别代表参加集会的任意6个人。如果两人以前彼此认识，那么就在代表他们的两点间连成一条红线；否则连一条蓝线。考虑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ósa) 提出这个问题，而小波萨思考了不足半分钟便能给出正确的答案。

波萨是这样考虑问题：取n个盒子，在第一个盒子我们放1和2，在第二个盒子我们放3和4，第三个盒子是放5和6，依此类推直到第n个盒子放2n-1和2n这两个数。

如果我们在n个盒子里随意抽出n+1个数。我们马上看到一定有一个盒子是被抽空的。因此在这n+1个数中必有两个数是连续数，很明显的 连续数是互质的。因此这问题就解决了！这就是利用了鸽巢原理的核心思想。