鸽笼原理(抽屉原理)就是"如果有五个鸽子笼，养鸽人养了6只鸽子，那么当鸽子飞回笼中后，至少有一个笼子中装有2只鸽子。"这个简单的事实就是著名的鸽笼原理，在我们国家更多地称为抽屉原理。

故事背景

路易·波萨（Louis Pósa）是匈牙利的年青数学家，1988年时约40岁。他在14岁时就已能够发表有相当深度的数学论文。大学还没有读完，就已获得科学博士的头衔。

他的妈妈是一个数学家。小时他受母亲的影响，很爱思考问题。母亲看他对数学有兴趣，也鼓励他在这方面发展。她给他一些数学游戏，或数学玩具启发他独立思考问题。在母亲的循循善诱之下，他在读小学时已经自己拿高中的数学书来看了。真正训练他成为一个数学家的是匈牙利鼎鼎有名的大数学家。

厄杜斯在数论、图论等数学分支有很深入的研究，他把一生献给数学，从来没有想到结婚，只和自己的母亲为伴，他经常离开自己的祖国到外国去作研究和演讲。在东欧国家里像厄杜斯能这样随意离开自己的国家进出西方世界的数学家并不太多。他到处以数学会友，他在数学方面的多产，以及在解决问题上有巧妙的方法，使他在世界数学界上享有甚高的声誉。对于他的祖国来讲，他重要的贡献不单是在数学的研究，而是他一回到自己的国家就专心致志地培养年青一代的数学家，告诉他们外国目前数学家注意的问题，扩大他们的视野。

我这里要讲他怎么样发现路易·波萨的才能的故事。

有一次他从国外回来后，听到朋友讲起有一个很聪明的小东西，在小学能解决许多困难的数学问题，于是就登门拜访这小鬼的家庭。

波萨的家人很高兴请厄杜斯教授共进晚餐。在喝汤的时候，厄杜斯想考一考坐在他旁边的12岁小孩的能力，于是就问他这样的一个问题：

“如果你手头上有n+1个整数，而这些整数是小于或等于2n，那么你一定会有一对数是互素的。你知道这是什么原因吗？”

这小鬼不到半分钟的思考，就很快给出这个问题的解答。他的解答又是那么巧妙，使得厄杜斯教授叹服。认为这是一个难得的“英才”，应该好好地培养。

厄杜斯以后系统地教这小鬼数学，不到两年的时间波萨就成为一个“小数学家”了，而且发现在图论一些深湛的定理。

厄杜斯提问题

对于许多离开学校很久的读者，我想做一点解释厄杜斯提出的问题。

首先我们解释：一对数是互素是什么意思？

我们知道如果把自然数1，2，3，4，5，…照大小排起来，从2开始像2，3，5，7，11，13，17，19，23，…，等数都有这样特别的性质：除1和本身以外，再找不到比它小的数能整除它。

具有这样特殊性质的数我们称它为素数（Prime number）。

我们小学时不是学习过把整数因子分解吗？那就是把整数用素数的乘积来表示。例如50=2×5×5，108=2×2×3×3×3=22×33。

两个自然数称为互素（Coprime），如果把它们表示成素数乘积时，找不到它们有公共的素因数。例如{8，11}一对数是互素。10和108不是互素，因为它们有公共的素因数2。

现在让我们来理解厄杜斯的问题。先对一些特殊的情况来考虑：

当n=2时，我们手头上有3个整数，这些整数是小于或等于4，可以选出的只是{2，3，4}，不包含1，很明显的看出{2，3}或{3，4}是互素的。

n=3时，在小于或等于6的整数找4个整数组（不要包含1），可能找出的有{2，3，4，5}，{2，3，4，6}，{3，4，5，6}，{2，4，5，6}等等。你一个个检查一定会在每组中找出最少一对互素的数。

可以看出随着n增大时，构造n+1个不同数的数组的个数就会增加很大。如果我们是这样一个一个地对这些数组来检查证明，这真会成为：“吾生也有涯，而数无涯”，那时候皓首不但穷尽不了，最后真是要“呜呼哀哉”了！

如果读者中有人说：“我有苦干和拚命干的精神！”我还是要劝他不要用这样的苦干法，应该学会“巧干”，这才是最重要的。不然的话，人家小孩子用不到半分钟就解决了的问题，而我们苦干再加上拚命干却花一生还没法子解决，这不是太浪费生命吗？

我现在准备介绍波萨对这问题的解法。可是我希望读者先自己想想看怎么样解决这问题。如果你能找到和下面不同的解决方法，请来信告诉我。如果你花过一些时间还想不出，那么就请读下去，你这时就会欣赏波萨解决方法的巧妙，而最重要的你会学懂“鸽笼原理”，说不定以后你成为业余数学家或者专业数学家还会用到这个原理呢！

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

现在我们在n个盒子里随意抽出n+1个数。我们马上看到一定有一个盒子是被抽空的。因此在这n+1个数中曾有两个数是连续数，很明显的连续数是互素的。因此这问题就解决了！

你说这个解法是不是很容易明白又非常巧妙呢？！

鸽笼原理

