抽屜原理的典型問題

1、奧數(shù)探秘：奧數(shù)之抽屜原理桌上有十個(gè)蘋果，要把這十個(gè)蘋果放到九個(gè)抽屜里，無論怎樣放，有的抽屜可以放一個(gè)，有的可以放兩個(gè)，有的可以放五個(gè)，但最終我們會(huì)發(fā)現(xiàn)至少我們可以找到一個(gè)抽屜里面至少放兩個(gè)蘋果。這一現(xiàn)象就是我們所說的抽屜原理。抽屜原理的一般含義為：“如果每個(gè)抽屜代表一個(gè)集合，每一個(gè)蘋果就可以代表一個(gè)元素，假如有n+1或多于n+1個(gè)元素放到n個(gè)集合中去，其中必定至少有一個(gè)集合里至少有兩個(gè)元素?！币?.抽屜原理最常見的形式原理1把多于n個(gè)的物體放到n個(gè)抽屜里，則至少有一個(gè)抽屜里有2個(gè)或2個(gè)以上的物體。證明（反證法）：如果每個(gè)抽屜至多只能放進(jìn)一個(gè)物體，那么物體的總數(shù)至多是n,而不是題設(shè)的n+k（k1

2、），這不可能.原理2把多于mn（m乘以n）個(gè)的物體放到n個(gè)抽屜里，則至少有一個(gè)抽屜里有m+1個(gè)或多于m+1個(gè)的物體。證明（反證法）：若每個(gè)抽屜至多放進(jìn)m個(gè)物體，那么n個(gè)抽屜至多放進(jìn)mn個(gè)物體，與題設(shè)不符，故不可能.原理12都是第一抽屜原理的表述第二抽屜原理：把（mn-1）個(gè)物體放入n個(gè)抽屜中，其中必有一個(gè)抽屜中至多有（m1）個(gè)物體。證明（反證法）：若每個(gè)抽屜都有不少于m個(gè)物體，則總共至少有mn個(gè)物體，與題設(shè)矛盾，故不可能二 .應(yīng)用抽屜原理解題例1：400人中至少有兩個(gè)人的生日相同.解：將一年中的366天視為366個(gè)抽屜,400個(gè)人看作400個(gè)物體,由抽屜原理1可以得知：至少有兩人的生日相同.又

3、如：我們從街上隨便找來13人,就可斷定他們中至少有兩個(gè)人屬相相同.“從任意5雙手套中任取6只,其中至少有2只恰為一雙手套?！薄皬臄?shù)1,2,.,10中任取6個(gè)數(shù),其中至少有2個(gè)數(shù)為奇偶性不同。”例2：幼兒園買來了不少白兔、熊貓、長(zhǎng)頸鹿塑料玩具,每個(gè)小朋友任意選擇兩件,那么不管怎樣挑選,在任意七個(gè)小朋友中總有兩個(gè)彼此選的玩具都相同,試說明道理.解：從三種玩具中挑選兩件,搭配方式只能是下面六種：（兔、兔）,（兔、熊貓）,（兔、長(zhǎng)頸鹿）,（熊貓、熊貓）,（熊貓、長(zhǎng)頸鹿）,（長(zhǎng)頸鹿、長(zhǎng)頸鹿）。把每種搭配方式看作一個(gè)抽屜,把7個(gè)小朋友看作物體,那么根據(jù)原理1,至少有兩個(gè)物體要放進(jìn)同一個(gè)抽屜里,也就是說,至

4、少兩人挑選玩具采用同一搭配方式,選的玩具相同.上面數(shù)例論證的似乎都是“存在”、“總有”、“至少有”的問題,不錯(cuò),這正是抽屜原則的主要作用.（需要說明的是,運(yùn)用抽屜原則只是肯定了“存在”、“總有”、“至少有”,卻不能確切地指出哪個(gè)抽屜里存在多少.）（一）整除問題把所有整數(shù)按照除以某個(gè)自然數(shù)m的余數(shù)分為m類，叫做m的剩余類或同余類，用0，,2，m-1表示.每一個(gè)類含有無窮多個(gè)數(shù)，例如1中含有1,m+1,2m+1,3m+1,.在研究與整除有關(guān)的問題時(shí)常用剩余類作為抽屜.根據(jù)抽屜原理可以證明：任意n+1個(gè)自然數(shù)中總有兩個(gè)自然數(shù)的差是n的倍數(shù)。例1證明：任取8個(gè)自然數(shù)，必有兩個(gè)數(shù)的差是7的倍數(shù)。分析與解

