浅谈抽屉原理在高中数学竞赛中的运用

1、浅谈抽屉原理在高中数学竞赛中的运用在数学问题中有一类与“存在性”有关的问题，例如：“13个人屮至少有两个人出生 在相同月份”；"某校400名学生中，一定存在两名学牛，他们在同一天过生日” ；"2003 个人任意分成200个小组，一定存在一组，其成员数不少于11”； “把0, 1内的全部有 理数放到100个集合中，一定存在一个集合，它里面有无限多个冇理数”。这类存在性问题 中，“存在”的含义是“至少有一个”。在解决这类问题时，只要求指明存在，一般并不需 要指出哪一个，也不需要确定通过什么方式把这个存在的东西找出來。这类问题相对來说涉 及到的运算较少，依据的理论也不复朵，我们把

2、这些理论称之为“抽屉原理” “抽屉原理”最先是由19世纪的德国数学家辿里赫莱（dirichlet）运用于解决数学问 题的，所以又称“迪里赫莱原理”，也冇称“鸽巢原理”的。这个原理可以简单地叙述为“把 10个苹果，任意分放在9个抽屉里，则至少有一个抽屉里含有两个或两个以上的苹果”。 这个道理是非常明显的，但应用它却可以解决许多有趣的问题，并且常常得到一些令人惊异 的结果。捕屉原理是国际国内各级各类数学竞赛中的重要内容，本讲就来学习它的有关知识 及其应用。一、抽屉原理的基本形式定理1、如果把*1个元素分成n个集合，那么不管怎么分，都存在一个集合，其中至 少有两个元素。例1.已知在边长为1的等边三角

3、形内（包括边界）有任意五个点（如图）。证明：至少有两个点之间的距离不大于丄（1978年广东省数学竞赛题）2分析：5个点的分布是任意的。如果要证明“在边长为1的等 边三角形内（包括边界）有5个点，那么这5个点中一定有距离 不大于丄的两点”，则顺次连接三角形三边中点，即三角形的三2条屮位线，可以分原等边三用形为4个全等的边长为丄2 的小等边三角形，则5个点中必有2点位于同一个小等 边三角形中（包括边界），其距离便不大于丄。2以上结论要由定理'三角形內（包括边界）任意两点间的距离不大于其最大边长”来保 证，下面我们就來证明这个定理。如图，设bc是aabc的最大边，p, m是aabc内（包括边

4、界）任意两点，连接pm,过p分别作ab、bc边的平行线，过m作ac边的平行线，设各平行线交点为p、q、n,那么zpq2zc, zqnp=za因为 bc2ab,所以zazc,则zqnpzpqn,而zqmpzqnpzpqn （三角形的外 角大于不相邻的内角）,所以pqmpm。显然bcnpq,故bcmpm。山此我们可以推知，边长为丄的等边三角形内（包括边界）两点间的距离不人于丄。2 2说明：（1）这里是用等分三角形的方法来构造“抽屉”。类似地，还可以利用等分线段、 等分正方形的方法來构造“抽屉”。例如“任取n+1个正数ai,满足0v&w1 （i=l,2,n+1）,试证明：这n+1个数屮必存在

5、两个数，其差的绝对值小于丄”。乂如：n“在边长为1的正方形内任意放置五个点，求证：其屮必有两点，这两点之间的距离不人于 返o2（2）例1中，如果把条件（包括边界）去掉，则结论可以修改为：至少有两个点z间 的距离小于丄，大家可以口己证明，并比较证明的差别。2（3）用同样的方法可证明以下结论：i）在边长为1的等边三角形中有+1个点，这r?+l个点中一定有距离不大于丄的两点。nii）在边长为1的等边三角形内有+1个点，这+1个点中一定有距离小于丄的两点。nfi（4）将（3）中两个命题中的等边三角形换成正方形，相应的结论中的一换成 ,nn命题仍然成立。（5）我们还可以考虑相反的问题：-般地，至少需要多

6、少个点，才能够使得边长为1 的正三角形内（包括边界）有两点其距离不超过丄。n例2.从1-100的白然数中，任意取出51个数，证明其屮一定有两个数，它们屮的一 个是另一个的整数倍。分析：本题似乎茫无头绪，从何入手？其关键何在？其实就在“两个数”，其中一个是 另一个的整数倍。我们要构造“抽屉”，使得每个抽屉里任取两个数，都有一个是另一个的 整数倍，这只有把公比是正整数的整个等比数列都放进去同一个抽屉才行，这里用得到一个 h然数分类的基本知识：任何一个正整数都可以表示成一个奇数与2的方幕的积，即若 mgnkgn*, nen,则m二（2k-1）2",并且这种表示方式是唯一的,如1=1x2&#

