第3講：抽屜原理

高一數(shù)學(xué)拓展講座第3講：抽屜原理抽屜原則大家知道，兩個(gè)抽屜要放置三只蘋果，那么一定有兩只蘋果放在同一個(gè)抽屜里，更一般地說，只要被放置的蘋果數(shù)比抽屜數(shù)目大，就一定會(huì)有兩只或更多只的蘋果放進(jìn)同一個(gè)抽屜，可不要小看這一簡單事實(shí)，它包含著一個(gè)重要而又十分基本的原則——抽屜原則.1．

抽屜原則有幾種最常見的形式如果把n+k(k≥1)個(gè)物體放進(jìn)n只抽屜里，則至少有一只抽屜要放進(jìn)兩個(gè)或更多個(gè)物體：原則本身十分淺顯，為了加深對它的認(rèn)識(shí)，我們還是運(yùn)用反證法給予證明；如果每個(gè)抽屜至多只能放進(jìn)一個(gè)物體，那么物體的總數(shù)至多是n，而不是題設(shè)的n+k(k≥1)，這不可能.原則一：不妨假設(shè)人的壽命不超過4萬天（約110歲，超過這個(gè)年齡數(shù)的人為數(shù)甚少），則10億人口安排在8億6千4百萬個(gè)“抽屜”里，根據(jù)原則1，即知結(jié)論成立.原則雖簡單.巧妙地運(yùn)用原則卻可十分便利地解決一些看上去相當(dāng)復(fù)雜、甚至感到無從下手的總是，比如說，我們可以斷言在我國至少有兩個(gè)人出生的時(shí)間相差不超過4秒鐘，這是個(gè)驚人的結(jié)論，該是經(jīng)過很多人的艱苦勞動(dòng)，統(tǒng)計(jì)所得的吧！不，只須我們稍動(dòng)手算一下：幼兒園買來了不少白兔、熊貓、長頸鹿塑料玩具，每個(gè)小朋友任意選擇兩件，那么不管怎樣挑選，在任意七個(gè)小朋友中總有兩個(gè)彼此選的玩具都相同，試說明道理.下面我們再舉一個(gè)例子：例1

：解：從三種玩具中挑選兩件，搭配方式只能是下面六種：（兔、兔），（兔、熊貓），（兔、長頸鹿），（熊貓、熊貓），（熊貓、長頸鹿），（長頸鹿、長頸鹿）把每種搭配方式看作一個(gè)抽屜，把7個(gè)小朋友看作物體，那么根據(jù)原則1，至少有兩個(gè)物體要放進(jìn)同一個(gè)抽屜里，也就是說，至少兩人挑選玩具采用同一搭配方式，選的玩具相同.如果把mn+k(k≥1)個(gè)物體放進(jìn)n個(gè)抽屜，則至少有一個(gè)抽屜至多放進(jìn)m+1個(gè)物體.證明同原則一相仿.若每個(gè)抽屜至多放進(jìn)m個(gè)物體,那么n個(gè)抽屜至多放進(jìn)mn個(gè)物體,與題設(shè)不符，故不可能.（原則1可看作原則2的特例（m=1））例2：正方體各面上涂上紅色或藍(lán)色的油漆（每面只涂一種色），證明正方體一定有三個(gè)面顏色相同.原則二：把兩種顏色當(dāng)作兩個(gè)抽屜，把正方體六個(gè)面當(dāng)作物體，那么6=2×2+2，根據(jù)原則二，至少有三個(gè)面涂上相同的顏色.證明：證明:如圖12-1，設(shè)a1，a2，a3，…，a9，a10分別代表不超過10的十個(gè)自然數(shù)，它們圍成一個(gè)圈，三個(gè)相鄰的數(shù)的組成是（a1，a2，a3），（a2，a3，a4），（a3，a4，a5），…,（a9，a10，a1）,（a10，a1，a2）共十組.現(xiàn)把它們看作十個(gè)抽屜，每個(gè)抽屜的物體數(shù)是a1+a2+a3，a2+a3+a4，a3+a4+a5，…a9+a10+a1，a10+a1+a2,由于（a1+a2+a3）+（a2+a3+a4）+…+（a9+a10+a1）+（a10+a1+a2）=3(a1+a2+…+a9+a10)=3×(1+2+…+9+10)根據(jù)原則2,至少有一個(gè)括號內(nèi)的三數(shù)和不少于17,即至少有三個(gè)相鄰的數(shù)的和不小于17.例3把1到10的自然數(shù)擺成一個(gè)圓圈，證明一定存在在個(gè)相鄰的數(shù)，它們的和數(shù)大于17.原則3:把m1+m2+…+mn+k(k≥1)個(gè)物體放入n個(gè)抽屜里，那么或在第一個(gè)抽屜里至少放入m1+1個(gè)物體，或在第二個(gè)抽屜里至少放入m2+1個(gè)物體，……，或在第n個(gè)抽屜里至少放入mn+1個(gè)物體.證明假定第一個(gè)抽屜放入物體的數(shù)不超過m1個(gè)，第二個(gè)抽屜放入物體的數(shù)不超過m2個(gè)，……，第n個(gè)抽屜放入物體的個(gè)數(shù)不超過mn，那么放入所有抽屜的物體總數(shù)不超過m1+m2+…+mn個(gè)，與題設(shè)矛盾.原則1、原則2可歸結(jié)到期更一般形式：證明:除可能取出紅襪、白襪3雙外.還至少從其它三種顏色的襪子里取出4雙，根據(jù)原理3，必在黑襪或黃襪、藍(lán)襪里取2雙.例4:有紅襪2雙，白襪3雙，黑襪4雙，黃襪5雙，藍(lán)襪6雙（每雙襪子包裝在一起）若取出9雙，證明其中必有黑襪或黃襪2雙.上面數(shù)例論證的似乎都是“存在”、“總有”、“至少有”的問題，不錯(cuò)，這正是抽屜原則的主要作用.需要說明的是，運(yùn)用抽屜原則只是肯定了“存在”、“總有”、“至少有”，卻不能確切地指出哪個(gè)抽屜里存在多少.說明：1.抽屜原理的實(shí)質(zhì)性思想是：把一些東西分成若干份，那么必有一份不少于平均數(shù)，也必有一份不多于平均數(shù).2.把無限個(gè)東西分成有限份，必有一份有無限個(gè)東西.

