桌上有十個蘋果，要把這十個蘋果放到九個抽屜里，無論怎樣放，有的抽屜可以放一個，有的可以放兩個，有的可以放五個，但最終我們會發(fā)現(xiàn)至少我們可以找到一個抽屜里面至少放兩個蘋果。這一現(xiàn)象就是我們所說的抽屜原理。

　　抽屜原理的一般含義為：“如果每個抽屜代表一個集合，每一個蘋果就可以代表一個元素，假如有n+1或多于n+1個元素放到n個集合中去，其中必定至少有一個集合里至少有兩個元素。”

　　抽屜原理有時也被稱為鴿巢原理(“如果有五個鴿子籠，養(yǎng)鴿人養(yǎng)了6只鴿子，那么當鴿子飛回籠中后，至少有一個籠子中裝有2只鴿子”)。它是德國數(shù)學家狄利克雷首先明確的提出來并用以證明一些數(shù)論中的問題，因此，也稱為狄利克雷原理。它是組合數(shù)學中一個重要的原理。

　　一. 抽屜原理最常見的形式

　　原理1 把多于n個的物體放到n個抽屜里，則至少有一個抽屜里有2個或2個以上的物體。

　　[證明](反證法)：如果每個抽屜至多只能放進一個物體，那么物體的總數(shù)至多是n，而不是題設的n+k(k≥1)，這不可能.

　　原理2 把多于mn(m乘以n)個的物體放到n個抽屜里，則至少有一個抽屜里有m+1個或多于m+1個的物體。

　　[證明](反證法)：若每個抽屜至多放進m個物體,那么n個抽屜至多放進mn個物體,與題設不符，故不可能.

　　原理1 2都是第一抽屜原理的表述

　　第二抽屜原理：

　　把(mn-1)個物體放入n個抽屜中，其中必有一個抽屜中至多有(m—1)個物體。

　　[證明](反證法)：若每個抽屜都有不少于m個物體，則總共至少有mn個物體，與題設矛盾，故不可能

　　二.應用抽屜原理解題

　　抽屜原理的內容簡明樸素，易于接受，它在數(shù)學問題中有重要的作用。許多有關存在性的證明都可用它來解決。

　　例1：400人中至少有兩個人的生日相同.

　　解：將一年中的366天視為366個抽屜，400個人看作400個物體，由抽屜原理1可以得知：至少有兩人的生日相同.

　　又如：我們從街上隨便找來13人，就可斷定他們中至少有兩個人屬相相同.

　　“從任意5雙手套中任取6只，其中至少有2只恰為一雙手套。”

　　“從數(shù)1，2，...，10中任取6個數(shù)，其中至少有2個數(shù)為奇偶性不同。”

　　例2：幼兒園買來了不少白兔、熊貓、長頸鹿塑料玩具，每個小朋友任意選擇兩件，那么不管怎樣挑選，在任意七個小朋友中總有兩個彼此選的玩具都相同，試說明道理.

　　解：從三種玩具中挑選兩件，搭配方式只能是下面六種：(兔、兔)，(兔、熊貓)，(兔、長頸鹿)，(熊貓、熊貓)，(熊貓、長頸鹿)，(長頸鹿、長頸鹿)。把每種搭配方式看作一個抽屜，把7個小朋友看作物體，那么根據原理1，至少有兩個物體要放進同一個抽屜里，也就是說，至少兩人挑選玩具采用同一搭配方式，選的玩具相同.

　　上面數(shù)例論證的似乎都是“存在”、“總有”、“至少有”的問題，不錯，這正是抽屜原則的主要作用.(需要說明的是，運用抽屜原則只是肯定了“存在”、“總有”、“至少有”，卻不能確切地指出哪個抽屜里存在多少.)

　　抽屜原理雖然簡單，但應用卻很廣泛，它可以解答很多有趣的問題，其中有些問題還具有相當?shù)碾y度。下面我們來研究有關的一些問題。

　　(一) 整除問題