7、176; , 2=1 x21,3=3x2° ,证明：因为任何一个正整数都能表示成一个奇数乘2的方幕，并几这种表示方法是唯一的,所以我们可把1-100的正整数分成如下50个抽屉（因为1-100中共冇50个奇数）：(1)1，1x2,1x22,1x23,1x24,1x25, 1x2,(2)3,3x2,3x22,3x2',3x21,3x25；(3)5,5x2,5x22,5x2',5x2'(4)7,7x2,7x22,7x2'(5)9,9x2,9x2",9 x 23*(6) 11, 11 x2, 11x22, 11x23；(25) 49, 49x2；(2

8、6) 51；（50） 99 o这样，1-100的正整数就无重复，无遗漏地放进这50个抽屉内了。从这100个数中任 取51个数，也即从这50个抽屉内任取51个数，根据抽屉原则，其中必定至少有两个数属 于同一个抽屉，即属于（1） - （25）号屮的某一个抽屉，显然，在这25个抽屉中的任何同 一个抽屉内的两个数中，一个是另一个的整数倍。说明：（1）从上面的证明小可以看出，本题能够推广到一般情形：从l-2n的占然数中, 任意取出n+1个数，则其中必有两个数，它们中的一个是另一个的整数倍。想一想，为什么？ 因为1-2口中共含1, 3,，2n-l这n个奇数，因此可以制造n个抽屉,而n+l>n,由抽

9、屉原则，结论就是必然的了。给n以具体值，就可以构造出不同的题冃。例2中的n取值是 50,还可以编制相反的题目，如：“从前30个h然数中最少要（不看这些数而以任意方式 地）取出儿个数，才能保证取出的数屮能找到两个数，其屮较大的数是较小的数的倍数？ ”（2）如下两个问题的结论都是否定的（n均为正整数）想一想，为什么？ 从2, 3, 4,，2n+l中任取n+1个数，是否必有两个数，它们中的一个是另一个的 整数倍？ 从1, 2, 3,，2n+l中任取n+1个数,是否必有两个数,它们中的一个是另一个的 整数倍？你能举出反例，证切上述两个问题的结论都是否定的吗？(3) 如果将(2)中两个问题中任取的n+1

10、个数增加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_在两个数，它们相互

