淺談抽屜原理在高中數(shù)學競賽中的運用

1、淺談抽屜原理在高中數(shù)學競賽中的運用在數(shù)學問題中有一類與“存在性”有關(guān)的問題，例如：“13個人中至少有兩個人出生在相同月份”；“某校400名學生中，一定存在兩名學生，他們在同一天過生日；“2003個人任意分成200個小組，一定存在一組，其成員數(shù)不少于11” ； “把0,1內(nèi)的全部有理數(shù)放到100個集合中，一定存在一個集合，它里面有無限多個有理數(shù)”。這類存在性問題 中，“存在”的含義是“至少有一個”。在解決這類問題時，只要求指明存在，一般并不需要指出哪一個，也不需要確定通過什么方式把這個存在的東西找出來。這類問題相對來說涉及到的運算較少，依據(jù)的理論也不復雜，我們把這些理論稱之為“抽屜原理”.“抽屜

2、原理”最先是由19世紀的德國數(shù)學家迪里赫萊 （Dirichlet）運用于解決數(shù)學問 題的，所以又稱“迪里赫萊原理”，也有稱“鴿巢原理”的。 這個原理可以簡單地敘述為“把10個蘋果，任意分放在9個抽屜里，則至少有一個抽屜里含有兩個或兩個以上的蘋果”。 這個道理是非常明顯的，但應用它卻可以解決許多有趣的問題， 并且常常得到一些令人驚異 的結(jié)果。抽屜原理是國際國內(nèi)各級各類數(shù)學競賽中的重要內(nèi)容，本講就來學習它的有關(guān)知識及其應用。、抽屜原理的基本形式定理1、如果把n+1個元素分成n個集合，那么不管怎么分，都存在一個集合，其中至 少有兩個元素。例1.已知在邊長為1的等邊三角形內(nèi)（包括邊界）有任意五個點（如

3、圖）。證明：至1少有兩個點之間的距離不大于（1978年廣東省數(shù)學競賽題）2分析：5個點的分布是任意的。如果要證明“在邊長為1的等邊三角形內(nèi)（包括邊界）有5個點，那么這5個點中一定有距離1不大于丄的兩點”，則順次連接三角形三邊中點，即三角形的三21條中位線，可以分原等邊三角形為4個全等的邊長為-2的小等邊三角形，則5個點中必有2點位于同一個小等1邊三角形中（包括邊界），其距離便不大于。2以上結(jié)論要由定理“三角形內(nèi)（包括邊界）任意兩點間的距離不大于其最大邊長”來保 證，下面我們就來證明這個定理。如圖，設(shè)BC是心ABC的最大邊，P,M是心ABC內(nèi)（包括邊界）任意兩點，連接PM過P分別作AB BC邊的

4、平行線，過M作AC邊的平行線，設(shè)各平行線交點為P、Q N,那么/PQNMC,/QNPMA因為BOAB所以/AZC,則/QN/PQN而/QMPP/QNR/PQN（三角形的外角大于不相鄰的內(nèi)角），所以POPM顯然BOPQ故BOPM11由此我們可以推知，邊長為的等邊三角形內(nèi)（包括邊界）兩點間的距離不大于22說明：（1）這里是用等分三角形的方法來構(gòu)造“抽屜”。類似地，還可以利用等分線段、等分正方形的方法來構(gòu)造“抽屜”。例如“任取n+1個正數(shù)a,滿足0vaiWl1（i=1,2,n+1），試證明：這n+1個數(shù)中必存在兩個數(shù)，其差的絕對值小于。又如：n“在邊長為1的正方形內(nèi)任意放置五個點，求證：其中必有兩點

5、，這兩點之間的距離不大于（2）例1中，如果把條件（包括邊界）去掉，則結(jié)論可以修改為：至少有兩個點之間1的距離小于丄，大家可以自己證明，并比較證明的差別。2（3）用同樣的方法可證明以下結(jié)論：i）在邊長為1的等邊三角形中有n2+1個點，這n2+1個點中一定有距離不大于 -的兩點。n1ii）在邊長為1的等邊三角形內(nèi)有n2+1個點，這n2+1個點中一定有距離小于的兩點。（4）將（3）中兩個命題中的等邊三角形換成正方形，相應的結(jié)論中的命題仍然成立。（5）我們還可以考慮相反的問題：一般地，至少需要多少個點，才能夠使得邊長為1的正三角形內(nèi)（包括邊界）有兩點其距離不超過例2.從1-100的自然數(shù)中，任意取出5