5、答在與整除有關(guān)的問題中有這樣的性質(zhì)，如果兩個(gè)整數(shù)a、b,它們除以自然數(shù)m的余數(shù)相同，那么它們的差a-b是m的倍數(shù).根據(jù)這個(gè)性質(zhì)，本題只需證明這8個(gè)自然數(shù)中有2個(gè)自然數(shù)，它們除以7的余數(shù)相同.我們可以把所有自然數(shù)按被7除所得的7種不同的余數(shù)0、1、2、3、4、5、6分成七類.也就是7個(gè)抽屜.任取8個(gè)自然數(shù)，根據(jù)抽屜原理，必有兩個(gè)數(shù)在同一個(gè)抽屜中，也就是它們除以7的余數(shù)相同，因此這兩個(gè)數(shù)的差一定是7的倍數(shù)。例2：對(duì)于任意的五個(gè)自然數(shù)，證明其中必有3個(gè)數(shù)的和能被3整除.證明任何數(shù)除以3所得余數(shù)只能是0,1,2，不妨分別構(gòu)造為3個(gè)抽屜：0，1，2 若這五個(gè)自然數(shù)除以3后所得余數(shù)分別分布在這3個(gè)抽屜中（

6、即抽屜中分別為含有余數(shù)為0,1,2的數(shù)），我們從這三個(gè)抽屜中各取1個(gè)（如15中取3,4,5），其和（3+4+5=12）必能被3整除. 若這5個(gè)余數(shù)分布在其中的兩個(gè)抽屜中，則其中必有一個(gè)抽屜，包含有3個(gè)余數(shù)（抽屜原理），而這三個(gè)余數(shù)之和或?yàn)?，或?yàn)?，或?yàn)?，故所對(duì)應(yīng)的3個(gè)自然數(shù)之和是3的倍數(shù). 若這5個(gè)余數(shù)分布在其中的一個(gè)抽屜中，很顯然，必有3個(gè)自然數(shù)之和能被3整除.例2:對(duì)于任意的11個(gè)整數(shù)，證明其中一定有6個(gè)數(shù)，它們的和能被6整除.證明：設(shè)這11個(gè)整數(shù)為：al,a2,a3all又6=2X3 先考慮被3整除的情形由例2知，在11個(gè)任意整數(shù)中，必存在：3|a1+a2+a3，不妨設(shè)a1+a2+a

7、3=b1;同理，剩下的8個(gè)任意整數(shù)中，由例2，必存在：3|a4+a5+a6.設(shè)a4+a5+a6=b2;同理，其余的5個(gè)任意整數(shù)中，有：3|a7+a8+a9，設(shè)：a7+a8+a9=b3 再考慮b1、b2、b3被2整除.依據(jù)抽屜原理，b1、b2、b3這三個(gè)整數(shù)中，至少有兩個(gè)是同奇或同偶，這兩個(gè)同奇（或同偶）的整數(shù)之和必為偶數(shù).不妨設(shè)2|b1+b2則：6|b1+b2，即：6|a1+a2+a3+a4+a5+a6任意11個(gè)整數(shù)，其中必有6個(gè)數(shù)的和是6的倍數(shù).例3：任意給定7個(gè)不同的自然數(shù)，求證其中必有兩個(gè)整數(shù)，其和或差是10的倍數(shù).分析：注意到這些數(shù)隊(duì)以10的余數(shù)即個(gè)位數(shù)字，以0,1，9為標(biāo)準(zhǔn)制造10個(gè)

8、抽屜，標(biāo)以0,1，9.若有兩數(shù)落入同一抽屜，其差是10的倍數(shù)，只是僅有7個(gè)自然數(shù)，似不便運(yùn)用抽屜原則，再作調(diào)整：6，7，8，9四個(gè)抽屜分別與4，3，2，1合并，則可保證至少有一個(gè)抽屜里有兩個(gè)數(shù)，它們的和或差是10的倍數(shù).（二）面積問題例：九條直線中的每一條直線都將正方形分成面積比為2:3的梯形，證明：這九條直線中至少有三條經(jīng)過同一點(diǎn).證明：如圖，設(shè)直線EF將正方形分成兩個(gè)梯形，作中位線MN由于這兩個(gè)梯形的高相等，故它們的面積之比等于中位線長(zhǎng)的比，即|MH|:|NH|。于是點(diǎn)H有確定的位置（它在正方形一對(duì)對(duì)邊中點(diǎn)的連線上，且|MH|:|NH|=2:3）.由幾何上的對(duì)稱性，這種點(diǎn)共有四個(gè)（即圖中的

