高中數(shù)學(xué)競(jìng)賽講義抽屜原理

1、23抽屜原理在數(shù)學(xué)問(wèn)題中有一類(lèi)與“存在性”有關(guān)的問(wèn)題，例如：“13個(gè)人中至少有兩個(gè)人出生在相同月份”；“某校400名學(xué)生中，一定存在兩名學(xué)生，他們?cè)谕惶爝^(guò)生日”；“2003個(gè)人任意分成200個(gè)小組，一定存在一組，其成員數(shù)不少于11”；“把0，1內(nèi)的全部有理數(shù)放到100個(gè)集合中，一定存在一個(gè)集合，它里面有無(wú)限多個(gè)有理數(shù)”。這類(lèi)存在性問(wèn)題中，“存在”的含義是“至少有一個(gè)”。在解決這類(lèi)問(wèn)題時(shí)，只要求指明存在，一般并不需要指出哪一個(gè)，也不需要確定通過(guò)什么方式把這個(gè)存在的東西找出來(lái)。這類(lèi)問(wèn)題相對(duì)來(lái)說(shuō)涉及到的運(yùn)算較少，依據(jù)的理論也不復(fù)雜，我們把這些理論稱(chēng)之為“抽屜原理”。“抽屜原理”最先是由19世紀(jì)的德

2、國(guó)數(shù)學(xué)家迪里赫萊（Dirichlet）運(yùn)用于解決數(shù)學(xué)問(wèn)題的，所以又稱(chēng)“迪里赫萊原理”，也有稱(chēng)“鴿巢原理”的。這個(gè)原理可以簡(jiǎn)單地?cái)⑹鰹椤鞍?0個(gè)蘋(píng)果，任意分放在9個(gè)抽屜里，則至少有一個(gè)抽屜里含有兩個(gè)或兩個(gè)以上的蘋(píng)果”。這個(gè)道理是非常明顯的，但應(yīng)用它卻可以解決許多有趣的問(wèn)題，并且常常得到一些令人驚異的結(jié)果。抽屜原理是國(guó)際國(guó)內(nèi)各級(jí)各類(lèi)數(shù)學(xué)競(jìng)賽中的重要內(nèi)容，本講就來(lái)學(xué)習(xí)它的有關(guān)知識(shí)及其應(yīng)用。（一）抽屜原理的基本形式定理1、如果把n+1個(gè)元素分成n個(gè)集合，那么不管怎么分，都存在一個(gè)集合，其中至少有兩個(gè)元素。證明：（用反證法）若不存在至少有兩個(gè)元素的集合，則每個(gè)集合至多1個(gè)元素，從而n個(gè)集合至多有n個(gè)元素

3、，此與共有n+1個(gè)元素矛盾，故命題成立。在定理1的敘述中，可以把“元素”改為“物件”，把“集合”改成“抽屜”，抽屜原理正是由此得名。同樣，可以把“元素”改成“鴿子”，把“分成n個(gè)集合”改成“飛進(jìn)n個(gè)鴿籠中”?！傍澔\原理”由此得名。例題講解1已知在邊長(zhǎng)為1的等邊三角形內(nèi)（包括邊界）有任意五個(gè)點(diǎn)（圖1）。證明：至少有兩個(gè)點(diǎn)之間的距離不大于2從1-100的自然數(shù)中，任意取出51個(gè)數(shù)，證明其中一定有兩個(gè)數(shù)，它們中的一個(gè)是另一個(gè)的整數(shù)倍。3從前25個(gè)自然數(shù)中任意取出7個(gè)數(shù)，證明：取出的數(shù)中一定有兩個(gè)數(shù)，這兩個(gè)數(shù)中大數(shù)不超過(guò)小數(shù)的1.5倍。4已給一個(gè)由10個(gè)互不相等的兩位十進(jìn)制正整數(shù)組成的集合。求證：這個(gè)