6、1個數(shù)，證明其中一定有兩個數(shù)，它們中的一個是 另一個的整數(shù)倍。分析：本題似乎茫無頭緒， 從何入手？其關(guān)鍵何在？其實就在“兩個數(shù)”，其中一個是另一個的整數(shù)倍。我們要構(gòu)造“抽屜”，使得每個抽屜里任取兩個數(shù), 整數(shù)倍，這只有把公比是正整數(shù)的整個等比數(shù)列都放進去同一個抽屜才行, 自然數(shù)分類的基本知識：任何一個正整數(shù)都可以表示成一個奇數(shù)與-換成一2,n n都有一個是另一個的這里用得到一個2的方幕的積，即若1=1X2,2=1X2mN+,KN+,nN,則m=（2k-1）2n,并且這種表示方式是唯一的，如3=3X2證明：因為任何一個正整數(shù)都能表示成一個奇數(shù)乘2的方冪，并且這種表示方法是唯一25)49，49X2

7、；26)51；（50）99。這樣，1-100的正整數(shù)就無重復，無遺漏地放進這50個抽屜內(nèi)了。從這100個數(shù)中任 取51個數(shù)，也即從這50個抽屜內(nèi)任取51個數(shù)，根據(jù)抽屜原則，其中必定至少有兩個數(shù)屬 于同一個抽屜，即屬于（1）-（25）號中的某一個抽屜，顯然，在這25個抽屜中的任何同 一個抽屜內(nèi)的兩個數(shù)中，一個是另一個的整數(shù)倍。說明：（1）從上面的證明中可以看出，本題能夠推廣到一般情形：從1-2n的自然數(shù)中，任意取出n+1個數(shù)，則其中必有兩個數(shù)，它們中的一個是另一個的整數(shù)倍。 想一想，為什么？ 因為1-2n中共含1,3，2n-1這n個奇數(shù)，因此可以制造n個抽屜，而n+1n,由抽 屜原則，結(jié)論就是必

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

9、數(shù)，則它們的結(jié)論是肯定的還是否定的？你能判斷證明嗎？例3.從前25個自然數(shù)中任意取出7個數(shù)，證明：取出的數(shù)中一定有兩個數(shù)，這兩個 數(shù)中大數(shù)不超過小數(shù)的1.5倍。的，所以我們可把1-100的正整數(shù)分成如下1）1,1X2,1X221X23,1X242）3,3X2,3X2233X23,3X243）5,5X2,5X225X23,5X244）7,7X2,7X2237X23；5）9,9X2,9X2239X23；6）11,11X2,11X2232,11X23；50個抽屜（因為1-100中共有50個奇數(shù)）：1X 25,1X 26;證明：把前25個自然數(shù)分成下面6組：1;2,3;4,5,6;7,8,9,10;1

10、1,12,13,14,15,16;17,18,19,20,21,22,23,因為從前25個自然數(shù)中任意取出7個數(shù)，所以至少有兩個數(shù)取自上面第組到第組 中的某同一組，這兩個數(shù)中大數(shù)就不超過小數(shù)的1.5倍。說明：（1）本題可以改變敘述如下：在前25個自然數(shù)中任意取出7個數(shù)，求證其中存在兩個數(shù)，它們相互的比值在-,-內(nèi)。h,2j顯然，必須找出一種能把前25個自然數(shù)分成6（7-仁6）個集合的方法，不過分類時有一個限制條件：同一集合中任兩個數(shù)的比值在2,3內(nèi)，故同一集合中元素的數(shù)值差不得IL3 2過大。這樣，我們可以用如上一種特殊的分類法：遞推分類法：從1開始，顯然1只能單獨作為1個集合1;否則不滿足限

11、制條件。能與2同屬于一個集合的數(shù)只有3,于是2,3為一集合。如此依次遞推下去，使若干個連續(xù)的自然數(shù)屬于同一集合，其中最大的數(shù)不超過最小的3數(shù)的3倍，就可以得到滿足條件的六個集合。2（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;22那么我們可以將例3改造為如下一系列題目：(1)從前16個自然數(shù)中任取6個自然數(shù)；(2)從前39個自然數(shù)中任取8個自然數(shù)；(3)從前60個自然數(shù)中任取9個自然數(shù)；(4)從前91個自然