9、H、J、I、K）.已知的九條適合條件的分割直線中的每一條必須經(jīng)過H、J、丨、K這四點(diǎn)中的一點(diǎn).把HJ、丨、K看成四個(gè)抽屜，九條直線當(dāng)成9個(gè)物體，即可得出必定有3條分割線經(jīng)過同一點(diǎn).（三）染色問題例1正方體各面上涂上紅色或藍(lán)色的油漆（每面只涂一種色），證明正方體一定有三個(gè)面顏色相同.證明：把兩種顏色當(dāng)作兩個(gè)抽屜，把正方體六個(gè)面當(dāng)作物體，那么6=2X2+2，根據(jù)原理二，至少有三個(gè)面涂上相同的顏色.例2有5個(gè)小朋友，每人都從裝有許多黑白圍棋子的布袋中任意摸出3枚棋子.請(qǐng)你證明，這5個(gè)人中至少有兩個(gè)小朋友摸出的棋子的顏色的配組是一樣的。分析與解答首先要確定3枚棋子的顏色可以有多少種不同的情況，可以有：

10、3黑，2黑1白，1黑2白，3白共4種配組情況，看作4個(gè)抽屜.根據(jù)抽屜原理，至少有兩個(gè)小朋友摸出的棋子的顏色在同一個(gè)抽屜里，也就是他們所拿棋子的顏色配組是一樣的。例3：假設(shè)在一個(gè)平面上有任意六個(gè)點(diǎn)，無三點(diǎn)共線，每?jī)牲c(diǎn)用紅色或藍(lán)色的線段連起來，都連好后，問你能不能找到一個(gè)由這些線構(gòu)成的三角形，使三角形的三邊同色?解：首先可以從這六個(gè)點(diǎn)中任意選擇一點(diǎn)，然后把這一點(diǎn)到其他五點(diǎn)間連五條線段，如圖，在這五條線段中，至少有三條線段是同一種顏色，假定是紅色，現(xiàn)在我們?cè)賳为?dú)來研究這三條紅色的線。這三條線段的另一端或許是不同顏色，假設(shè)這三條線段（虛線）中其中一條是紅色的，那么這條紅色的線段和其他兩條紅色的線段便組

11、成了我們所需要的同色三角形，如果這三條線段都是藍(lán)色的，那么這三條線段也組成我們所需要的同色三角形。因而無論怎樣著色，在這六點(diǎn)之間的所有線段中至少能找到一個(gè)同色三角形。例3（六人集會(huì)問題）證明在任意6個(gè)人的集會(huì)上，或者有3個(gè)人以前彼此相識(shí)，或者有三個(gè)人以前彼此不相識(shí)。”例3”：17個(gè)科學(xué)家中每個(gè)人與其余16個(gè)人通信，他們通信所討論的僅有三個(gè)問題，而任兩個(gè)科學(xué)家之間通信討論的是同一個(gè)問題。證明：至少有三個(gè)科學(xué)家通信時(shí)討論的是同一個(gè)問題。解：不妨設(shè)A是某科學(xué)家，他與其余16位討論僅三個(gè)問題，由鴿籠原理知，他至少與其中的6位討論同一問題。設(shè)這6位科學(xué)家為B,C,D,E,F,G,討論的是甲問題。若這6位

12、中有兩位之間也討論甲問題，則結(jié)論成立。否則他們6位只討論乙、丙兩問題。這樣又由鴿籠原理知B至少與另三位討論同一問題，不妨設(shè)這三位是C,D,E,且討論的是乙問題。若C,D,E中有兩人也討論乙問題，則結(jié)論也就成立了。否則，他們間只討論丙問題，這樣結(jié)論也成立。三 .制造抽屜是運(yùn)用原則的一大關(guān)鍵例1從2、4、6、30這15個(gè)偶數(shù)中，任取9個(gè)數(shù)，證明其中一定有兩個(gè)數(shù)之和是34。分析與解答我們用題目中的15個(gè)偶數(shù)制造8個(gè)抽屜：凡是抽屜中有兩個(gè)數(shù)的,都具有一個(gè)共同的特點(diǎn)：這兩個(gè)數(shù)的和是34?，F(xiàn)從題目中的15個(gè)偶數(shù)中任取9個(gè)數(shù),由抽屜原理（因?yàn)槌閷现挥?個(gè)）,必有兩個(gè)數(shù)在同一個(gè)抽屜中.由制造的抽屜的特點(diǎn),這兩