4、集合必有兩個(gè)無(wú)公共元素的子集合，各子集合中各數(shù)之和相等。5在坐標(biāo)平面上任取五個(gè)整點(diǎn)（該點(diǎn)的橫縱坐標(biāo)都取整數(shù)），證明：其中一定存在兩個(gè)整點(diǎn)，它們的連線中點(diǎn)仍是整點(diǎn)。6在任意給出的100個(gè)整數(shù)中，都可以找出若干個(gè)數(shù)來(lái)（可以是一個(gè)數(shù)），它們的和可被100整除。717名科學(xué)家中每?jī)擅茖W(xué)家都和其他科學(xué)家通信，在他們通信時(shí)，只討論三個(gè)題目，而且任意兩名科學(xué)家通信時(shí)只討論一個(gè)題目，證明：其中至少有三名科學(xué)家，他們相互通信時(shí)討論的是同一個(gè)題目。例題答案：1分析：5個(gè)點(diǎn)的分布是任意的。如果要證明“在邊長(zhǎng)為1的等邊三角形內(nèi)（包括邊界）有5個(gè)點(diǎn)，那么這5個(gè)點(diǎn)中一定有距離不大于的兩點(diǎn)”，則順次連接三角形三邊中點(diǎn)，即

5、三角形的三條中位線，可以分原等邊三角形為4個(gè)全等的邊長(zhǎng)為的小等邊三角形，則5個(gè)點(diǎn)中必有2點(diǎn)位于同一個(gè)小等邊三角形中（包括邊界），其距離便不大于。以上結(jié)論要由定理“三角形內(nèi)（包括邊界）任意兩點(diǎn)間的距離不大于其最大邊長(zhǎng)”來(lái)保證，下面我們就來(lái)證明這個(gè)定理。如圖2，設(shè)BC是ABC的最大邊，P，M是ABC內(nèi)（包括邊界）任意兩點(diǎn)，連接PM，過(guò)P分別作AB、BC邊的平行線，過(guò)M作AC邊的平行線，設(shè)各平行線交點(diǎn)為P、Q、N，那么PQN=C，QNP=A因?yàn)锽CAB，所以AC，則QNPPQN，而QMPQNPPQN（三角形的外角大于不相鄰的內(nèi)角），所以PQPM。顯然BCPQ，故BCPM。由此我們可以推知，邊長(zhǎng)為的等

6、邊三角形內(nèi)（包括邊界）兩點(diǎn)間的距離不大于。說(shuō)明：（1）這里是用等分三角形的方法來(lái)構(gòu)造“抽屜”。類(lèi)似地，還可以利用等分線段、等分正方形的方法來(lái)構(gòu)造“抽屜”。例如“任取n+1個(gè)正數(shù)ai，滿足0ai1（i=1,2,n+1），試證明：這n+1個(gè)數(shù)中必存在兩個(gè)數(shù)，其差的絕對(duì)值小于”。又如：“在邊長(zhǎng)為1的正方形內(nèi)任意放置五個(gè)點(diǎn)，求證：其中必有兩點(diǎn)，這兩點(diǎn)之間的距離不大于。（2）例1中，如果把條件（包括邊界）去掉，則結(jié)論可以修改為：至少有兩個(gè)點(diǎn)之間的距離小于，請(qǐng)讀者試證之，并比較證明的差別。（3）用同樣的方法可證明以下結(jié)論：i）在邊長(zhǎng)為1的等邊三角形中有n2+1個(gè)點(diǎn)，這n2+1個(gè)點(diǎn)中一定有距離不大于的兩點(diǎn)。