　　把所有整數(shù)按照除以某個自然數(shù)m的余數(shù)分為m類，叫做m的剩余類或同余類，用[0]，[1]， [2]，…，[m-1]表示.每一個類含有無窮多個數(shù)，例如[1]中含有1，m+1，2m+1，3m+1，….在研究與整除有關的問題時，常用剩余類作為抽屜.根據抽屜原理，可以證明：任意n+1個自然數(shù)中，總有兩個自然數(shù)的差是n的倍數(shù)。

　　例1 證明：任取8個自然數(shù)，必有兩個數(shù)的差是7的倍數(shù)。

　　分析與解答在與整除有關的問題中有這樣的性質，如果兩個整數(shù)a、b，它們除以自然數(shù)m的余數(shù)相同，那么它們的差a-b是m的倍數(shù).根據這個性質，本題只需證明這8個自然數(shù)中有2個自然數(shù)，它們除以7的余數(shù)相同.我們可以把所有自然數(shù)按被7除所得的7種不同的余數(shù)0、1、2、3、4、5、6分成七類.也就是7個抽屜. 任取8個自然數(shù)，根據抽屜原理，必有兩個數(shù)在同一個抽屜中，也就是它們除以7的余數(shù)相同，因此這兩個數(shù)的差一定是7的倍數(shù)。

　　例2：對于任意的五個自然數(shù)，證明其中必有3個數(shù)的和能被3整除.

　　證明∵任何數(shù)除以3所得余數(shù)只能是0，1，2，不妨分別構造為3個抽屜：

　　[0]，[1]，[2]

　�、偃暨@五個自然數(shù)除以3后所得余數(shù)分別分布在這3個抽屜中(即抽屜中分別為含有余數(shù)為0,1,2的數(shù))，我們從這三個抽屜中各取1個(如1~5中取3,4,5)，其和(3+4+5=12)必能被3整除.

　�、谌暨@5個余數(shù)分布在其中的兩個抽屜中，則其中必有一個抽屜，包含有3個余數(shù)(抽屜原理)，而這三個余數(shù)之和或為0，或為3，或為6，故所對應的3個自然數(shù)之和是3的倍數(shù).

　�、廴暨@5個余數(shù)分布在其中的一個抽屜中，很顯然，必有3個自然數(shù)之和能被3整除.

　　例2′：對于任意的11個整數(shù)，證明其中一定有6個數(shù)，它們的和能被6整除.

　　證明：設這11個整數(shù)為：a1，a2，a3……a11 又6=2×3

　�、傧瓤紤]被3整除的情形

　　由例2知，在11個任意整數(shù)中，必存在：

　　3|a1+a2+a3，不妨設a1+a2+a3=b1;

　　同理，剩下的8個任意整數(shù)中，由例2，必存在：3 | a4+a5+a6.設a4+a5+a6=b2;

　　同理，其余的5個任意整數(shù)中，有：3|a7+a8+a9，設：a7+a8+a9=b3

　�、谠倏紤]b1、b2、b3被2整除.

　　依據抽屜原理，b1、b2、b3這三個整數(shù)中，至少有兩個是同奇或同偶，這兩個同奇(或同偶)的整數(shù)之和必為偶數(shù).不妨設2|b1+b2

　　則：6|b1+b2，即：6|a1+a2+a3+a4+a5+a6

　　∴任意11個整數(shù)，其中必有6個數(shù)的和是6的倍數(shù).

　　例3： 任意給定7個不同的自然數(shù)，求證其中必有兩個整數(shù)，其和或差是10的倍數(shù).

　　分析：注意到這些數(shù)隊以10的余數(shù)即個位數(shù)字，以0，1，…，9為標準制造10個抽屜，標以 [0]，[1]，…，[9].若有兩數(shù)落入同一抽屜，其差是10的倍數(shù)，只是僅有7個自然數(shù)，似不便運用抽屜原則，再作調整：[6]，[7]，[8]， [9]四個抽屜分別與[4]，[3]，[2]，[1]合并，則可保證至少有一個抽屜里有兩個數(shù)，它們的和或差是10的倍數(shù).

