| 词条 | 鸽笼原理 |
| 释义 | 鸽笼原理 (抽屉原理) “如果有五个鸽子笼，养鸽人养了6只鸽子，那么当鸽子飞回笼中后，至少有一个笼子中装有2只鸽子。”这个简单的事实就是著名的鸽笼原理，在我们国家更多地称为抽屉原理。 更一般的叙述有n+1件或n+1件以上的物品要放到n个抽屉中，那么至少有一个抽屉里有两个或两个以上物品。 英文：pigeonhole principle 证明此原理用反证法容易证明其正确性。 应用应用广泛抽屉原理虽然简单，但应用却很广泛。它可以解答很多有趣的问题，其中有些问题还具有相当的难度。 下面我们来研究有关的一些问题。 问题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个数,至少必有两个数在同一组中,这两个数中的一个必为另一个的整数倍。 另解：(个人觉得)这个问题有更容易理解的解法 将这51个数,全部转换为 2^r * b ( 2的r次方乘以b) 比如这51个数为3、5、7、8、22...... 2 --> 2^1 * 1 5 -->2^0 * 57 -->2^0 * 7 8 -->2^3 * 1 22-->2^1 * 11 ...... 提取出的51个b都满足 (1) 必然是奇数 (2) 必然小于100 而小于100的奇数只有50个，由鸽笼原理 ==> 必然存在2个b相等,则这2个b对应的数必然满足，其中一个是另一个的倍数 问题517个科学家中每个人与其余16个人通信,他们通信所讨论的仅有三个问题,而任两个科学家之间通信讨论的是同一个问题.证明:至少有三个科学家通信时讨论的是同一个问题. 解：不妨设A是某科学家,他与其余16位讨论仅三个问题,由鸽笼原理知,他至少与其中的6位讨论同一问题.设这6位科学家为B,C,D 若这6位中有两位之间也讨论甲问题,则结论成立.否则他们6位只讨论乙,丙两问题.这样又由鸽笼原理知B至少与另三位讨论同一问题,不妨设这三位是C,D,E,且讨论的是乙问题。 若C，D，E中有两人也讨论乙问题，则结论也就成立了。否则，他们间只讨论丙问题，这样结论也成立。 问题6（2002年数学建模d题）你所在的年级有5个班，每班一支球队在同一块场地上进行单循环赛, 共要进行10场比赛. 如何安排赛程使对各队来说都尽量公平呢. 下面是随便安排的一个赛程: 记5支球队为A, B, C, D, E，在下表左半部分的右上三角的10个空格中, 随手填上1,2,¼10, 就得到一个赛程, 即第1场A对B, 第2场B对C, ¼, 第10场C对E. 为方便起见将这些数字沿对角线对称地填入左下三角. 这个赛程的公平性如何呢, 不妨只看看各队每两场比赛中间得到的休整时间是否均等. 表的右半部分是各队每两场比赛间相隔的场次数, 显然这个赛程对A, E有利, 对D则不公平.
A X 1 9 3 6 1, 2, 2 B 1 X 2 5 8 0, 2, 2 C 9 2 X 7 10 4, 1, 0 D 3 5 7 X 4 0, 0, 1 E 6 8 10 4 X 1, 1, 1 |
| 随便看 |
百科全书收录4421916条中文百科知识，基本涵盖了大多数领域的百科知识，是一部内容开放、自由的电子版百科全书。