7、ii）在邊長(zhǎng)為1的等邊三角形內(nèi)有n2+1個(gè)點(diǎn)，這n2+1個(gè)點(diǎn)中一定有距離小于的兩點(diǎn)。（4）將（3）中兩個(gè)命題中的等邊三角形換成正方形，相應(yīng)的結(jié)論中的換成，命題仍然成立。（5）讀者還可以考慮相反的問(wèn)題：一般地，“至少需要多少個(gè)點(diǎn)，才能夠使得邊長(zhǎng)為1的正三角形內(nèi)（包括邊界）有兩點(diǎn)其距離不超過(guò)”。2分析：本題似乎茫無(wú)頭緒，從何入手？其關(guān)鍵何在？其實(shí)就在“兩個(gè)數(shù)”，其中一個(gè)是另一個(gè)的整數(shù)倍。我們要構(gòu)造“抽屜”，使得每個(gè)抽屜里任取兩個(gè)數(shù)，都有一個(gè)是另一個(gè)的整數(shù)倍，這只有把公比是正整數(shù)的整個(gè)等比數(shù)列都放進(jìn)去同一個(gè)抽屜才行，這里用得到一個(gè)自然數(shù)分類(lèi)的基本知識(shí)：任何一個(gè)正整數(shù)都可以表示成一個(gè)奇數(shù)與2的方冪的積

8、，即若mN+,KN+，nN,則m=(2k-1)2n，并且這種表示方式是唯一的，如1=12，2=121，3=32，證明：因?yàn)槿魏我粋€(gè)正整數(shù)都能表示成一個(gè)奇數(shù)乘2的方冪，并且這種表示方法是唯一的，所以我們可把1-100的正整數(shù)分成如下50個(gè)抽屜（因?yàn)?-100中共有50個(gè)奇數(shù)）：（1）1，12，122，123，124，125，126；（2）3，32，322，323，324，325；（3）5，52，522，523，524；（4）7，72，722，723；（5）9，92，922，923；（6）11，112，1122，1123；（25）49，492；（26）51；（50）99。這樣，1-100的正整數(shù)就

9、無(wú)重復(fù)，無(wú)遺漏地放進(jìn)這50個(gè)抽屜內(nèi)了。從這100個(gè)數(shù)中任取51個(gè)數(shù)，也即從這50個(gè)抽屜內(nèi)任取51個(gè)數(shù)，根據(jù)抽屜原則，其中必定至少有兩個(gè)數(shù)屬于同一個(gè)抽屜，即屬于（1）-（25）號(hào)中的某一個(gè)抽屜，顯然，在這25個(gè)抽屜中的任何同一個(gè)抽屜內(nèi)的兩個(gè)數(shù)中，一個(gè)是另一個(gè)的整數(shù)倍。說(shuō)明：（1）從上面的證明中可以看出，本題能夠推廣到一般情形：從1-2n的自然數(shù)中，任意取出n+1個(gè)數(shù)，則其中必有兩個(gè)數(shù)，它們中的一個(gè)是另一個(gè)的整數(shù)倍。想一想，為什么？因?yàn)?-2n中共含1，3，2n-1這n個(gè)奇數(shù)，因此可以制造n個(gè)抽屜，而n+1n，由抽屜原則，結(jié)論就是必然的了。給n以具體值，就可以構(gòu)造出不同的題目。例2中的n取值是50

10、，還可以編制相反的題目，如：“從前30個(gè)自然數(shù)中最少要（不看這些數(shù)而以任意方式地）取出幾個(gè)數(shù)，才能保證取出的數(shù)中能找到兩個(gè)數(shù)，其中較大的數(shù)是較小的數(shù)的倍數(shù)？”（2）如下兩個(gè)問(wèn)題的結(jié)論都是否定的（n均為正整數(shù)）想一想，為什么？從2，3，4，2n+1中任取n+1個(gè)數(shù)，是否必有兩個(gè)數(shù)，它們中的一個(gè)是另一個(gè)的整數(shù)倍？從1，2，3，2n+1中任取n+1個(gè)數(shù)，是否必有兩個(gè)數(shù)，它們中的一個(gè)是另一個(gè)的整數(shù)倍？你能舉出反例，證明上述兩個(gè)問(wèn)題的結(jié)論都是否定的嗎？（3）如果將（2）中兩個(gè)問(wèn)題中任取的n+1個(gè)數(shù)增加1個(gè)，都改成任取n+2個(gè)數(shù)，則它們的結(jié)論是肯定的還是否定的？你能判斷證明嗎？3證明：把前25個(gè)自然數(shù)分成