波萨在证明过程中用到在数学上称为鸽笼原理（PigeonholePrinciple）的东西。这原理是这样说的：如果把n+1个东西放进n个盒子里，有一些盒子必须包含最少2个东西。 有高六层的鸽笼，每一层有四个间隔，所以总共有6×4=24个鸽笼。现在我放进25只鸽进去，你一定看到有一个鸽笼会有2只鸽要挤在一起。

鸽笼原理就是这么简单，3岁以上的小孩子都会明白。

可是这原理在数学上却是有很重要的应用。

在19世纪时一个名叫狄利克雷（Dirichlet 1805—1859）的数学家，在研究数论的问题时最早很巧妙运用鸽笼原理去解决问题。后来德国数学家敏古斯基（Minkowski 1864—1909）也运用这原理得到一些结果。

到了20世纪初期杜尔（A．Thue 1863—1922）在不知道狄利克雷和敏古斯基的工作情况下，很机巧地利用鸽笼原理来解决不定方程的有理数解的问题，有12篇论文是用到这个原理。

后来西根（C．L．Siegel，1896—？）利用杜尔的结果发现了现在称为西根引理的东西，这引理（Lemma）是在研究超越数时是最基本必用的工具。

因此读者不要小看这个看来简单的原理，你如果善于运用是能帮助你解决一些数学难题的。

日常运用

我这里举一些和日常生活有关的一些问题，你可以看到数学在这里的运用。 （1）月黑风高穿袜子

有一个晚上你的房间的电灯忽然间坏了，伸手不见五指，而你又要出去，于是你就摸床底下的袜子。你有三双分别为红、白、蓝颜色的袜子，可是你平时做事随便，一脱袜就乱丢，在黑暗中不能知道哪一双是颜色相同的。

你想拿最少数目的袜子出去，在外面借街灯配成同颜色的一双。这最少数目应该是多少？

如果你懂得鸽笼原理，你就会知道只需拿出去四只袜子就行了。

为什么呢？因为如果我们有三个涂上红、白、蓝的盒子，里面各放进相对颜色的袜子，只要我们抽出4只袜子一定有一个盒子是空的，那么这空的盒子取出的袜子是可以拿来穿。

（2）手指纹和头发

据说世界上没有两个人的手指纹是一样的，因此警方在处理犯罪问题时很重视手指纹，希望通过手指纹来破案或检定犯人。

可是你知道不知道：在12亿中国人当中，最少有两个人的头发是一样的多？

道理是很简单，人的头发数目是不会超过12亿这么大的数目字！假定人最多有N根头发。现在我们想像有编上号码1，2，3，4，…一直到N的房子。

谁有多少头发，谁就进入那编号和他的头发数相同的房子去。因此张乐平先生的“三毛”应该进入“3号房子”。

现在假定每间房巳进入一个人，那么还剩下“九亿减N”个人，这数目不会等于零，我们现在随便挑一个放进一间和他头发数相同的房子，他就会在里面遇到和他有相同头发数目的同志了。

（3）戏院观众的生日

在一间能容纳1500个座位的戏院里，证明如果戏院坐满人时，一定最少有五个观众是同月同日生。

现在假定一年有三百六十五天。想像有一个很大的鸽子笼，这笼有编上“一月一日”，“一月二日”，至到“十二月三十一日”为止的标志的间隔。

假定现在每个间隔都塞进四个人，那么 4×365=1460个是进去鸽子笼子里去，还剩下1500-1460=40人。只要任何一人进入鸽子笼，就有五个人是有相同的生日了。

一般的叙述

抽屉原理的更一般的叙述是:

有n+1件或n+1件以上的物品要放到n个抽屉中,那么至少有一个抽屉里有两个或两个以上物品.

此原理用反证法容易证明其正确性.

抽屉原理虽然简单,但应用却很广泛,它可以解答很多有趣的问题,其中有些问题还具有相当的难度.下面我们来研究有关的一些问题.

问题1 某校初中部有30个班,每班平均52人.已知这些学生的90%都是在1978～1980年这三年出生的,问他们中有同年同月同日出生的吗

解:全校共有学生52×30=1560人,1978～1980年间出生的有1560×90%=1404人.

而这三年有365×3+1=1096天.

由鸽笼原理知道,至少有两个同学是同年同月同日出生的.

问题2 一个书架有五层,从下至上依次称第1,第2,…,第5层.今把15册图书分别放在书架的各层上,有些层可以不放,证明:无论怎样放法,书架每层上的图书册数以及相邻两层内图书册数之和,所有这些数中至少有两个是相等的.

解:我们先把这个实际问题抽象成数学问题.用xi表示第i层放书的册数(i=1,2,…,5).

若有某个xi=0,则相邻的一层放书册数等于它与第i层放书册数之和,结论成立.

下面考虑xi≥1(i=1,2,3,4,5)的情况:

(1)若x1,x2,…,x5中已有两数相等,结论成立.