11、的比值在内。_3 2_显然，必须找出一种能把前25个自然数分成6 (7-1=6)个集合的方法，不过分类时有'2 3'一个限制条件：同一集合中任两个数的比值在一,二内，故同一集合中元素的数值差不得 1_3 2过大。这样，我们可以用如上-种特殊的分类法：递推分类法：从1开始，显然1只能单独作为1个集合1；否则不满足限制条件。能与2同属于一个集合的数只有3,于是2, 3为一集合。如此依次递推下去，使若干个连续的白然数属于同一集合，其屮最人的数不超过最小的3数的？倍，就可以得到满足条件的六个集合。2(2) 如果我们按照(1)中的递推方法依次造“抽屉”，则第7个抽屉为(26, 27, 2

12、8, 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个h然数中任取10个白然数；_2 3'都可以得到同一个结论：其中存在2个数，它们相互的比值在一,二内。_3 2_上述第（4）个命题，就是前苏联基辅第49届数学竞赛试题。如果我们改变区间 生上 _p q.（p>q）端点的值

13、，则乂可以构造出一系列的新题目来。例4已给一个由10个互不相等的两位十进制正整数组成的集合。求证：这个集合必 冇两个无公共元素的了集合，使了集合中各数z和相等。（笫14届1m0试题）分析与解答：一个冇着10个元素的集合共有2,0=1024个不同的子集，包括空集和全集 在内。空集与全集显然不是考虑的对象，所以剩下1024-2二1022个非空真子集。再来看各个真子集中一切数字之和。用n来记这个和数，很切显：10wnw91+92+93+94+95+96+97+98+99二 855这表明n至多只冇855-9=846种不同的情况。由于非空真了集的个数是1022, 1022> 846,所以一定存在两

14、个子集a与b,使得a中各数之和二b中各数之和。若ac1b二"，则命题得证，若aqb=ch",即a与b有公共元索，这时只要剔除a与b 中的一切公有元素，得出两个不相交的子集加与很显然，血中各元素之和二中各元素 z和，因此a.lj-b.就是符合题冃要求的子集。思考：本例能否推广为如下命题：已给一个由m个互不相等的n位十进制正整数组成的集合。求证：这个集合必有两个无 公共元素的子集合，各子集合小各数之和相等。例5在处标平而上任収五个整点（该点的横纵处标都収整数），证明：其中一定存在 两个整点，它们的连线中点仍是整点。/ 分析：由中点处标公式，处标平面两点（西，1）,（兀2，丁2

15、）的中点绝标 人+ " , '。、2 2 丿欲使匕鱼都是整数，必须而且只须心与x2,刃与y2的奇偶性相同。坐标平面上2 2的任意整点按照横纵两个处标的奇偶性考虑有且只有如下四种：（奇数、奇数），（偶数, 偶数），（奇数，偶数），（偶数，奇数）以此构造四个“抽屉”，则在坐标平面上任取五 个整点，那么至少有两个整点，属于同一个“抽屉”因此它们连线的中点就必是整点。说明：我们可以把整点的概念推广：如果（xi, x2,xn）是n维（元）有序数组，且x, x2,xn 中的每一个数都是整数，则称（xi,x2,xj是一个n维整点。如果对所有的n维整点按每 一个xi的奇偶性来分类，由于每一个

16、位置上有奇、偶两种可能性，因此共可分为 2x2xx2二t个类。这是对n维整点的一种分类方法。当沪3时,2=8,此时可以构造命 题：“任意给定空间中九个整点，求证它们之中必有两点存在，使连接这两点的肓线段的内 部含有整点”。这就是1971年的美国普特南数学竞赛题。在n=2的情形，也可以构造如下 的命题：“平而上任意给定5个整点”，对"它们连线段中点为整点”的4个命题中，为真 命题的是：（a）授少可为0个，最多只能是5个；（b）最少可为0个，授多町取10个（c）最少为1个，最多为5个；（d）最少为1个，最多为10个 答案（d）例6.在任意给出的100个整数中，都可以找出若干个数來（可以是

17、一个数），它们的和 可被100整除。分析：本题也似乎是茫无头绪，无从下手，其关键何在？仔细审题，它们的“和”能“被 100整除”应是做文章的地方。如果把这100个数排成一个数列，用sj己其前m项的和，则 其可构造,，s2,£。°共100个和数。讨论这些“和数”被100除所得的余数。注意到5., s2,s】o。共有100个数,一个数被100除所得的余数有0, 1, 2,99共100种可能性。“苹果”数与“抽屉”数一样多，如何排除“故障” ？证明：设已知的整数为ab a2, -aioo考察数列ab a2, -aioo的前n项和构成的数列si,s2, *s100o如果s|, s2

18、, -s.00屮有某个数可被100整除，则命题得证。否则，即si, s2,弘均 不能被100整除，这样，它们被100除后余数必是1, 2,，99小的元索。由抽屉原理i 知，s）, s2,血中必有两个数，它们被100除后具有相同的余数。不妨设这两个数为si,5. （i<j）,则100 i （sj-si）,即100丨（勺+|+4+2+勺）。命题得证。说明：有时候直接对所给对象作某种划分，是很难构造出恰当的抽屉的。这时候，我们 需要对所给对象先作一些变换,然后对变换得到的对象进行分类，就可以构造出恰当的抽屉。 木题总接对缶进行分类是很难奏效的。但由%构造出sn后，再对sn进行分类就容易得 多。

19、另外，对sn按模100的剩余类划分时，只能分成100个集合，而0只有100项，似 乎不能应用抽屉原则。但注意到余数为0的类恰使结论成立，于是通过分别情况讨论后，就 可去掉余数为0的类，从而转化为100个数分配在剩下的99个类中。最后，本例的结论及证明町以推广到一般情形（而一口有加强的环节）：在任意给定的n个整数中，都口j以找出若干个数來（可以是一个数），它们的和可被n 整除，而且，在任意给定的排定顺序的n个幣数屮，都可以找出若干个连续的项（可以是一 项），它们的和可被n整除。将以上一般结论中的n赋以相应的年份的值如1999, 2000, 2001-,就可以编出相应 年份的试题来。如果再赋以特殊

20、背景，则可以编出非常有趣的数学智力题来，如下题：有100只猴了在吃花生，每只猴了至少吃了 1粒花生，多者不限。请你证明：一定冇若 干只猴子（可以是一只），它们所吃的花生的粒数总和恰好是100的倍数。二、单色三角形问题丽而数例我们看到，抽屉原理应用的关键在于恰当地制造抽屉，分割图形，利用自然数 分类的不同方法如按剩余类制造抽屉或按奇数乘以2的方幕制造抽屉，利用奇偶性等等，都 是制造“抽屉”的方法。大家看到，抽屉原理的道理极英简单，但恰当地精心地应用它，不 仅可以解决国内数学竞赛屮的问题，而且可以解决国际中学生数学竞赛，例如tm0屮的难题。例7.（第6届国际小学生数学奥林匹克试题）17名科学家小每

21、两名科学家都和其他科 学家通信，在他们通信吋，只讨论三个题目，而且任意两名科学家通倍吋只讨论一个题目， 证明：其中至少有三名科学家，他们相互通信时讨论的是同一个题h。证明：视17个科学家为17个点，每两个点z间连一条线表示这两个科学家在讨论同一 个问题，若讨论第一个问题则在相应两点连红线，若讨论第2个问题则在相应两点连条黄线, 若讨论第3个问题则在相应两点连条蓝线。三名科学家研究同一个问题就转化为找到一个三 边同颜色的三角形。（木例同第十二讲染色问题例4）考虑科学家a,他要与另外的16位科学家每人通信讨论一个问题，相应于从a出发引 出16条线段,将它们染成3种颜色，而16=3x5+1,因而必有

22、6=5+1条同色，不妨记为ab】, abz, ab3, ab., ab：, abe同红色,若bi （i=l, 2,，6）之间有红线,则出现红色三角线, 命题已成立；否则bi, b2, b；i, b. b5,间的连线只染有黄蓝两色。考虑从bi引出的5条线,bib2, b1b3, bibi, b1b5, bib6,用两种颜色染色,因为5二2x2+1, 故必有3=2+1条线段同色,假设为黄色,并记它们为bib2, b.b3, b1b10这时若b2, b3, b,z 间有黄线,则有黄色三角形,命题也成立,若b3, bn之间无黄线,则b?, b3, b4,必 为蓝色三角形，命题仍然成立。说明：(1)本题

23、源于一个古典问题一世界上任意6个人中必有3人互相认识，或互相 不认识。(美国普特南数学竞赛题)。(2) 将互相认识用红色表示，将互相不认识用蓝色表示，(1)将化为一个染色问题, 成为一个图论问题：空间六个点，任何三点不共线，四点不共面，每两点之间连线都涂上红 色或蓝色。求证：存在三点，它们所成的三角形三边同色。(3) 问题(2)可以往两个方向推广：其一是颜色的种数，其二是点数。木例便是方向一的进展，其证明已知上述。如果继续沿此方向前进，可有下题：在66个科学家中，每个科学家都和其他科学家通信，在他们的通信中仅仅讨论四个题 目，而任何两个科学家之间仅仅讨论一个题1=1。证明至少冇三个科学家，他们

24、互相之间讨论 同一个题目。(4) 回顾上而证明过程，对于17点染3色问题可归结为6点染2色问题，乂可归结为 3点染一色问题。反过来，我们可以继续推广。从以上(3, 1) - (6, 2) - (17, 3)的 过程，易发现6= (3-1) x2+2, 17= (6-1) x3+2, 66二(17-1) x4+2,同理可得(66-1) x 5+2=327,(327-1) x6+2=1958记为 r)=3, r2=6, n=17, n=66,“=327, r6=1958,我们可以得到递推关系式:心(“厂1)+2, n=2, 3, 4这样就可以构造出327点染5色 问题，1958点染6色问题，都必出