11、下面6組：1；2，3；4，5，6；7，8，9，10；11，12，13，14，15，16；17，18，19，20，21，22，23，因?yàn)閺那?5個(gè)自然數(shù)中任意取出7個(gè)數(shù)，所以至少有兩個(gè)數(shù)取自上面第組到第組中的某同一組，這兩個(gè)數(shù)中大數(shù)就不超過(guò)小數(shù)的1.5倍。說(shuō)明：（1）本題可以改變敘述如下：在前25個(gè)自然數(shù)中任意取出7個(gè)數(shù)，求證其中存在兩個(gè)數(shù)，它們相互的比值在內(nèi)。顯然，必須找出一種能把前25個(gè)自然數(shù)分成6（7-1=6）個(gè)集合的方法，不過(guò)分類(lèi)時(shí)有一個(gè)限制條件：同一集合中任兩個(gè)數(shù)的比值在內(nèi)，故同一集合中元素的數(shù)值差不得過(guò)大。這樣，我們可以用如上一種特殊的分類(lèi)法：遞推分類(lèi)法：從1開(kāi)始，顯然1只能單獨(dú)作為

12、1個(gè)集合1；否則不滿足限制條件。能與2同屬于一個(gè)集合的數(shù)只有3，于是2，3為一集合。如此依次遞推下去，使若干個(gè)連續(xù)的自然數(shù)屬于同一集合，其中最大的數(shù)不超過(guò)最小的數(shù)的倍，就可以得到滿足條件的六個(gè)集合。（2）如果我們按照（1）中的遞推方法依次造“抽屜”，則第7個(gè)抽屜為26，27，28，29，30，31，32，33，34，35，36，37，38，39；第8個(gè)抽屜為：40，41，42，60；第9個(gè)抽屜為：61，62，63，90，91；那么我們可以將例3改造為如下一系列題目：（1）從前16個(gè)自然數(shù)中任取6個(gè)自然數(shù)；（2）從前39個(gè)自然數(shù)中任取8個(gè)自然數(shù)；（3）從前60個(gè)自然數(shù)中任取9個(gè)自然數(shù)；（4）從前

13、91個(gè)自然數(shù)中任取10個(gè)自然數(shù)；都可以得到同一個(gè)結(jié)論：其中存在2個(gè)數(shù)，它們相互的比值在內(nèi)。上述第（4）個(gè)命題，就是前蘇聯(lián)基輔第49屆數(shù)學(xué)競(jìng)賽試題。如果我們改變區(qū)間（pq）端點(diǎn)的值，則又可以構(gòu)造出一系列的新題目來(lái)。4.分析與解答：一個(gè)有著10個(gè)元素的集合，它共有多少個(gè)可能的子集呢？由于在組成一個(gè)子集的時(shí)候，每一個(gè)元素都有被取過(guò)來(lái)或者不被取過(guò)來(lái)兩種可能，因此，10個(gè)元素的集合就有210=1024個(gè)不同的構(gòu)造子集的方法，也就是，它一共有1024個(gè)不同的子集，包括空集和全集在內(nèi)。空集與全集顯然不是考慮的對(duì)象，所以剩下1024-2=1022個(gè)非空真子集。再來(lái)看各個(gè)真子集中一切數(shù)字之和。用N來(lái)記這個(gè)和數(shù)，

14、很明顯：10N91+92+93+94+95+96+97+98+99=855這表明N至多只有855-9=846種不同的情況。由于非空真子集的個(gè)數(shù)是1022，1022846，所以一定存在兩個(gè)子集A與B，使得A中各數(shù)之和=B中各數(shù)之和。若AB=，則命題得證，若AB=C，即A與B有公共元素，這時(shí)只要剔除A與B中的一切公有元素，得出兩個(gè)不相交的子集A1與B1，很顯然A1中各元素之和=B1中各元素之和，因此A1與B1就是符合題目要求的子集。說(shuō)明：本例能否推廣為如下命題：已給一個(gè)由m個(gè)互不相等的n位十進(jìn)制正整數(shù)組成的集合。求證：這個(gè)集合必有兩個(gè)無(wú)公共元素的子集合，各子集合中各數(shù)之和相等。請(qǐng)讀者自己來(lái)研究這個(gè)