練習(xí)：任取5個(gè)整數(shù)，必然能夠從中選出三個(gè)，使它們的和能夠被3整除.證明：任意給一個(gè)整數(shù)，它被3除，余數(shù)可能為0，1，2，我們把被3除余數(shù)為0，1，2的整數(shù)分類為r０，r1，r2.至少有一類包含所給５個(gè)數(shù)中的至少兩個(gè).因此可能出現(xiàn)兩種情況：a某一類至少包含三個(gè)數(shù)；b某兩類各含兩個(gè)數(shù)，第三類包含一個(gè)數(shù).若是第一種情況，就在至少包含三個(gè)數(shù)的那一類中任取三數(shù)，其和一定能被3整除；若是第二種情況，在三類中各取一個(gè)數(shù)，其和也能被3整除.綜上所述，原命題正確.首先要指出的是，對于同一問題，?？梢罁?jù)情況，從不同角度設(shè)計(jì)抽屜，從而導(dǎo)致不同的制造抽屜的方式.2．

制造抽屜是運(yùn)用原則的一大關(guān)鍵例5.邊長為1的正方形中，任意放入9個(gè)點(diǎn)，任何3點(diǎn)不共線，求證：這9個(gè)點(diǎn)中任取3個(gè)點(diǎn)組成的三角形中，至少有一個(gè)的面積不超過1/8.解：將邊長為1的正方形等分成邊長為

的四個(gè)小正方形，視這四個(gè)正方形為抽屜，9個(gè)點(diǎn)任意放入這四個(gè)正方形中，必有三點(diǎn)落入同一個(gè)正方形內(nèi).現(xiàn)特別取出這個(gè)正方形來加以討論.把落在這個(gè)正方形中的三點(diǎn)記為D、E、F.通過這三點(diǎn)中的任意一點(diǎn)（如E）作平行線，如圖可知：×h＋＝＝S△DEF＝S△DEG＋S△EFG≤EDFG事實(shí)上，由于解決問題的核心在于將正方形分割成四個(gè)面積相等的部分，所以還可以把正方形按圖12-3所示的形式分割.合理地制造抽屜必須建立在充分考慮問題自身特點(diǎn)的基礎(chǔ)上.例6在一條筆直的馬路旁種樹，從起點(diǎn)起，每隔一米種一棵樹，如果把三塊“愛護(hù)樹木”的小牌分別掛在三棵樹上，那么不管怎樣掛，至少有兩棵掛牌的樹之間的距離是偶數(shù)（以米為單位），這是為什么？下面我們換一個(gè)角度考慮：給每棵樹上編上號，于是兩棵樹之間的距離就是號碼差，由于樹的號碼只能為奇數(shù)和偶數(shù)兩類，那么掛牌的三棵樹號碼至少有兩個(gè)同為奇數(shù)或偶數(shù)，它們的差必為偶數(shù)，后一證明十分巧妙，通過編號碼，將兩樹間距離轉(zhuǎn)化為號碼差.這種轉(zhuǎn)化的思想方法是一種非常重要的數(shù)學(xué)方法解:如圖12-4（設(shè)掛牌的三棵樹依次為A、B、C.AB=a，BC=b，若a、b中有一為偶數(shù)，命題得證.否則a、b均為奇數(shù)，則AC=a+b為偶數(shù)，命題得證.問題得證.