13、個(gè)數(shù)的和是34。例2:從1、2、3、4、19、20這20個(gè)自然數(shù)中，至少任選幾個(gè)數(shù)，就可以保證其中一定包括兩個(gè)數(shù),它們的差是12。分析與解答在這20個(gè)自然數(shù)中，差是12的有以下8對(duì)：20,8,19,7,186,17,5,16,4,15,3,14,2,13,1。另外還有4個(gè)不能配對(duì)的數(shù)9，10，11，12，共制成12個(gè)抽屜（每個(gè)括號(hào)看成一個(gè)抽屜）.只要有兩個(gè)數(shù)取自同一個(gè)抽屜，那么它們的差就等于12，根據(jù)抽屜原理至少任選13個(gè)數(shù)，即可辦到（取12個(gè)數(shù)：從12個(gè)抽屜中各取一個(gè)數(shù)（例如取1,2,3,，12），那么這12個(gè)數(shù)中任意兩個(gè)數(shù)的差必不等于12）。例3：從1到20這20個(gè)數(shù)中,任取11個(gè)數(shù),必有

14、兩個(gè)數(shù),其中一個(gè)數(shù)是另一個(gè)數(shù)的倍數(shù)。分析與解答根據(jù)題目所要求證的問題,應(yīng)考慮按照同一抽屜中,任意兩數(shù)都具有倍數(shù)關(guān)系的原則制造抽屜.把這20個(gè)數(shù)按奇數(shù)及其倍數(shù)分成以下十組,看成10個(gè)抽屜（顯然,它們具有上述性質(zhì)）：1,2,4,8,16,3,6,12,5,10,20,7,14,9,18,11,13,15,17,19。從這10個(gè)數(shù)組的20個(gè)數(shù)中任取11個(gè)數(shù),根據(jù)抽屜原理,至少有兩個(gè)數(shù)取自同一個(gè)抽屜.由于凡在同一抽屜中的兩個(gè)數(shù)都具有倍數(shù)關(guān)系,所以這兩個(gè)數(shù)中,其中一個(gè)數(shù)一定是另一個(gè)數(shù)的倍數(shù)。例4：某校校慶,來了n位校友,彼此認(rèn)識(shí)的握手問候.請(qǐng)你證明無論什么情況,在這n個(gè)校友中至少有兩人握手的次數(shù)一樣多。

15、分析與解答共有n位校友,每個(gè)人握手的次數(shù)最少是0次,即這個(gè)人與其他校友都沒有握過手;最多有n-1次,即這個(gè)人與每位到會(huì)校友都握了手.然而,如果有一個(gè)校友握手的次數(shù)是0次,那么握手次數(shù)最多的不能多于n-2次;如果有一個(gè)校友握手的次數(shù)是n-1次,那么握手次數(shù)最少的不能少于1次.不管是前一種狀態(tài)0、1、2、n-2,還是后一種狀態(tài)1、2、3、n-1，握手次數(shù)都只有n-1種情況.把這n-1種情況看成n-1個(gè)抽屜，到會(huì)的n個(gè)校友每人按照其握手的次數(shù)歸入相應(yīng)的“抽屜”，根據(jù)抽屜原理，至少有兩個(gè)人屬于同一抽屜，則這兩個(gè)人握手的次數(shù)一樣多。在有些問題中，“抽屜”和“物體”不是很明顯的，需要精心制造“抽屜”和“物

16、體”.如何制造“抽屜”和“物體”可能是很困難的，一方面需要認(rèn)真地分析題目中的條件和問題，另一方面需要多做一些題積累經(jīng)驗(yàn)。抽屜原理把八個(gè)蘋果任意地放進(jìn)七個(gè)抽屜里，不論怎樣放，至少有一個(gè)抽屜放有兩個(gè)或兩個(gè)以上的蘋果。抽屜原則有時(shí)也被稱為鴿巢原理，它是德國(guó)數(shù)學(xué)家狄利克雷首先明確的提出來并用以證明一些數(shù)論中的問題，因此，也稱為狄利克雷原則。它是組合數(shù)學(xué)中一個(gè)重要的原理。把它推廣到一般情形有以下幾種表現(xiàn)形式。形式一：證明：設(shè)把n+1個(gè)元素分為n個(gè)集合A1,A2,，An,用al,a2,，an表示這n個(gè)集合里相應(yīng)的元素個(gè)數(shù)，需要證明至少存在某個(gè)ai大于或等于2（用反證法）假設(shè)結(jié)論不成立，即對(duì)每一個(gè)ai都有a