　　(二)面積問題

　　例：九條直線中的每一條直線都將正方形分成面積比為2:3的梯形，證明：這九條直線中至少有三條經過同一點.

　　證明：如圖，設直線EF將正方形分成兩個梯形，作中位線MN。由于這兩個梯形的高相等，故它們的面積之比等于中位線長的比，即|MH|:|NH| 。于是點H有確定的位置(它在正方形一對對邊中點的連線上，且|MH|:|NH|=2:3). 由幾何上的對稱性，這種點共有四個(即圖中的H、J、I、K).已知的九條適合條件的分割直線中的每一條必須經過H、J、I、K這四點中的一點.把H、 J、I、K看成四個抽屜，九條直線當成9個物體，即可得出必定有3條分割線經過同一點.

　　(三)染色問題

　　例1正方體各面上涂上紅色或藍色的油漆(每面只涂一種色)，證明正方體一定有三個面顏色相同.

　　證明：把兩種顏色當作兩個抽屜，把正方體六個面當作物體，那么6=2×2+2，根據原理二，至少有三個面涂上相同的顏色.

　　例2 有5個小朋友，每人都從裝有許多黑白圍棋子的布袋中任意摸出3枚棋子.請你證明，這5個人中至少有兩個小朋友摸出的棋子的顏色的配組是一樣的。

　　分析與解答首先要確定3枚棋子的顏色可以有多少種不同的情況，可以有：3黑，2黑1白，1黑2白，3白共4種配組情況，看作4個抽屜.根據抽屜原理，至少有兩個小朋友摸出的棋子的顏色在同一個抽屜里，也就是他們所拿棋子的顏色配組是一樣的。

　　例3：假設在一個平面上有任意六個點，無三點共線，每兩點用紅色或藍色的線段連起來，都連好后，問你能不能找到一個由這些線構成的三角形，使三角形的三邊同色?

　　解：首先可以從這六個點中任意選擇一點，然后把這一點到其他五點間連五條線段，如圖，在這五條線段中，至少有三條線段是同一種顏色，假定是紅色，現(xiàn)在我們再單獨來研究這三條紅色的線。這三條線段的另一端或許是不同顏色，假設這三條線段(虛線)中其中一條是紅色的，那么這條紅色的線段和其他兩條紅色的線段便組成了我們所需要的同色三角形，如果這三條線段都是藍色的，那么這三條線段也組成我們所需要的同色三角形。因而無論怎樣著色，在這六點之間的所有線段中至少能找到一個同色三角形。

　　例3′(六人集會問題)證明在任意6個人的集會上，或者有3個人以前彼此相識，或者有三個人以前彼此不相識。”

　　例3”：17個科學家中每個人與其余16個人通信，他們通信所討論的僅有三個問題，而任兩個科學家之間通信討論的是同一個問題。證明：至少有三個科學家通信時討論的是同一個問題。

　　解：不妨設A是某科學家，他與其余16位討論僅三個問題，由鴿籠原理知，他至少與其中的6位討論同一問題。設這6位科學家為B，C，D，E，F(xiàn)，G，討論的是甲問題。

　　若這6位中有兩位之間也討論甲問題，則結論成立。否則他們6位只討論乙、丙兩問題。這樣又由鴿籠原理知B至少與另三位討論同一問題，不妨設這三位是C，D，E，且討論的是乙問題。

　　若C，D，E中有兩人也討論乙問題，則結論也就成立了。否則，他們間只討論丙問題，這樣結論也成立。

　　三.制造抽屜是運用原則的一大關鍵

　　例1 從2、4、6、…、30這15個偶數(shù)中，任取9個數(shù)，證明其中一定有兩個數(shù)之和是34。

　　分析與解答 我們用題目中的15個偶數(shù)制造8個抽屜：