1947年，匈牙利數(shù)學(xué)家把這一原理引進(jìn)到中學(xué)生數(shù)學(xué)競賽中，當(dāng)年匈牙利全國數(shù)學(xué)競賽有一道這樣的試題：“證明：任何六個(gè)人中，一定可以找到三個(gè)互相認(rèn)識(shí)的人，或者三個(gè)互不認(rèn)識(shí)的人。”

如果B、C、D三人互不認(rèn)識(shí)，那么我們就找到了三個(gè)互不認(rèn)識(shí)的人；如果B、C、D三人中有兩個(gè)互相認(rèn)識(shí)，例如B與C認(rèn)識(shí)，那么，A、B、C就是三個(gè)互相認(rèn)識(shí)的人。

用A、B、C、D、E、F代表六個(gè)人，從中隨便找一個(gè)，例如A，把其余五個(gè)人放到“與A認(rèn)識(shí)”和“與A不認(rèn)識(shí)”兩個(gè)“抽屜”里去，根據(jù)抽屜原理，至少有一個(gè)抽屜里有三個(gè)人。不妨假定在“與A認(rèn)識(shí)”的抽屜里有三個(gè)人，他們是B、C、D。Ramsey定理設(shè)空間6個(gè)點(diǎn)任意4點(diǎn)不共面，若將其中任意兩點(diǎn)間的連線染成紅色或藍(lán)色之一，則必存在一個(gè)三邊顏色相同的三角形.<拓展>：證明：從一個(gè)已知點(diǎn)A出發(fā)的5條線段被染成紅藍(lán)兩種顏色，由抽屜原理可知其中必有