25、现一个同色三角形。三、抽屉原理的其他形式在例7的证明过程中，我们实际上用到了抽屉原理的其他形式，我们把它作为定理2。定理2：把m个元素分成n个集合(m>n)iri(1) 当n能整除m吋，至少有一个集合含有一个元素；n(2) 为n不能整除m时，则至少有一个集合含有至少中+ 1个元素。定理2有吋候也可叙述成：把mxn+1个元素放进n个集合，则必有一个集合中至少放 有m+1个元素。例8.在边长为1的正方形内任意放入九个点，求证：存在三个点，以这三个点为顶点 的三角形的面积不超过丄（1963年北京市数学竞赛题）。8分析与解答：如图，四等分正方形,得到ah a2, a3, a（四个矩形。在止方形内

26、任意放1/4入九个点，则至少有一个矩形ai内存 在k1 + 1 = 3个或3个以上的点，设 三点为a、b、c,具体考察ai （如图所示），过a、b、c三点分别作矩形长边的平行线，过a点的平行线交bc于a'点，a点到矩形长边的距离为h=gh冷，则/的面积saabc=saaa，c+saaab< xlx/?+ xlx2 2111=x=248说明：把正方形分成四个区域，可以得出“至少有一个区域内有3个点”的结论，这就 为确定三角形面积的取值范围打下了基础。本题构造“抽屉”的办法不是唯一的，还可以将 正方形等分成边长为丄的四个小正方形等。但是如将正方形等分成四个全等的小三角形却2是不可行的