15、問(wèn)題。x5分析與解答：由中點(diǎn)坐標(biāo)公式知，坐標(biāo)平面兩點(diǎn)（1,y1）、（x2,y2）的中點(diǎn)坐標(biāo)是。欲使都是整數(shù)，必須而且只須x1與x2，y1與y2的奇偶性相同。坐標(biāo)平面上的任意整點(diǎn)按照橫縱兩個(gè)坐標(biāo)的奇偶性考慮有且只有如下四種：（奇數(shù)、奇數(shù)），（偶數(shù)，偶數(shù)），（奇數(shù)，偶數(shù)），（偶數(shù)，奇數(shù)）以此構(gòu)造四個(gè)“抽屜”，則在坐標(biāo)平面上任取五個(gè)整點(diǎn)，那么至少有兩個(gè)整點(diǎn)，屬于同一個(gè)“抽屜”因此它們連線的中點(diǎn)就必是整點(diǎn)。說(shuō)明：我們可以把整點(diǎn)的概念推廣：如果（x1,x2,xn）是n維（元）有序數(shù)組，且x1,x2,xn中的每一個(gè)數(shù)都是整數(shù)，則稱(chēng)（x1,x2,xn）是一個(gè)n維整點(diǎn)（整點(diǎn)又稱(chēng)格點(diǎn)）。如果對(duì)所有的n維整點(diǎn)按每

16、一個(gè)xi的奇偶性來(lái)分類(lèi)，由于每一個(gè)位置上有奇、偶兩種可能性，因此共可分為222=2n個(gè)類(lèi)。這是對(duì)n維整點(diǎn)的一種分類(lèi)方法。當(dāng)n=3時(shí)，23=8，此時(shí)可以構(gòu)造命題：“任意給定空間中九個(gè)整點(diǎn)，求證它們之中必有兩點(diǎn)存在，使連接這兩點(diǎn)的直線段的內(nèi)部含有整點(diǎn)”。這就是1971年的美國(guó)普特南數(shù)學(xué)競(jìng)賽題。在n=2的情形，也可以構(gòu)造如下的命題：“平面上任意給定5個(gè)整點(diǎn)”，對(duì)“它們連線段中點(diǎn)為整點(diǎn)”的4個(gè)命題中，為真命題的是：（A）最少可為0個(gè)，最多只能是5個(gè)（B）最少可為0個(gè)，最多可取10個(gè)（C）最少為1個(gè)，最多為5個(gè)（D）最少為1個(gè)，最多為10個(gè)（正確答案（D）6分析：本題也似乎是茫無(wú)頭緒，無(wú)從下手，其關(guān)鍵何

17、在？仔細(xì)審題，它們的“和”能“被100整除”應(yīng)是做文章的地方。如果把這100個(gè)數(shù)排成一個(gè)數(shù)列，用Sm記其前m項(xiàng)的和，則其可構(gòu)造S1，S2，S100共100個(gè)和數(shù)。討論這些“和數(shù)”被100除所得的余數(shù)。注意到S1，S2，S100共有100個(gè)數(shù)，一個(gè)數(shù)被100除所得的余數(shù)有0，1，2，99共100種可能性?！疤O(píng)果”數(shù)與“抽屜”數(shù)一樣多，如何排除“故障”？證明：設(shè)已知的整數(shù)為a1,a2,a100考察數(shù)列a1,a2,a100的前n項(xiàng)和構(gòu)成的數(shù)列S1，S2，S100。如果S1，S2，S100中有某個(gè)數(shù)可被100整除，則命題得證。否則，即S1，S2，S100均不能被100整除，這樣，它們被100除后余數(shù)必