12、數(shù)中任取10個自然數(shù)；都可以得到同一個結(jié)論：其中存在2個數(shù)，它們相互的比值在-,-內(nèi)。収2上述第(4)個命題，就是前蘇聯(lián)基輔第49屆數(shù)學競賽試題。如果我們改變區(qū)間|9,衛(wèi)Ip q一(pq)端點的值，則又可以構(gòu)造出一系列的新題目來。例4.已給一個由10個互不相等的兩位十進制正整數(shù)組成的集合。求證：這個集合必 有兩個無公共元素的子集合，使子集合中各數(shù)之和相等。(第14屆1M0試題)分析與解答：一個有著10個元素的集合共有210=1024個不同的子集，包括空集和全集 在內(nèi)?？占c全集顯然不是考慮的對象，所以剩下1024-2=1022個非空真子集。再來看各個真子集中一切數(shù)字之和。用N來記這個和數(shù)，很明

13、顯：10WNK91+92+93+94+95+96+97+98+99=855這表明N至多只有855-9=846種不同的情況。由于非空真子集的個數(shù)是1022,1022846,所以一定存在兩個子集A與B,使得A中各數(shù)之和=B中各數(shù)之和。若AAB=$，則命題得證，若AAB=O$ ,即A與B有公共元素，這時只要剔除A與B中的一切公有元素，得出兩個不相交的子集A與B,很顯然，A中各元素之和=B1中各元素 之和，因此A與B就是符合題目要求的子集。思考：本例能否推廣為如下命題：已給一個由m個互不相等的n位十進制正整數(shù)組成的集合。求證：這個集合必有兩個無公共元素的子集合，各子集合中各數(shù)之和相等。例5.在坐標平面

14、上任取五個整點(該點的橫縱坐標都取整數(shù))，證明：其中一定存在 兩個整點，它們的連線中點仍是整點。分析：由中點坐標公式，坐標平面兩點 為，, x2, y2的中點坐標i 生， 血。12 2丿欲使X1一X2M一y2都是整數(shù)，必須而且只須X1與X2,y1與y2的奇偶性相同。坐標平面上 的任意整點按照橫縱兩個坐標的奇偶性考慮有且只有如下四種：（奇數(shù)、奇數(shù)），（偶數(shù)， 偶數(shù)），（奇數(shù)，偶數(shù)），（偶數(shù)，奇數(shù)）以此構(gòu)造四個“抽屜”，則在坐標平面上任取五 個整點，那么至少有兩個整點，屬于同一個“抽屜”因此它們連線的中點就必是整點。說明：我們可以把整點的概念推廣：如果（X1,X2,Xn）是n維（元）有序數(shù)組，且X

15、1,X2,Xn中的每一個數(shù)都是整數(shù)，則稱（X1,X2,Xn）是一個n維整點。如果對所有的n維整點按每 一個Xi的奇偶性來分類，由于每一個位置上有奇、偶兩種可能性，因此共可分為2X2X-X2=2n個類。這是對n維整點的一種分類方法。當n=3時，23=8，此時可以構(gòu)造命題：“任意給定空間中九個整點，求證它們之中必有兩點存在，使連接這兩點的直線段的內(nèi)部含有整點”。這就是1971年的美國普特南數(shù)學競賽題。在n=2的情形，也可以構(gòu)造如下的命題：“平面上任意給定5個整點”，對“它們連線段中點為整點”的4個命題中，為真命題的是：（A）最少可為0個，最多只能是5個；（B）最少可為0個，最多可取10個（C）最少

16、為1個，最多為5個；（D）最少為1個，最多為10個 答案（D）例6.在任意給出的100個整數(shù)中，都可以找出若干個數(shù)來（可以是一個數(shù)），它們的和可被100整除。分析：本題也似乎是茫無頭緒，無從下手，其關(guān)鍵何在？仔細審題，它們的“和”能“被100整除”應是做文章的地方。如果把這100個數(shù)排成一個數(shù)列，用Sm記其前m項的和，貝y其可構(gòu)造S1,S2,S100共100個”和數(shù)。討論這些“和數(shù)”被100除所得的余數(shù)。注意到S,S2,-S100共有100個數(shù)，一個數(shù)被100除所得的余數(shù)有0,1,2,99共100種可能性。 “蘋果”數(shù)與“抽屜”數(shù)一樣多，如何排除“故障”？證明：設(shè)已知的整數(shù)為a1,a2,-a1