27、（想一想为什么？）。所以适当地构造“抽屉”，正是应用抽屉原则解决问题的 关键所在。以下两个题目可以看作是本例的推广：（1）在边长为2的正方形内，随意放置9个点，证明：必有3个点，以它们为顶点的 三角形的而积不超过丄。2（2）在边长为1的正方形内任意给出13个点。求证：必有4个点，以它们为顶点的四边形的而积不超过1/4o例99条岂线的每一条都把一个正方形分成两个梯形，而且它们的而积之比为2： 3。证明：这9条肓线屮至少有3条通过同一个点。证明：设正方形为abcd, e、f分别是ab, cd的中点。设肓线l把正方形abcd分成两个梯形abgh和cdhg, 并且与ef相交于p （如图6）据题意梯形a

28、bgh的面积：梯形 cdhg的而积二2 ： 3 , ep是梯形abgh的中位线，pf是梯形 cdhg的中位线，由于梯形的而积二中位线x梯形的高，并几两个梯形的高相等（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相交，并口把正方形分成两个梯形面积z比是2 : 3,那 么这条直线必定通过ad、bc中点连线上的两个类似的点（三等分点）。这样，在正方形内就有4

29、个固定的点，凡是把正方形面积分成两个面积为2 : 3的梯形 的直线，一定通过这4点屮的某一个。我们把这4个点看作4个抽屉，9条直线看作9个苹 果，山定理2可知，9=4x2+1,所以，必有一个抽屉内至少放有3个苹果，也就是，必有三条直线要通过一个点。说明：本例中的抽屉比较隐蔽，正方形两双対边中点连线上的4个三等分点的发现是关 键，而它的发现源于对梯形而积公式s梯形二屮位线x梯形的高的充分感悟。例10. 910瓶红、蓝墨水，排成130行，每行7瓶。证明：不论怎样排列，红、蓝墨水 瓶的颜色次序必定出现下述两种情况z种：1. 至少三行完全相同；2. 至少有两组（四行），每组的两行完全相同。（北京市高中

30、一年级数学竞赛1990 年复赛试题）证明：910瓶红、蓝黑水，排成130行，每行7瓶。每行中的7个位置中的每个位置都 冇红、蓝两种町能，因而总计共冇2'128种不同的行式（当仅当两行墨水瓶颜色及次序 完全相同时称为“行式”相同）任取130行中的129行,依抽屉原理可知,必有两行（记为a, b） “行式”相同。在除a、b外的其余128行中若有一行p与a （b） “行式”相同,则p, a, b满足“至 少有三行完全相同”；在其余（除a, b外）的128行中若没有与a （b）行式和同者，则128 行至多冇127种不同的行式，依抽屉原则，必有两行（不妨记为c、d）行式相同，这样便 找到了（a,

31、 b）、（c, d）两组（四行），每组两行完全相同。说明：本例构造抽屉时用到了乘法原理,2x2x2x2x2x2x2=2=128个“行式”是制 造和应用抽屉原理的关键。四、抽屉原理的无限形式定理3.如果把无穷多个元素分成n个集合，那么不管怎么分，都至少存在一个集合， 其小有无穷多个元素。例11.在处标平而上给岀无限多个矩形，它们的顶点的直角他标都具有如下形式：（0, 0） ,（0, m ） ,（n, 0） ,（n, m）其中m, n是正整数，并n<6,求证：在这些矩形中一定存在无限多个矩形， 其中任意两个矩形必有一个被包含在另一个之中。证明：由n<6知，21,2,3,4,5,只有5种情形，由定理3知，将所给的无穷多个矩形 按n的取值分成5类，当作5个抽屉，其中必有一个抽屉（一类）里包含有无穷多个矩形。 不妨设这一类矩形的n的取值为n。对于这一类矩形中的任意两个矩形而言，由于n的取值 相同，因此m取值较小的一个矩形必然被包含在m取值较大的一个矩形z中。五、抽屉原理的多次使用例12.有苹果、梨、桔子若干个，任意分成9堆，求证一定可以找到两堆，其苹果数、 梨数、桔子数分别求和都是偶数。证明：因为每一堆里的每一种水杲数或为奇数或为偶数（两个抽屉），而9二2x4+1, 故对于苹果，9堆中必冇5堆的奇偶性相同；这5