高中数学竞赛系列讲座：抽屉原理
在数学问题中有一类与“存在性”有关的问题,例如：“13个人中至少有两个人出生在相同月份”；“某校400名学生中,一定存在两名学生,他们在同一天过生日”；“2003个人任意分成200个小组,一定存在一组,其成员数不少于11”；“把[0,1]内的全部有理数放到100个集合中,一定存在一个集合,它里面有无限多个有理数”。这类存在性问题中,“存在”的含义是“至少有一个”。在解决这类问题时,只要求指明存在,一般并不需要指出哪一个,也不需要确定通过什么方式把这个存在的东西找出来。这类问题相对来说涉及到的运算较少,依据的 理论也不复杂,我们把这些理论称之为“抽屉原理”。
“抽屉原理”最先是由19世纪的德国数学家迪里赫莱（Dirichlet）运用于解决数学问题的,所以又称“迪里赫莱原理”,也有称“鸽巢原理”的。这个原理可以简单地叙述为“把10个苹果,任意分放在9个抽屉里,则至少有一个抽屉里含有两个或两个以上的苹果”。这个道理是非常明显的,但应用它却可以解决许多有趣的问题,并且常常得到一些令人惊异的结果。抽屉原理是国际国内各级各类数学竞赛中的重要内容,本讲就来学习它的有关知识及其应用。 （一） 抽屉原理的基本形式
定理1、如果把n+1个元素分成n个集合,那么不管怎么分,都存在一个集合,其中至少有两个元素。
证明：（用反证法）若不存在至少有两个元素的集合,则每个集合至多1个元素,从而n个集合至多有n个元素,此与共有n+1个元素矛盾,故命题成立。
在定理1的叙述中,可以把“元素”改为“物件”,把“集合”改成“抽屉”,抽屉原理正是由此得名。
同样,可以把“元素”改成“鸽子”,把“分成n个集合”改成“飞进n个鸽笼中”。“鸽笼原理”由此得名。
例1． 已知在边长为1的等边三角形内（包括边界）有任意五个点（图1）。证明：至少有两个点之间的距离不大于（广东省数学竞赛题）
分析：5个点的分布是任意的。如果要证明“在边长为1的等边三角形内（包括边界）有5个点,那么这5个点中一定有距离不大于的两点”,则顺次连接三角形三边中点,即三角形的三条中位线,可以分原等边三角形为4个全等的边长为的小等边三角形,则5个点中必有2点位于同一个小等边三角形中（包括边界）,其距离便不大于。
以上结论要由定理“三角形内（包括边界）任意两点间的距离不大于其最大边长”来保证,下面我们就来证明这个定理。
如图2,设BC是△ABC的最大边,P,M是△ABC内（包括边界）任意两点,连接PM,过P分别作AB、BC边的平行线,过M作AC边的平行线,设各平行线交点为P、Q、N,那么 ∠PQN=∠C,∠QNP=∠A
因为BC≥AB,所以∠A≥∠C,则∠QNP≥∠PQN,而∠QMP≥∠QNP≥∠PQN（三角形的外角大于不相邻的内角）,所以 PQ≥PM。显然BC≥PQ,故BC≥PM。
由此我们可以推知,边长为的等边三角形内（包括边界）两点间的距离不大于。 说明：
（1）这里是用等分三角形的方法来构造“抽屉”。类似地,还可以利用等分线段、等分正方形的方法来构造“抽屉”。例如“任取n+1个正数ai,满足0＜ai≤1（i=1,2,…,n+1）,试证明：这n+1个数中必存在两个数,其差的绝对值小于”。又如：“在边长为1的正方形内任意放置五个点,求证：其中必有两点,这两点之间的距离不大于。
（2）例1中,如果把条件（包括边界）去掉,则结论可以修改为：至少有两个点之间的距离小于\请读者试证之,并比较证明的差别。 （3）用同样的方法可证明以下结论：
i）在边长为1的等边三角形中有n2+1个点,这n2+1个点中一定有距离不大于的两点。 ii）在边长为1的等边三角形内有n2+1个点,这n2+1个点中一定有距离小于的两点。 （4）将（3）中两个命题中的等边三角形换成正方形,相应的结论中的换成,命 题仍然成立。
（5）读者还可以考虑相反的问题：一般地,“至少需要多少个点,才能够使得边长 为1的正三角形内（包括边界）有两点其距离不超过”。
例2．从1-100的自然数中,任意取出51个数,证明其中一定有两个数,它们中的一个是另一个的整数倍。
分析：本题似乎茫无头绪,从何入手？其关键何在？其实就在“两个数”,其中一个是另一个的整数倍。我们要构造“抽屉”,使得每个抽屉里任取两个数,都有一个是另一个的整数倍,这只有把公比是正整数的整个等比数列都放进去同一个抽屉才行,这里用得到一个自然数分类的基本知识：任何一个正整数都可以表示成一个奇数与2的方幂的积,即若m∈N+,K∈N+,n∈N,则m=(2k-1)·2,并且这种表示方式是唯一的,如1=1×2°,2=1×21,3=3×2°,…… 证明：因为任何一个正整数都能表示成一个奇数乘2的方幂,并且这种表示方法是唯一的,所以我们可把1-100的正整数分成如下50个抽屉（因为1-100中共有50个奇数）： （1）{1,1×2,1×22,1×23,1×24,1×25,1×26}； （2）{3,3×2,3×22,3×23,3×24,3×25}； （3）{5,5×2,5×22,5×23,5×24}； （4）{7,7×2,7×22,7×23}； （5）{9,9×2,9×22,9×23}； （6）{11,11×2,11×22,11×23}； ……
（25）{49,49×2}； （26）{51}；
n
…… （50）{99}。
这样,1-100的正整数就无重复,无遗漏地放进这50个抽屉内了。从这100个数中任取51个数,也即从这50个抽屉内任取51个数,根据抽屉原则,其中必定至少有两个数属于同一个抽屉,即属于（1）-（25）号中的某一个抽屉,显然,在这25个抽屉中的任何同一个抽屉内的两个数中,一个是另一个的整数倍。 说明：
（1）从上面的证明中可以看出,本题能够推广到一般情形：从1-2n的自然数中,任意取出n+1个数,则其中必有两个数,它们中的一个是另一个的整数倍。想一想,为什么？因为1-2n中共含1,3,…,2n-1这n个奇数,因此可以制造n个抽屉,而n+1＞n,由抽屉原则,结论就是必然的了。给n以具体值,就可以构造出不同的题目。例2中的n取值是50,还可以编制相反的题目,如：“从前30个自然数中最少要（不看这些数而以任意方式地）取出几个数,才能保证取出的数中能找到两个数,其中较大的数是较小的数的倍数？”
（2）如下两个问题的结论都是否定的（n均为正整数）想一想,为什么？
①从2,3,4,…,2n+1中任取n+1个数,是否必有两个数,它们中的一个是另一个的整数倍？ ②从1,2,3,…,2n+1中任取n+1个数,是否必有两个数,它们中的一个是另一个的整数倍？ 你能举出反例,证明上述两个问题的结论都是否定的吗？
（3）如果将（2）中两个问题中任取的n+1个数增加1个,都改成任取n+2个数,则它们的结论是肯定的还是否定的？你能判断证明吗？
例3．从前25个自然数中任意取出7个数,证明：取出的数中一定有两个数,这两个数中大数不超过小数的1.5倍。
证明：把前25个自然数分成下面6组：
1； ① 2,3； ② 4,5,6； ③ 7,8,9,10； ④ 11,12,13,14,15,16； ⑤ 17,18,19,20,21,22,23, ⑥
因为从前25个自然数中任意取出7个数,所以至少有两个数取自上面第②组到第⑥组中的某同一组,这两个数中大数就不超过小数的1.5倍。 说明：
（1）本题可以改变叙述如下：在前25个自然数中任意取出7个数,求证其中存在两个数,它们相互的比值在
内。
显然,必须找出一种能把前25个自然数分成6（7-1=6）个集合的方法,不过分类时有一个限制条件：同一集合中任两个数的比值在
内,故同一集合中元素的数值差不得过大。这样,
我们可以用如上一种特殊的分类法：递推分类法：
从1开始,显然1只能单独作为1个集合{1}；否则不满足限制条件。 能与2同属于一个集合的数只有3,于是{2,3}为一集合。
如此依次递推下去,使若干个连续的自然数属于同一集合,其中最大的数不超过最小的数的倍,就可以得到满足条件的六个集合。
（2）如果我们按照（1）中的递推方法依次造“抽屉”,则第7个抽屉为 {26,27,28,29,30,31,32,33,34,35,36,37,38,39}； 第8个抽屉为：{40,41,42,…,60}； 第9个抽屉为：{61,62,63,…,90,91}； ……
高中数学竞赛系列讲座：抽屉原理