17、i2，則因?yàn)閍i是整數(shù)，應(yīng)有aim+1高斯函數(shù)：對(duì)任意的實(shí)數(shù)x,x表示“不大于x的最大整數(shù)”.例如：3.5=3,2.9=2，卜2.5=-3,7=7,一般地，我們有：xxx+1形式三：證明：設(shè)把n個(gè)元素分為k個(gè)集合A1,A2,，Ak,用a1,a2,，ak表示這k個(gè)集合里相應(yīng)的元素個(gè)數(shù)，需要證明至少存在某個(gè)ai大于或等于n/k。（用反證法）假設(shè)結(jié)論不成立，即對(duì)每一個(gè)ai都有ain/k,于是有：a1+a2+akn/k+n/k+n/k=k?n/kqi形式五：證明：（用反證法）將無窮多個(gè)元素分為有限個(gè)集合,假設(shè)這有限個(gè)集合中的元素的個(gè)數(shù)都是有限個(gè),則有限個(gè)有限數(shù)相加,所得的數(shù)必是有限數(shù),這就與題設(shè)產(chǎn)生矛

18、盾,所以,假設(shè)不成立,故必有一個(gè)集合含有無窮多個(gè)元素。例題1：400人中至少有兩個(gè)人的生日相同.分析：生日從1月1日排到12月31日,共有366個(gè)不相同的生日,我們把366個(gè)不同的生日看作366個(gè)抽屜,400人視為400個(gè)蘋果,由表現(xiàn)形式1可知,至少有兩人在同一個(gè)抽屜里,所以這400人中有兩人的生日相同.解：將一年中的366天視為366個(gè)抽屜,400個(gè)人看作400個(gè)蘋果,由抽屜原理的表現(xiàn)形式1可以得知：至少有兩人的生日相同.例題2：任取5個(gè)整數(shù),必然能夠從中選出三個(gè),使它們的和能夠被3整除.證明：任意給一個(gè)整數(shù),它被3除,余數(shù)可能為0,1,2,我們把被3除余數(shù)為0,1,2的整數(shù)各歸入類r0,r

19、1,r2.至少有一類包含所給5個(gè)數(shù)中的至少兩個(gè).因此可能出現(xiàn)兩種情況：1.某一類至少包含三個(gè)數(shù);2.某兩類各含兩個(gè)數(shù),第三類包含一個(gè)數(shù).若是第一種情況,就在至少包含三個(gè)數(shù)的那一類中任取三數(shù),其和一定能被3整除;若是第二種情況,在三類中各取一個(gè)數(shù),其和也能被3整除.綜上所述,原命題正確.例題3：某校派出學(xué)生204人上山植樹15301株,其中最少一人植樹50株,最多一人植樹100株,則至少有5人植樹的株數(shù)相同.證明：按植樹的多少，從50到100株可以構(gòu)造51個(gè)抽屜，則個(gè)問題就轉(zhuǎn)化為至少有5人植樹的株數(shù)在同一個(gè)抽屜里.（用反證法）假設(shè)無5人或5人以上植樹的株數(shù)在同一個(gè)抽屜里，那只有5人以下植樹的株數(shù)在同一個(gè)抽屜里，而參加植樹的人數(shù)為204人，所以，每個(gè)抽屜最多有4人，故植樹的總株數(shù)最多有：4（50+51+100）=4X=15300n），那么一定有一個(gè)抽屜中放進(jìn)了至少2個(gè)東西。”在上面的第一個(gè)結(jié)論中，由于一年最多有366天，因此在367人中至少有2人出生在同月同日。這相當(dāng)于把367個(gè)東西放入366個(gè)抽屜，至少有2個(gè)東西在同一抽屜里在第二個(gè)結(jié)論中，不妨想象將5雙手套分別編號(hào)，即號(hào)碼為1，2，5的手套各有兩只，同號(hào)的兩只是一雙。任取6只手套，它們的編號(hào)至多有5種，因此其中至少有兩只的號(hào)碼相同。這相當(dāng)于把6個(gè)東西放入5個(gè)抽屜，至少有2