鸽笼原理

"如果有五个鸽子笼,养鸽人养了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,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四个数字中只有一个不对.下面逐个讨论验证:若3不对,则第2位的1对,因此这个数位上只能取6,第2位取1,第3位不能取2,5(因为2,5在第4,5位是对的)所以第3位取0,第4位取2,第五位取5,剩下第6位必取3,此数字为610253.

若1不对,则第1位的3对,第2位只能取0(因2在第4位是对的),第3位上A,B,C的数各为0,5,2,这三个数均不能取(因0已在第2位,而5,2已在第5,4位).因此,这时没有符合要求的取数法.若2不对,则第1位取3,第2位取1都对.第3位可以取0或2,第4位只能取6,第5位取5.但第6位取A,B,C的数各是1,3,5,这3个数都在前面被取过,因此都不能取.这时也没有符合要求的取数法.