17、00考察數(shù)列a1,a2,-a100的前n項和構(gòu)成的數(shù)列S,S2,S100。如果S,S2,S100中有某個數(shù)可被100整除，則命題得證。否則，即S, S，S100均 不能被100整除，這樣，它們被100除后余數(shù)必是1,2,，99中的元素。由抽屜原理I知，S,S,S100中必有兩個數(shù)，它們被100除后具有相同的余數(shù)。不妨設(shè)這兩個數(shù)為Si,S（iVj）,則1001（Sj-Si）,即卩1001a ai2I。命題得證。說明：有時候直接對所給對象作某種劃分，是很難構(gòu)造出恰當?shù)某閷系?。這時候，我們 需要對所給對象先作一些變換，然后對變換得到的對象進行分類，就可以構(gòu)造出恰當?shù)某閷稀?本題直接對an進行分類是很

18、難奏效的。 但由an構(gòu)造出Sn后，再對Sn進行分類就容易得多。另外，對Sn按模100的剩余類劃分時，只能分成100個集合，而Sn只有100項，似 乎不能應用抽屜原則。 但注意到余數(shù)為0的類恰使結(jié)論成立， 于是通過分別情況討論后， 就 可去掉余數(shù)為0的類，從而轉(zhuǎn)化為100個數(shù)分配在剩下的99個類中。最后，本例的結(jié)論及證明可以推廣到一般情形（而且有加強的環(huán)節(jié)）：在任意給定的n個整數(shù)中，都可以找出若干個數(shù)來（可以是一個數(shù)），它們的和可被n整除， 而且，在任意給定的排定順序的n個整數(shù)中，都可以找出若干個連續(xù)的項（可以是一 項），它們的和可被n整除。將以上一般結(jié)論中的n賦以相應的年份的值如1999,20

19、00,2001，就可以編出相應 年份的試題來。如果再賦以特殊背景，則可以編出非常有趣的數(shù)學智力題來，如下題：有100只猴子在吃花生,每只猴子至少吃了1粒花生,多者不限。 請你證明： 一定有若干只猴子（可以是一只）,它們所吃的花生的粒數(shù)總和恰好是100的倍數(shù)。二、單色三角形問題前面數(shù)例我們看到, 抽屜原理應用的關(guān)鍵在于恰當?shù)刂圃斐閷? 分割圖形, 利用自然數(shù) 分類的不同方法如按剩余類制造抽屜或按奇數(shù)乘以2的方冪制造抽屜, 利用奇偶性等等, 都 是制造“抽屜”的方法。 大家看到, 抽屜原理的道理極其簡單,但恰當?shù)鼐牡貞盟?不 僅可以解決國內(nèi)數(shù)學競賽中的問題, 而且可以解決國際中學生數(shù)學競賽,

20、例如IM0中的難題。例7（第6屆國際中學生數(shù)學奧林匹克試題）17名科學家中每兩名科學家都和其他科 學家通信,在他們通信時,只討論三個題目,而且任意兩名科學家通信時只討論一個題目, 證明：其中至少有三名科學家,他們相互通信時討論的是同一個題目。證明：視17個科學家為17個點,每兩個點之間連一條線表示這兩個科學家在討論同一 個問題,若討論第一個問題則在相應兩點連紅線, 若討論第2個問題則在相應兩點連條黃線, 若討論第3個問題則在相應兩點連條藍線。 三名科學家研究同一個問題就轉(zhuǎn)化為找到一個三 邊同顏色的三角形。 （本例同第十二講染色問題例4）考慮科學家A,他要與另外的16位科學家每人通信討論一個問題

21、，相應于從A出發(fā)引出16條線段， 將它們?nèi)境?種顏色， 而16=3X5+1,因而必有6=5+1條同色， 不妨記為AB,AB,AB3,AB4,AB,AB6同紅色，若Bi（i=1,2，6）之間有紅線，則出現(xiàn)紅色三角線， 命題已成立；否則B1，B2，B3，B4，B5，B6之間的連線只染有黃藍兩色。考慮從Bi引出的5條線，B1B2,B1B3, BB4,B1B5,B1B6,用兩種顏色染色， 因為5=2X2+1,故必有3=2+1條線段同色，假設(shè)為黃色，并記它們?yōu)锽iR,BB3, BB。這時若B2,Ba,B4之間有黃線，則有黃色三角形，命題也成立，若B2，Ba，B4,之間無黃線，則AB2，Ba，B4,必為藍