條線段同色，不妨設(shè)他們是AB,AC,AD,并且同染為紅色。考察三角形BCD,若其中有一邊為紅色，例如BD為紅色，則三角形ABD各邊都為紅色，結(jié)論成立！否則，三角形BCD的三邊都為藍(lán)色，結(jié)論也成立.有17位科學(xué)家，其中每位科學(xué)家都同其他所有人通信，他們在通信時(shí)只討論了三個(gè)題目，且每兩位科學(xué)家之間只討論一個(gè)題目，證明:至少有三位科學(xué)家，他們互相之間討論的是同一個(gè)題目（第6屆IMO試題）練習(xí)：考慮以A1為端點(diǎn)的線段A1A2,A1A3,…，A1A17，這16條線段被染成了3種顏色，由抽屜原理知這16條線段中至少有6條同色，不妨設(shè)A1A2，A1A3，…，A1A7為紅色.現(xiàn)考查連結(jié)六點(diǎn)A2，A3，…，A7的15條線段，如其中至少有一條紅色線段，則同色（紅色）三角形已出現(xiàn)；如沒有紅色線段，則這15條線段只有藍(lán)色和黃色，由Ramsey定理知一定存在以這15條線段中某三條為邊的同色三角形（同為藍(lán)色或同為黃色）.這都表示對應(yīng)的3位科學(xué)家，他們之間討論的是同一個(gè)問題。問題得證！證明:在圓周上任取17個(gè)點(diǎn)A1,A2,…，A17分別表示17位科學(xué)家.設(shè)他們討論的題目為x,y,z,兩位科學(xué)家討論x連紅線,討論y連藍(lán)線,討論z連黃線.于是只須證明以這17個(gè)點(diǎn)為頂點(diǎn)的三角形中有一同色三角形.練習(xí)：從自然數(shù)1，2，3，…99，100這100個(gè)數(shù)中隨意取出51個(gè)數(shù)來，求證：其中一定有兩個(gè)數(shù)，，它們中的一個(gè)是另一個(gè)的倍數(shù).分析:設(shè)法制造抽屜：（1）不超過50個(gè)；（2）每個(gè)抽屜的里的數(shù)（除僅有的一個(gè)外），其中一個(gè)數(shù)是另一個(gè)數(shù)的倍數(shù)，一個(gè)自然數(shù)的想法是從數(shù)的質(zhì)因數(shù)表示形式入手.解:設(shè)第一個(gè)抽屜里放進(jìn)數(shù)：1，1×2，1×22，1×23，1×24，1×25，1×26；第二個(gè)抽屜時(shí)放進(jìn)數(shù)：3，3×2，3×22，3×23，3×24，3×25；第三個(gè)抽屜里放進(jìn)數(shù)：5，5×2，5×22，5×23，5×24；………………第二十五個(gè)抽屜里放進(jìn)數(shù)：49，49×2；第二十六個(gè)抽屜里放進(jìn)數(shù)：51.………………第五十個(gè)抽屜里放進(jìn)數(shù)：99.那么隨意取出51個(gè)數(shù)中，必有兩個(gè)數(shù)同屬一個(gè)抽屜，其中一個(gè)數(shù)是另一個(gè)數(shù)的倍數(shù).制造抽屜并非總是一帆風(fēng)順的，有時(shí)要邊制造邊調(diào)整、改進(jìn).練習(xí)：任意給定7個(gè)不同的自然數(shù)，求證其中必有兩個(gè)整數(shù)，其和或差是10的倍數(shù).分析:注意到這些數(shù)隊(duì)以10的余數(shù)即個(gè)位數(shù)字，以0，1，…，9為標(biāo)準(zhǔn)制造10個(gè)抽屜，標(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ù).分析:設(shè)七個(gè)三元素組為A1（x1，y1，z1）、A2（x2，y2，z2）、…、A7（x7，y7，z7）.現(xiàn)在逐步探索，從x元開始，由抽屜原則，x1，x2，…，x7這七個(gè)數(shù)中，必定有四個(gè)數(shù)具有相同的奇偶性，不妨設(shè)這四個(gè)數(shù)是x1，x2，x3，x4且為偶數(shù)，接著集中考慮A1、A2、A3、A4這四組數(shù)的y元，若比如y1，y2，y3，y4中有兩個(gè)是偶數(shù)，則問題已證，否則至多有一個(gè)是偶數(shù)，比如y4是偶數(shù)，這時(shí)我們再來集中考慮A1、A2、A3的z元.在z1，z2，z3中，由抽屜原則必有兩個(gè)數(shù)具有相同的奇偶性，如z1、z2，這時(shí)無論它們是奇數(shù)，還是偶數(shù)，問題都已得到證明.3．

較復(fù)雜的問題須反復(fù)地運(yùn)用抽屜原則，將復(fù)雜問題轉(zhuǎn)化為簡單問題.練習(xí)：以（x，y，z）表示三元有序整數(shù)組，其中x、y、z為整數(shù)，試證：在任意七個(gè)三元整數(shù)組中，至少有兩個(gè)三元數(shù)組，它們的x、y、z元中有兩對都是奇數(shù)或都是偶數(shù).設(shè)a，b，c，d四數(shù)除以4的余數(shù)不同，由此推知，a，b，c，d之中必有二個(gè)奇數(shù)（不妨設(shè)為a，b），也必有二個(gè)偶數(shù)（設(shè)為c，d），這時(shí)b-a為偶數(shù)，d-c也是偶數(shù)，故4可整除(b-a)(d-c)，自然也可得出4可整除p.練習(xí)：

a，b，c，d為四個(gè)任意給定的整數(shù)，求證：以下六個(gè)差數(shù)b-a，c-a，d-a，c-b，d-b，d-c的乘積一定可以被12整除.證明

:把這6個(gè)差數(shù)的乘積記為p，我們必須且只須證明：3與4都可以整除p，以下分兩步進(jìn)行.第一步，把a(bǔ)，b，c，d按以3為除數(shù)的余數(shù)來分類，這樣的類只有三個(gè)，故知a，b，c，d中至少有2個(gè)除以3的余數(shù)相同，例如，不妨設(shè)為a，b，這時(shí)3可整除b-a，從而3可整除p.第二步，再把a(bǔ)，b，c，d按以4為除數(shù)的余數(shù)來分類，這種類至多只有四個(gè)，如果a，b，c，d中有二數(shù)除以4的余數(shù)相同，那么與第一步類似，我們立即可作出4可整除p的結(jié)論.如果能進(jìn)一步靈活運(yùn)用原則，不僅制造抽屜，還根據(jù)問題的特征，制造出放進(jìn)抽屜的物體，則更可收到意想不到的效果.練習(xí)：求證：從任意n個(gè)自然數(shù)a1，a2，…，a