组合数学（6）鸽笼原理

一些数学问题，比方说“鸽笼原理”，是如此地显然，以至于人们或许以为只能给出同样显然的结果。为说服人们“那可不一定”，我们要演示一些Paul Erdos建议的例子和理论。下面的十分著名的鸽笼原理就是我们在日常生活中不可避免的著名定理.

鸽笼原理：若八把n个物体放在r个盒子里面，r n，那么至少有一个盒子包含多于一个物体。定理1（鸽笼原理的加强形式）将q1 q2 ... qn n 1个物件放入n个合子内，则一定有某个i使得第i个合子内部至少有qi个物件。推论2（一般的鸽笼原理）将n 1个物件放入n个合子内，一定有一个盒子里面至少有两个物件。推论3.将n(r 1) 1个物件放入n个合子内，一定有一个合子里面至少有r个物件。推论4.若n个自然数m1,m2,...,mn的算数平均数m1 m2 ... mn r 1，则一定有一个自然数mi r。例1.在前200个自然n

数中任意取101个数。求证：一定有两个数，其中一个被另外一

整除。例2.将1,2,3,...,10随机摆成一圈，证明：其中必然有某三个相邻的数，它们之和不小于17。例3. 一个棋手为参加一次锦标赛将进行为期77天的练习。如果他每天至少下一盘棋，而每周至多下12盘棋，证明：一定存在一个正整数n使得他在这77天的训练里面一共下了21盘棋。

例4．在数列1,1,2,3,5,8,3,1,4,...中从第三项起，每一项是前面两项之和，但是加法是(mod10)做的，即，是前两项的和的个位数字。证明；这个数列是纯周期的（即，从某一项开始，重复出现），周期长度最多是多少？

例5.任何六个人中总有3个人相互认识或相互之间完全不认识.

例6. 在3 4cm的长方形中放置6个点。证明：可以找到两个点，其相距不大于cm（第十五界全苏数学奥林

匹克十年级试题）。

例7. 证明：在任何一个凸2n边形中，总有一条对角线不

与任何一条边平行。

例8. 在边长为1的正方形中，放有51个小虫。证明；任何时候总至少有三个小虫可以被一个半径为1/7的圆盖住。

解答：把单位正方形分成25个边长为1/5的小正方形。由抽屉原理，其中一定有三个小虫位于某一个小正方形内。容易知道，这个小正方形可以被一个半径是1/7的圆所覆盖。 例9.在同一间房子里面有n( 3)个人。证明：总有两个人在这n个人中的熟人一样多。 例10.由1到99（包括1和99）中人选10个自然数做成一个集合。证明：该集合存在两个不相交的非空子集合，它们的元素之和相等。

例11. 设a1,a2,...,a100和b1,b2,...,b100是集合{1,2,...,100)上的两个排列。证明：乘积a1b1,a2b2,...,a100b100中总有两个数被100所除的余数相同。