18、是1，2，99中的元素。由抽屜原理I知，S1，S2，S100中必有兩個(gè)數(shù)，它們被100除后具有相同的余數(shù)。不妨設(shè)這兩個(gè)數(shù)為Si，Sj（ij），則100（Sj-Si），即100。命題得證。說(shuō)明：有時(shí)候直接對(duì)所給對(duì)象作某種劃分，是很難構(gòu)造出恰當(dāng)?shù)某閷系?。這時(shí)候，我們需要對(duì)所給對(duì)象先作一些變換，然后對(duì)變換得到的對(duì)象進(jìn)行分類(lèi)，就可以構(gòu)造出恰當(dāng)?shù)某閷?。本題直接對(duì)an進(jìn)行分類(lèi)是很難奏效的。但由an構(gòu)造出Sn后，再對(duì)Sn進(jìn)行分類(lèi)就容易得多。另外，對(duì)Sn按模100的剩余類(lèi)劃分時(shí)，只能分成100個(gè)集合，而Sn只有100項(xiàng)，似乎不能應(yīng)用抽屜原則。但注意到余數(shù)為0的類(lèi)恰使結(jié)論成立，于是通過(guò)分別情況討論后，就可去掉余

19、數(shù)為0的類(lèi)，從而轉(zhuǎn)化為100個(gè)數(shù)分配在剩下的99個(gè)類(lèi)中。這種處理問(wèn)題的方法應(yīng)當(dāng)學(xué)會(huì)，它會(huì)助你從“山窮水盡疑無(wú)路”時(shí)，走入“柳暗花明又一村”中。最后，本例的結(jié)論及證明可以推廣到一般情形（而且有加強(qiáng)的環(huán)節(jié)）：在任意給定的n個(gè)整數(shù)中，都可以找出若干個(gè)數(shù)來(lái)（可以是一個(gè)數(shù)），它們的和可被n整除，而且，在任意給定的排定順序的n個(gè)整數(shù)中，都可以找出若干個(gè)連續(xù)的項(xiàng)（可以是一項(xiàng)），它們的和可被n整除。將以上一般結(jié)論中的n賦以相應(yīng)的年份的值如1999，2000，2001，就可以編出相應(yīng)年份的試題來(lái)。如果再賦以特殊背景，則可以編出非常有趣的數(shù)學(xué)智力題來(lái)，如下題：有100只猴子在吃花生，每只猴子至少吃了1?；ㄉ?，多者

20、不限。請(qǐng)你證明：一定有若干只猴子（可以是一只），它們所吃的花生的粒數(shù)總和恰好是100的倍數(shù)。7證明：視17個(gè)科學(xué)家為17個(gè)點(diǎn)，每?jī)蓚€(gè)點(diǎn)之間連一條線表示這兩個(gè)科學(xué)家在討論同一個(gè)問(wèn)題，若討論第一個(gè)問(wèn)題則在相應(yīng)兩點(diǎn)連紅線，若討論第2個(gè)問(wèn)題則在相應(yīng)兩點(diǎn)連條黃線，若討論第3個(gè)問(wèn)題則在相應(yīng)兩點(diǎn)連條藍(lán)線。三名科學(xué)家研究同一個(gè)問(wèn)題就轉(zhuǎn)化為找到一個(gè)三邊同顏色的三角形?？紤]科學(xué)家A，他要與另外的16位科學(xué)家每人通信討論一個(gè)問(wèn)題，相應(yīng)于從A出發(fā)引出16條線段，將它們?nèi)境?種顏色，而16=35+1，因而必有6=5+1條同色，不妨記為AB1，AB2，AB3，AB4，AB5，AB6同紅色，若Bi（i=1，2，6）之間有紅線，則出現(xiàn)紅色三角線，命題已成立；否則B1，B2，B3，B4，B5，B6之間的連線只染有黃藍(lán)兩色。考慮從B1引出的5條線，B1B2，B1B3，B1B4，B1B5，B1B6，用兩種顏色染色，因?yàn)?=22+1，故必有3=2+1條線段同色，假設(shè)為黃色，并