22、色三角形，命題仍然成立。說明：(1)本題源于一個古典問題-世界上任意6個人中必有3人互相認識，或互相 不認識。(美國普特南數(shù)學競賽題)。(2)將互相認識用紅色表示，將互相不認識用藍色表示，(1)將化為一個染色問題，成為一個圖論問題：空間六個點，任何三點不共線，四點不共面，每兩點之間連線都涂上紅色或藍色。求證：存在三點，它們所成的三角形三邊同色。(3)問題(2)可以往兩個方向推廣：其一是顏色的種數(shù)，其二是點數(shù)。本例便是方向一的進展，其證明已知上述。如果繼續(xù)沿此方向前進，可有下題：在66個科學家中，每個科學家都和其他科學家通信，在他們的通信中僅僅討論四個題目,而任何兩個科學家之間僅僅討論一個題目。

23、證明至少有三個科學家，他們互相之間討論同一個題目。(4)回顧上面證明過程，對于17點染3色問題可歸結(jié)為6點染2色問題，又可歸結(jié)為3點染一色問題。反過來，我們可以繼續(xù)推廣。從以上(3,1)(6,2)T(17,3)的過程，易發(fā)現(xiàn)6=(3-1)X2+2,17=(6-1)X3+2,66=(17-1)X4+2,同理可得(66-1)X5+2=327,(327-1)x6+2=1958記為1=3,2=6,o=17,r4=66,r5=327,6=1958,我們可以得到遞推關(guān)系式：rn= n(rn-1-1)+2,n=2,3,4這樣就可以構(gòu)造出327點染5色問題，1958點染6色問題，都必出現(xiàn)一個同色三角形。三、抽

24、屜原理的其他形式在例7的證明過程中，我們實際上用到了抽屜原理的其他形式，我們把它作為定理2。定理2:把m個元素分成n個集合(m n)(1)當n能整除m時，至少有一個集合含有m個元素；n(2)當n不能整除m時，則至少有一個集合含有至少m1個元素。_n定理2有時候也可敘述成：把mKn+1個元素放進n個集合，則必有一個集合中至少放 有m+1個元素。例8.在邊長為1的正方形內(nèi)任意放入九個點，求證：存在三個點，以這三個點為頂點1的三角形的面積不超過（1963年北京市數(shù)學競賽題）。8分析與解答：如圖，四等分正方形，得到A,A, A,A四個矩形。在正方形內(nèi)任意放入九個點，則至少有一個矩形A內(nèi)存在9=3個或3

25、個以上的點，設(shè)_4三點為A、B、C,具體考察A（如圖所示），過A、B、C三點分別作矩形長邊的平行線，過矩形長邊的距離為1h=(0 3,nv6，求證：在這些矩形中一定存在無限多個矩形，其中任意兩個矩形必有一個被包含在另一個之中。證明： 由nv6知,n=1,2,3,4,5,只有5種情形,由定理3知,將所給的無窮多個矩形按n的取值分成5類,當作5個抽屜,其中必有一個抽屜（一類）里包含有無窮多個矩形。 不妨設(shè)這一類矩形的n的取值為n。對于這一類矩形中的任意兩個矩形而言，由于n的取值相同，因此m取值較小的一個矩形必然被包含在m取值較大的一個矩形之中。五、抽屜原理的多次使用例12有蘋果、梨、桔子若干個,任意分成9堆,求證一定可以找到兩堆,其蘋果數(shù)、梨數(shù)、桔子數(shù)分別求和都是偶數(shù)。證明：因為每一堆里的每一種水果數(shù)或為奇數(shù)或為偶數(shù)（兩個抽屜），而9=2X4+1,故對于蘋果，9堆中必有5堆的奇偶性相同；這5堆對于梨數(shù)來說，由于5=2X2+1,故必有3堆的奇偶性相同； 這3堆對于桔子數(shù)也必有2堆的奇偶性相同。 于是, 就找到這樣的兩堆, 它們的蘋果數(shù)、梨數(shù),桔子數(shù)的奇偶性都分別相同,從而其和數(shù)分別都是偶數(shù)。說明 ：為了得出和是偶數(shù), 需要兩加數(shù)的奇偶性相同。 對3類水果逐一找用了3次抽屜原理,若將過程合并簡化可將蘋果數(shù)、梨數(shù)、桔子數(shù)作為的奇偶性構(gòu)造8個抽屜：奇,奇,奇