　　凡是抽屜中有兩個數(shù)的，都具有一個共同的特點：這兩個數(shù)的和是34�，F(xiàn)從題目中的15個偶數(shù)中任取9個數(shù)，由抽屜原理(因為抽屜只有8個)，必有兩個數(shù)在同一個抽屜中.由制造的抽屜的特點，這兩個數(shù)的和是34。

　　例2：從1、2、3、4、…、19、20這20個自然數(shù)中，至少任選幾個數(shù)，就可以保證其中一定包括兩個數(shù)，它們的差是12。

　　分析與解答在這20個自然數(shù)中，差是12的有以下8對：{20，8｝，{19，7｝，{18，6｝，{17，5｝，{16，4｝，{15，3｝，{14，2｝，{13，1｝。

　　另外還有4個不能配對的數(shù){9｝，{10｝，{11｝，{12｝，共制成12個抽屜(每個括號看成一個抽屜).只要有兩個數(shù)取自同一個抽屜，那么它們的差就等于12，根據抽屜原理至少任選13個數(shù)，即可辦到(取12個數(shù)：從12個抽屜中各取一個數(shù)(例如取1，2，3，…，12)，那么這12個數(shù)中任意兩個數(shù)的差必不等于12)。

　　例3： 從1到20這20個數(shù)中，任取11個數(shù)，必有兩個數(shù)，其中一個數(shù)是另一個數(shù)的倍數(shù)。

　　分析與解答根據題目所要求證的問題，應考慮按照同一抽屜中，任意兩數(shù)都具有倍數(shù)關系的原則制造抽屜.把這20個數(shù)按奇數(shù)及其倍數(shù)分成以下十組，看成10個抽屜(顯然，它們具有上述性質)：

　　{1，2，4，8，16｝，{3，6，12｝，{5，10，20｝，{7，14｝，{9，18｝，{11｝，{13｝，{15｝，{17｝，{19｝。

　　從這10個數(shù)組的20個數(shù)中任取11個數(shù)，根據抽屜原理，至少有兩個數(shù)取自同一個抽屜.由于凡在同一抽屜中的兩個數(shù)都具有倍數(shù)關系，所以這兩個數(shù)中，其中一個數(shù)一定是另一個數(shù)的倍數(shù)。

　　例4：某校校慶，來了n位校友，彼此認識的握手問候.請你證明無論什么情況，在這n個校友中至少有兩人握手的次數(shù)一樣多。

　　分析與解答共有n位校友，每個人握手的次數(shù)最少是0次，即這個人與其他校友都沒有握過手;最多有n-1次，即這個人與每位到會校友都握了手.然而，如果有一個校友握手的次數(shù)是0次，那么握手次數(shù)最多的不能多于n-2次;如果有一個校友握手的次數(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個抽屜，到會的n個校友每人按照其握手的次數(shù)歸入相應的“抽屜”，根據抽屜原理，至少有兩個人屬于同一抽屜，則這兩個人握手的次數(shù)一樣多。

　　在有些問題中，“抽屜”和“物體”不是很明顯的，需要精心制造“抽屜”和“物體”.如何制造“抽屜”和“物體”可能是很困難的，一方面需要認真地分析題目中的條件和問題，另一方面需要多做一些題積累經驗。

　　抽屜原理

　　把八個蘋果任意地放進七個抽屜里，不論怎樣放，至少有一個抽屜放有兩個或兩個以上的蘋果。抽屜原則有時也被稱為鴿巢原理，它是德國數(shù)學家狄利克雷首先明確的提出來并用以證明一些數(shù)論中的問題，因此，也稱為狄利克雷原則。它是組合數(shù)學中一個重要的原理。把它推廣到一般情形有以下幾種表現(xiàn)形式。

　　形式一：證明：設把n+1個元素分為n個集合A1，A2，…，An，用a1，a2，…，an表示這n個集合里相應的元素個數(shù)，需要證明至少存在某個ai大于或等于2(用反證法)假設結論不成立，即對每一個ai都有ai<2，則因為ai是整數(shù)，應有ai≤1，于是有：

　　a1+a2+…+an≤1+1+…+1=n

　　形式二：設把n•m+1個元素分為n個集合A1，A2，…，An，用a1，a2，…，an表示這n個集合里相應的元素個數(shù)，需要證明至少存在某個ai大于或等于m+1。用反證法)假設結論不成立，即對每一個ai都有ai

　　a1+a2+…+an≤m+m+…+m=n•m

　　n個m 這與題設相矛盾。所以，至少有存在一個ai≥m+1

　　高斯函數(shù)：對任意的實數(shù)x,[x]表示“不大于x的最大整數(shù)”.

　　例如：[3.5]=3，[2.9]=2，[-2.5]=-3，[7]=7，……一般地，我們有：[x]≤x<[x]+1

　　形式三：證明：設把n個元素分為k個集合A1，A2，…，Ak，用a1，a2，…，ak表示這k個集合里相應的元素個數(shù)，需要證明至少存在某個ai大于或等于[n/k]。(用反證法)假設結論不成立，即對每一個ai都有ai<[n/k]，于是有：

　　a1+a2+…+ak<[n/k]+[n/k]+…+[n/k] =k•[n/k]≤k•(n/k)=n

　　k個[n/k] ∴ a1+a2+…+ak

　　形式四：證明：設把q1+q2+…+qn-n+1個元素分為n個集合A1，A2，…，An，用 a1，a2，…，an表示這n個集合里相應的元素個數(shù)，需要證明至少存在某個i，使得ai大于或等于qi。(用反證法)假設結論不成立，即對每一個ai都有ai

　　所以，假設不成立，故必有一個i,在第i個集合中元素個數(shù)ai≥qi

　　形式五：證明：(用反證法)將無窮多個元素分為有限個集合，假設這有限個集合中的元素的個數(shù)都是有限個，則有限個有限數(shù)相加，所得的數(shù)必是有限數(shù)，這就與題設產生矛盾，所以，假設不成立，故必有一個集合含有無窮多個元素。

　　例題1：400人中至少有兩個人的生日相同.分析：生日從1月1日排到12月31日，共有366個不相同的生日，我們把366個不同的生日看作366個抽屜，400人視為400個蘋果，由表現(xiàn)形式1可知，至少有兩人在同一個抽屜里，所以這400人中有兩人的生日相同.

　　解：將一年中的366天視為366個抽屜，400個人看作400個蘋果，由抽屜原理的表現(xiàn)形式1可以得知：至少有兩人的生日相同.

　　例題2：任取5個整數(shù)，必然能夠從中選出三個，使它們的和能夠被3整除.

　　證明：任意給一個整數(shù)，它被3除，余數(shù)可能為0，1，2，我們把被3除余數(shù)為0，1，2的整數(shù)各歸入類r0，r1，r2.至少有一類包含所給5個數(shù)中的至少兩個.因此可能出現(xiàn)兩種情況：1°.某一類至少包含三個數(shù);2°.某兩類各含兩個數(shù)，第三類包含一個數(shù).

　　若是第一種情況，就在至少包含三個數(shù)的那一類中任取三數(shù)，其和一定能被3整除;若是第二種情況，在三類中各取一個數(shù)，其和也能被3整除..綜上所述，原命題正確.

　　例題3：某校派出學生204人上山植樹15301株，其中最少一人植樹50株，最多一人植樹100株，則至少有5人植樹的株數(shù)相同.

　　證明：按植樹的多少，從50到100株可以構造51個抽屜，則個問題就轉化為至少有5人植樹的株數(shù)在同一個抽屜里.

　　(用反證法)假設無5人或5人以上植樹的株數(shù)在同一個抽屜里，那只有5人以下植樹的株數(shù)在同一個抽屜里，而參加植樹的人數(shù)為204人，所以，每個抽屜最多有4人，故植樹的總株數(shù)最多有：

　　4(50+51+…+100)=4× =15300<15301得出矛盾.因此，至少有5人植樹的株數(shù)相同.

　　練習：1.邊長為1的等邊三角形內有5個點，那么這5個點中一定有距離小于0.5的兩點.

　　2.邊長為1的等邊三角形內，若有n2+1個點，則至少存在2點距離小于 .

　　3.求證：任意四個整數(shù)中，至少有兩個整數(shù)的差能夠被3整除.

　　4.某校高一某班有50名新生，試說明其中一定有二人的熟人一樣多.

　　5.某個年級有202人參加考試，滿分為100分，且得分都為整數(shù)，總得分為10101分，則至少有3人得分相同.

　　“任意367個人中，必有生日相同的人。”

　　“從任意5雙手套中任取6只，其中至少有2只恰為一雙手套。”

　　“從數(shù)1，2，...，10中任取6個數(shù)，其中至少有2個數(shù)為奇偶性不同。”

　　... ...

　　大家都會認為上面所述結論是正確的。這些結論是依據什么原理得出的呢?這個原理叫做抽屜原理。它的內容可以用形象的語言表述為：

　　“把m個東西任意分放進n個空抽屜里(m>n)，那么一定有一個抽屜中放進了至少2個東西。”

　　在上面的第一個結論中，由于一年最多有366天，因此在367人中至少有2人出生在同月同日。 這相當于把367個東西放入 366個抽屜，至少有2個東西在同一抽屜里。在第二個結論中，不妨想象將5雙手套分別編號，即號碼為1，2，...，5的手套各有兩只，同號的兩只是一雙。任取6只手套，它們的編號至多有5種，因此其中至少有兩只的號碼相同。這相當于把6個東西放入5個抽屜，至少有2個東西在同一抽屜里。

　　抽屜原理的一種更一般的表述為：

　　“把多于kn+1個東西任意分放進n個空抽屜(k是正整數(shù))，那么一定有一個抽屜中放進了至少k+1個東西。”

　　利用上述原理容易證明：“任意7個整數(shù)中，至少有3個數(shù)的兩兩之差是3的倍數(shù)。”因為任一整數(shù)除以3時余數(shù)只有0、1、2三種可能，所以7個整數(shù)中至少有3個數(shù)除以3所得余數(shù)相同，即它們兩兩之差是3的倍數(shù)。

　　如果問題所討論的對象有無限多個，抽屜原理還有另一種表述：

　　“把無限多個東西任意分放進n個空抽屜(n是自然數(shù))，那么一定有一個抽屜中放進了無限多個東西。”

　　抽屜原理的內容簡明樸素，易于接受，它在數(shù)學問題中有重要的作用。許多有關存在性的證明都可用它來解決。

　　1958年6/7月號的《美國數(shù)學月刊》上有這樣一道題目：

　　“證明在任意6個人的集會上，或者有3個人以前彼此相識，或者有三個人以前彼此不相識。”

　　這個問題可以用如下方法簡單明了地證出：

　　在平面上用6個點A、B、C、D、E、F分別代表參加集會的任意6個人。如果兩人以前彼此認識，那么就在代表他們的兩點間連成一條紅線;否則連一條藍線�？紤]A點與其余各點間的5條連線AB，AC，...，AF，它們的顏色不超過2種。根據抽屜原理可知其中至少有3條連線同色，不妨設AB，AC，AD同為紅色。如果BC，BD ，CD 3條連線中有一條(不妨設為BC)也為紅色，那么三角形ABC即一個紅色三角形，A、B、C代表的3個人以前彼此相識：如果BC、BD、CD 3條連線全為藍色，那么三角形BCD即一個藍色三角形，B、C、D代表的3個人以前彼此不相識。不論哪種情形發(fā)生，都符合問題的結論。

　　六人集會問題是組合數(shù)學中著名的拉姆塞定理的一個最簡單的特例，這個簡單問題的證明思想可用來得出另外一些深入的結論。這些結論構成了組合數(shù)學中的重要內容-----臘姆塞理論。從六人集會問題的證明中，我們又一次看到了抽屜原理的應用。