(2)若x1,x2,…,x5两两不等,再由它们和为15,所以它们分别取1,2,3,4,5.我们容易验证,在x1+x2,x2+x3,x3+x4,x4+x5这四个数中不可能同时包含6,7,8,9这四个数(请读者验证).这四个数与x1,x2,…,x5总共九个数,但只能有8种取值,因此其中必有两数相等.

问题3 某个信封上两个邮政编码M和N均由0,1,2,3,5,6这六个不同数字组成,现有4个邮政编码如下:

A:320651,B:105263,C:612305,D:316250.已知编码A,B,C各恰有两个数字的位置与M和N相同,D恰有三个数字的位置与M和N相同,试求M和N.

解：

-------------------------------------------------------------

A:320651 恰有两个数字的位置与M和N相同

B:105263 恰有两个数字的位置与M和N相同

C:612305 恰有两个数字的位置与M和N相同

D:316250 恰有三个数字的位置与M和N相同

-------------------------------------------------------------

首先仔细观察A、B、C。它们虽然均由0、1、2、3、5、6这六个数码组成，但同一数位上的数字都互不相同。

由鸽笼原理知A、B、C 三数中各数位上都有一个数字是正确的(即与M和N的相应数字相同)。

再把D的各数位上的数与A、B、C 比较，发现D中第3位的6和第6位的0在A、B、C 的第3和第6位上没有出现，

因此这两个数码肯定不正确。由已知D有三个数字正确。因此D中的3、1、2、5四个数字中只有一个不对。

得到结果为：31X25X X=未知数

-------------------------------------------------------------

以下数字必须符合31X25X的数字对应位置。必须满足D:316250 恰有三个数字的位置与M和N相同。

下面逐个讨论验证:

若3不对，取得以下结果：

X1X25X 613250 610253

X1X25X 013256 016253

若1不对，取得以下结果：

3XX25X 301256 306251

3XX25X 361250 360251

若2不对，取得以下结果：

31XX5X 312056 316052

31XX5X 310652 312650

若5不对，取得以下结果：

31X2XX 310265 315260

31X2XX 316205 315206

-------------------------------------------------------------

回头校正所有结果，必须满足A、B、C 当中有且仅有两个数字的位置与M和N相同

613250 X 不符合A，排除

610253

013256 X 不符合A，排除

016253 X 第3位为6，排除

301256 x 不符合C，排除

306251 X 第3位为6，排除

361250 X 第6位为0，排除

360251 X

312056 X 不符合B，排除

316052 X 第3位为6，排除

310652 X 不符合A，排除

312650 X 第6位为0，排除

310265

315260 X 第6位为0，排除

316205 X 第3位为6，排除

315206 X 不符合A，排除

-------------------------------------------------------------

最后检验所有条件，可知 610253 与 310265 是满足这些条件的两个数。

问题4 在前100个自然数中任取51个数,求证:一定存在两个数,其中一个是另一个的整数倍.

解:我们用鸽笼原理来考虑.把这100个自然数分成50组,使得每组中的数(如果至少含两个数)是倍数关系,怎样分组呢 我们记

A1={1,1×21,1×22,1×23,…,1×26},

A2={3,3×21,3×22,…,3×25},

A3={5,5×21,5×22,5×23,5×24},

………………………

A25={49,49×2},A26=,A27=,

………………

A50=.

这50组数中包含了从1到100这100个自然数.根据鸽笼原理从中任取51个数,至少必有两个数在同一组中,这两个数中的一个必为另一个的整数倍.

问题5 17个科学家中每个人与其余16个人通信,他们通信所讨论的仅有三个问题,而任两个科学家之间通信讨论的是同一个问题.证明:至少有三个科学家通信时讨论的是同一个问题.

解:不妨设A是某科学家,他与其余16位讨论仅三个问题,由鸽笼原理知,他至少与其中的6位讨论同一问题.设这6位科学家为B,C,D

若这6位中有两位之间也讨论甲问题,则结论成立.否则他们6位只讨论乙,丙两问题.这样又由鸽笼原理知B至少与另三位讨论同一问题,不妨设这三位是C,D,E,

相关问题

（1）给出任意12个数字，证明当用11来除时，一定有一对数的余数是相同。 （2）如果在一个每边都是2单位的正三角形板上随便钉上17个大

（3）如果在一个每边都是2单位的正方形板上随便钉上5根钉，

（4）我们一定能够在一个每边都是2单位长的正方形板上适当的钉上9根钉，使它们之中不存在有两根钉的距离是小于1单位。

（5）（英国数学奥林匹克1975年的问题）在一个半径为1单位的圆板上钉7个钉，使得没有两个钉的距离是大过或等于1，那么这7个钉一定会有一个位置恰好是在圆心上。

（6）任意6个人在一起，一定会有其中两种情形之一发生：第一种情形──有3个人互相认识。第二种情形──有3个人，他们之间完全不认识。

（7）（a）你能不能在从1到200的整数里挑选出100个自然数，使到任何其中之一不能整除剩下的99个数。

（b）证明如果在从1到200间随便取101个自然数，那么一定最少有两个自然数，其中之一能整除另外的数。

（8）随便给出10个10位数的数字，我们一定能把它分成两部分，使到每一部分的整数的和是等于其他一部分的整数的和。