鸽笼原理(抽屉原理)
"如果有五个鸽子笼,养鸽人养了6只鸽子,那么当鸽子飞回笼中后,至少有一个笼子中装有2只鸽子."这个简单的事实就是著名的鸽笼原理,在我们国家更多地称为抽屉原理.
抽屉原理的更一般的叙述是:
有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,