第1个回答 2013-03-15
1 抽屉原理
在数学问题中有一类与“存在性”有关的问题，例如：“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）。证明：至少有两个点之间的距离不大于（1978年广东省数学竞赛题）
分析：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）中两个命题中的等边三角形换成正方形，相应的结论中的换成，命
2 抽屉原理
题仍然成立。
（5）读者还可以考虑相反的问题：一般地，“至少需要多少个点，才能够使得边长
为1的正三角形内（包括边界）有两点其距离不超过”。
例2．从1-100的自然数中，任意取出51个数，证明其中一定有两个数，它们中的一个是另一个的整数倍。
分析：本题似乎茫无头绪，从何入手？其关键何在？其实就在“两个数”，其中一个是另一个的整数倍。我们要构造“抽屉”，使得每个抽屉里任取两个数，都有一个是另一个的整数倍，这只有把公比是正整数的整个等比数列都放进去同一个抽屉才行，这里用得到一个自然数分类的基本知识：任何一个正整数都可以表示成一个奇数与2的方幂的积，即若m∈N ,K∈N ，n∈N,则m=(2k-1)·2n，并且这种表示方式是唯一的，如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}；
……
（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个数，求证其中存在两个数，它们相互的比值在内。
3 抽屉原理
显然，必须找出一种能把前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}；
……
那么我们可以将例3改造为如下一系列题目：
（1）从前16个自然数中任取6个自然数；
（2）从前39个自然数中任取8个自然数；
（3）从前60个自然数中任取9个自然数；
（4）从前91个自然数中任取10个自然数；…
都可以得到同一个结论：其中存在2个数，它们相互的比值在]内。
上述第（4）个命题，就是前苏联基辅第49届数学竞赛试题。如果我们改变区间[]（p＞q）端点的值，则又可以构造出一系列的新题目来。
例4．已给一个由10个互不相等的两位十进制正整数组成的集合。求证：这个集合必有两个无公共元素的子集合，各子集合中各数之和相等。（第14届1M0试题）
分析与解答：一个有着10个元素的集合，它共有多少个可能的子集呢？由于在组成一个子集的时候，每一个元素都有被取过来或者不被取过来两种可能，因此，10个元素的集合就有210=1024个不同的构造子集的方法，也就是，它一共有1024个不同的子集，包括空集和全集在内。空集与全集显然不是考虑的对象，所以剩下1024-2=1022个非空真子集。
再来看各个真子集中一切数字之和。用N来记这个和数，很明显：
10≤N≤91 92 93 94 95 96 97 98 99=855
这表明N至多只有855-9=846种不同的情况。由于非空真子集的个数是1022，1022＞846，所以一定存在两个子集A与B，
使得A中各数之和=B中各数之和。
若A∩B=φ，则命题得证，若A∩B=C≠φ，即A与B有公共元素，这时只要剔除A与B中的一切公有元素，得出两个不相交的子集A1与B1，很显然
A1中各元素之和=B1中各元素之和，因此A1与B1就是符合题目要求的子集。
说明：本例能否推广为如下命题：
已给一个由m个互不相等的n位十进制正整数组成的集合。求证：这个集合必有两个无公共元素的子集合，各子集合中各数之和相等。
请读者自己来研究这个问题。
例5．在坐标平面上任取五个整点（该点的横纵坐标都取整数），证明：其中一定存在两个整点，它们的连线中点仍是整点。
分析与解答：由中点坐标公式知，坐标平面两点（x1,y1）、（x2,y2）的中点坐标是。欲使都是整数，必须而且只须x1与x2，y1与y2的奇偶性相同。坐标平面上的任意整点按照横纵两个坐标的奇偶性考虑有且只有如下四种：（奇数、奇数），（偶数，偶数），（奇数，偶数），（偶数，奇数）以此构造四个“抽屉”，则在坐标平面上任取五个整点，那么至少有两个整点，属于同一个“抽屉”因此它们连线的中点就必是整点。
说明：我们可以把整点的概念推广：如果（x1,x2,…xn）是n维（元）有序数组，且x1,x2,…xn中的每一个数都是整数，则称（x1,x2,…xn）是一个n维整点（整点又称格点）。如果对所有的n维整点按每一个xi的奇偶性来分类，由于每一个位置上有奇、偶两种可能性，因此共可分为2×2×…×2=2n个类。这是对n维整点的一种分类方法。当n=3时，23=8，此时可以构造命题：“任意给定空间中九个整点，求证它们之中必有两点存在，使连接这两点的直线段的内部含有整点”。这就是1971年的美国普特南数学竞赛题。在n=2的情形，也可以构造如下的命题：“平面上任意给定5个整点”，对“它们连线段中点为整点”的4个命题中，为真命题的是：
4 抽屉原理
（A）最少可为0个，最多只能是5个 （B）最少可为0个，最多可取10个
（C）最少为1个，最多为5个 （D）最少为1个，最多为10个
（正确答案（D））
例6．在任意给出的100个整数中，都可以找出若干个数来（可以是一个数），它们的和可被100整除。
分析：本题也似乎是茫无头绪，无从下手，其关键何在？仔细审题，它们的“和”能“被100整除”应是做文章的地方。如果把这100个数排成一个数列，用Sm记其前m项的和，则其可构造S1，S2，…S100共100个"和"数。讨论这些“和数”被100除所得的余数。注意到S1，S2，…S100共有100个数，一个数被100除所得的余数有0，1，2，…99共100种可能性。“苹果”数与“抽屉”数一样多，如何排除“故障”？
证明：设已知的整数为a1,a2,…a100考察数列a1,a2,…a100的前n项和构成的数列S1，S2，…S100。
如果S1，S2，…S100中有某个数可被100整除，则命题得证。否则，即S1，S2，…S100均不能被100整除，这样，它们被100除后余数必是{1，2，…，99}中的元素。由抽屉原理I知，S1，S2，…S100中必有两个数，它们被100除后具有相同的余数。不妨设这两个数为Si，Sj（i＜j），则100∣（Sj-Si），即100∣。命题得证。
说明：有时候直接对所给对象作某种划分，是很难构造出恰当的抽屉的。这时候，我们需要对所给对象先作一些变换，然后对变换得到的对象进行分类，就可以构造出恰当的抽屉。本题直接对{an}进行分类是很难奏效的。但由{an}构造出{Sn}后，再对{Sn}进行分类就容易得多。
另外，对{Sn}按模100的剩余类划分时，只能分成100个集合，而{Sn}只有100项，似乎不能应用抽屉原则。但注意到余数为0的类恰使结论成立，于是通过分别情况讨论后，就可去掉余数为0的类，从而转化为100个数分配在剩下的99个类中。这种处理问题的方法应当学会，它会助你从“山穷水尽疑无路”时，走入“柳暗花明又一村”中。
最后，本例的结论及证明可以推广到一般情形（而且有加强的环节）：
在任意给定的n个整数中，都可以找出若干个数来（可以是一个数），它们的和可被n整除，而且，在任意给定的排定顺序的n个整数中，都可以找出若干个连续的项（可以是一项），它们的和可被n整除。
将以上一般结论中的n赋以相应的年份的值如1999，2000，2001…，就可以编出相应年份的试题来。如果再赋以特殊背景，则可以编出非常有趣的数学智力题来，如下题：
有100只猴子在吃花生，每只猴子至少吃了1粒花生，多者不限。请你证明：一定有若干只猴子（可以是一只），它们所吃的花生的粒数总和恰好是100的倍数。
（二）于无声处听惊雷--单色三角形问题
前面数例我们看到，抽屉原理的应用多么奇妙，其关键在于恰当地制造抽屉，分割图形，利用自然数分类的不同方法如按剩余类制造抽屉或按奇数乘以2的方幂制造抽屉，利用奇偶性等等，都是制造“抽屉”的方法。大家看到，抽屉原理的道理极其简单，但“于无声处听惊雷”，恰当地精心地应用它，不仅可以解决国内数学竞赛中的问题，而且可以解决国际中学生数学竞赛，例如IM0中的难题。本节我们就来看几个这样的例子。
例7．（第6届国际中学生数学奥林匹克试题）17名科学家中每两名科学家都和其他科学家通信，在他们通信时，只讨论三个题目，而且任意两名科学家通信时只讨论一个题目，证明：其中至少有三名科学家，他们相互通信时讨论的是同一个题目。
证明：视17个科学家为17个点，每两个点之间连一条线表示这两个科学家在讨论同一个问题，若讨论第一个问题则在相应两点连红线，若讨论第2个问题则在相应两点连条黄线，若讨论第3个问题则在相应两点连条蓝线。三名科学家研究同一个问题就转化为找到一个三边同颜色的三角形。
考虑科学家A，他要与另外的16位科学家每人通信讨论一个问题，相应于从A出发引出16条线段，将它们染成3种颜色，而16=3×5 1，因而必有6=5 1条同色，不妨记为AB1，AB2，AB3，AB4，AB5，AB6同红色，若Bi（i=1，2，…，6）之间有红线，则出现红色三角线，命题已成立；否则B1，B2，B3，B4，B5，B6之间的连线只染有黄蓝两色。
5 抽屉原理
考虑从B1引出的5条线，B1B2，B1B3，B1B4，B1B5，B1B6，用两种颜色染色，因为5=2×2 1，故必有3=2 1条线段同色，假设为黄色，并记它们为B1B2，B1B3，B1B4。这时若B2，B3，B4之间有黄线，则有黄色三角形，命题也成立，若B2，B3，B4，之间无黄线，则△B2，B3，B4，必为蓝色三角形，命题仍然成立。
说明：（1）本题源于一个古典问题--世界上任意6个人中必有3人互相认识，或互相不认识。（美国普特南数学竞赛题）。
（2）将互相认识用红色表示，将互相不认识用蓝色表示，（1）将化为一个染色问题，成为一个图论问题：空间六个点，任何三点不共线，四点不共面，每两点之间连线都涂上红色或蓝色。求证：存在三点，它们所成的三角形三边同色。
（3）问题（2）可以往两个方向推广：其一是颜色的种数，其二是点数。
本例便是方向一的进展，其证明已知上述。如果继续沿此方向前进，可有下题：
在66个科学家中，每个科学家都和其他科学家通信，在他们的通信中仅仅讨论四个题目，而任何两个科学家之间仅仅讨论一个题目。证明至少有三个科学家，他们互相之间讨论同一个题目。
（4）回顾上面证明过程，对于17点染3色问题可归结为6点染2色问题，又可归结为3点染一色问题。反过来，我们可以继续推广。从以上（3，1）→（6，2）→（17，3）的过程，易发现
6=（3-1）×2 2，17=（6-1）×3 2，66=（17-1）×4 2，
同理可得（66-1）×5 2=327，（327-1）×6 2=1958…记为r1=3，r2=6，r3=17，r4=66，r5=327，r6=1958，…
我们可以得到递推关系式：rn=n(rn-1-1) 2，n=2,3,4…这样就可以构造出327点染5色问题，1958点染6色问题，都必出现一个同色三角形。
（三）抽屉原理的其他形式。
在例7的证明过程中，我们实际上用到了抽屉原理的其他形式，我们把它作为定理2。
定理2：把m个元素分成n个集合（m＞n）
（1）当n能整除m时，至少有一个集合含有个元素；
（2）当n不能整除 m时，则至少有一个集合含有至少[] 1个元素，（[]表示不超过 的最大整数）
定理2有时候也可叙述成：把m×n 1个元素放进n个集合，则必有一个集合中至少放有m 1个元素。
例8．在边长为1的正方形内任意放入九个点，求证：存在三个点，以这三个点为顶点的三角形的面积不超过（1963年北京市数学竞赛题）。
分析与解答：如图3，四等分正方形，得到A1，A2，A3，A4四个矩形。在正方形内任意放入九个点，则至少有一个矩形Ai内存在[] 1=3个或3个以上的点，设三点为A、B、C，具体考察Ai（如图4），过A、B、C三点分别作矩形长边的平行线，过A点的平行线交BC于A'点，A点到矩形长边的距离为h=(0≤h≤)，则△ABC的面积
S△ABC=S△AA'C S△AA'B
≤×1×h ×1×（-h）
=×=
说明：把正方形分成四个区域，可以得出“至少有一个区域内有3个点”的结论，这就为确定三角形面积的取值范围打下了基础。本题构造“抽屉”的办法不是唯一的，还可以将正方形等分成边长为的四个小正方形等。但是如将正方形等分成四个全等的小三角形却是不可行的（想一想为什么？）。所以适当地构造“抽屉”，正是应用抽屉原则解决问题的关键所在。
图5
以下两个题目可以看作是本例的平凡拓广：
（1）在边长为2的正方形内，随意放置9个点，证明：必有3个点，以它们为顶点的三角形的面积不超过。
（2）在边长为1的正方形内任意给出13个点。求证：必有4个点，以它们为顶点的四边形的面积不超过1/4。
例9．9条直线的每一条都把一个正方形分成两个梯形，而且它们的面积之比为2∶3。证明：这9条直线中至少有3条通过同一个点。
证明：设正方形为ABCD，E、F分别是AB，CD的中点。
6 抽屉原理
设直线L把正方形ABCD分成两个梯形ABGH和CDHG，并且与EF相交于P（如图6）
梯形ABGH的面积：梯形CDHG的面积=2∶3
EP是梯形ABGH的中位线，PF是梯形CDHG的中位线，由于
梯形的面积=中位线×梯形的高，并且两个梯形的高相等（AB=CD），所以
梯形ABGH的面积∶梯形CDHG的面积
=EP∶PF，也就是EP∶PF=2∶3
这说明，直线L通过EF上一个固定的点P，这个点把EF分成长度为2∶3的两部分。这样的点在EF上还有一个，如图上的Q点（FQ∶QE=2∶3）。
同样地，如果直线L与AB、CD相交，并且把正方形分成两个梯形面积之比是2∶3，那么这条直线必定通过AD、BC中点连线上的两个类似的点（三等分点）。
这样，在正方形内就有4个固定的点，凡是把正方形面积分成两个面积为2∶3的梯形的直线，一定通过这4点中的某一个。我们把这4个点看作4个抽屉，9条直线看作9个苹果，由定理2可知，
9=4×2 1，
所以，必有一个抽屉内至少放有3个苹果，也就是，必有三条直线要通过一个点。
说明：本例中的抽屉比较隐蔽，正方形两双对边中点连线上的4个三等分点的发现是关键，而它的发现源于对梯形面积公式S梯形=中位线×梯形的高的充分感悟。
例10．910瓶红、蓝墨水，排成130行，每行7瓶。证明：不论怎样排列，红、蓝墨水瓶的颜色次序必定出现下述两种情况之一种：
1．至少三行完全相同；
2．至少有两组（四行），每组的两行完全相同。（北京市高中一年级数学竞赛1990年复赛试题）