數學！抽屜定律~~

桌上有十個蘋果，要把這十個蘋果放到九個抽屜裏，無論怎樣放，有的抽屜可以放壹個，有的可以放兩個，有的可以放五個，但最終我們會發現至少我們可以找到壹個抽屜裏面至少放兩個蘋果。這壹現象就是我們所說的抽屜原理。 抽屜原理的壹般含義為：“如果每個抽屜代表壹個集合，每壹個蘋果就可以代表壹個元素，假如有n＋1或多於n＋1個元素放到n個集合中去，其中必定至少有壹個集合裏至少有兩個元素。” 抽屜原理有時也被稱為鴿巢原理（“如果有五個鴿子籠，養鴿人養了6只鴿子，那麽當鴿子飛回籠中後，至少有壹個籠子中裝有2只鴿子”）。它是德國數學家狄利克雷首先明確的提出來並用以證明壹些數論中的問題，因此，也稱為狄利克雷原理。它是組合數學中壹個重要的原理。 壹． 抽屜原理最常見的形式 原理1 把多於n個的物體放到n個抽屜裏，則至少有壹個抽屜裏有2個或2個以上的物體。 [證明]（反證法）：如果每個抽屜至多只能放進壹個物體，那麽物體的總數至多是n，而不是題設的n+k(k≥1)，這不可能. 原理2 把多於mn個的物體放到n個抽屜裏，則至少有壹個抽屜裏有m+1個或多於m+1個的物體。 [證明]（反證法）：若每個抽屜至多放進m個物體,那麽n個抽屜至多放進mn個物體,與題設不符，故不可能. 原理1 2都是第壹抽屜原理的表述 第二抽屜原理： 把（mn－1）個物體放入n個抽屜中，其中必有壹個抽屜中至多有（m—1）個物體。 [證明]（反證法）：若每個抽屜都有不少於m個物體，則總***至少有mn個物體，與題設矛盾，故不可能 二．應用抽屜原理解題 抽屜原理的內容簡明樸素，易於接受，它在數學問題中有重要的作用。許多有關存在性的證明都可用它來解決。 例1：400人中至少有兩個人的生日相同. 解：將壹年中的366天視為366個抽屜，400個人看作400個物體，由抽屜原理1可以得知：至少有兩人的生日相同. 又如：我們從街上隨便找來13人，就可斷定他們中至少有兩個人屬相相同. “從任意5雙手套中任取6只，其中至少有2只恰為壹雙手套。” “從數1，2，...，10中任取6個數，其中至少有2個數為奇偶性不同。” 例2： 幼兒園買來了不少白兔、熊貓、長頸鹿塑料玩具，每個小朋友任意選擇兩件，那麽不管怎樣挑選，在任意七個小朋友中總有兩個彼此選的玩具都相同，試說明道理. 解 ：從三種玩具中挑選兩件，搭配方式只能是下面六種：（兔、兔），（兔、熊貓），（兔、長頸鹿），（熊貓、熊貓），（熊貓、長頸鹿），（長頸鹿、長頸鹿）。把每種搭配方式看作壹個抽屜，把7個小朋友看作物體，那麽根據原理1，至少有兩個物體要放進同壹個抽屜裏，也就是說，至少兩人挑選玩具采用同壹搭配方式，選的玩具相同. 上面數例論證的似乎都是“存在”、“總有”、“至少有”的問題，不錯，這正是抽屜原則的主要作用.（需要說明的是，運用抽屜原則只是肯定了“存在”、“總有”、“至少有”，卻不能確切地指出哪個抽屜裏存在多少.） 抽屜原理雖然簡單，但應用卻很廣泛，它可以解答很多有趣的問題，其中有些問題還具有相當的難度。下面我們來研究有關的壹些問題。 （壹） 整除問題 把所有整數按照除以某個自然數m的余數分為m類，叫做m的剩余類或同余類，用[0]，[1]，[2]，…，[m-1]表示.每壹個類含有無窮多個數，例如[1]中含有1，m+1，2m＋1，3m＋1，….在研究與整除有關的問題時，常用剩余類作為抽屜.根據抽屜原理，可以證明：任意n+1個自然數中，總有兩個自然數的差是n的倍數。 例1 證明：任取8個自然數，必有兩個數的差是7的倍數。 分析與解答 在與整除有關的問題中有這樣的性質，如果兩個整數a、b，它們除以自然數m的余數相同，那麽它們的差a-b是m的倍數.根據這個性質，本題只需證明這8個自然數中有2個自然數，它們除以7的余數相同.我們可以把所有自然數按被7除所得的7種不同的余數0、1、2、3、4、5、6分成七類.也就是7個抽屜.任取8個自然數，根據抽屜原理，必有兩個數在同壹個抽屜中，也就是它們除以7的余數相同，因此這兩個數的差壹定是7的倍數。 例2：對於任意的五個自然數，證明其中必有3個數的和能被3整除. 證明∵任何數除以3所得余數只能是0，1，2，不妨分別構造為3個抽屜： [0]，[1]，[2] ①若這五個自然數除以3後所得余數分別分布在這3個抽屜中，我們從這三個抽屜中各取1個，其和必能被3整除. ②若這5個余數分布在其中的兩個抽屜中，則其中必有壹個抽屜，包含有3個余數（抽屜原理），而這三個余數之和或為0，或為3，或為6，故所對應的3個自然數之和是3的倍數. ③若這5個余數分布在其中的壹個抽屜中，很顯然，必有3個自然數之和能被3整除. 例2′：對於任意的11個整數，證明其中壹定有6個數，它們的和能被6整除. 證明：設這11個整數為：a1，a2，a3……a11 又6=2×3 ①先考慮被3整除的情形 由例2知，在11個任意整數中，必存在： 3|a1+a2+a3，不妨設a1+a2+a3=b1； 同理，剩下的8個任意整數中，由例2，必存在：3 | a4+a5+a6.設a4+a5+a6=b2； 同理，其余的5個任意整數中，有：3|a7+a8+a9，設：a7+a8+a9=b3 ②再考慮b1、b2、b3被2整除. 依據抽屜原理，b1、b2、b3這三個整數中，至少有兩個是同奇或同偶，這兩個同奇（或同偶）的整數之和必為偶數.不妨設2|b1+b2 則：6|b1+b2，即：6|a1+a2+a3+a4+a5+a6 ∴任意11個整數，其中必有6個數的和是6的倍數. 例3： 任意給定7個不同的自然數，求證其中必有兩個整數，其和或差是10的倍數. 分析：註意到這些數隊以10的余數即個位數字，以0，1，…，9為標準制造10個抽屜，標以[0]，[1]，…，[9].若有兩數落入同壹抽屜，其差是10的倍數，只是僅有7個自然數，似不便運用抽屜原則，再作調整：[6]，[7]，[8]，[9]四個抽屜分別與[4]，[3]，[2]，[1]合並，則可保證至少有壹個抽屜裏有兩個數，它們的和或差是10的倍數. （二）面積問題 例：九條直線中的每壹條直線都將正方形分成面積比為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：假設在壹個平面上有任意六個點，無三點***線，每兩點用紅色或藍色的線段連起來，都連好後，問妳能不能找到壹個由這些線構成的三角形，使三角形的三邊同色？ 解：首先可以從這六個點中任意選擇壹點，然後把這壹點到其他五點間連五條線段，如圖，在這五條線段中，至少有三條線段是同壹種顏色，假定是紅色，現在我們再單獨來研究這三條紅色的線。這三條線段的另壹端或許是不同顏色，假設這三條線段（虛線）中其中壹條是紅色的，那麽這條紅色的線段和其他兩條紅色的線段便組成了我們所需要的同色三角形，如果這三條線段都是藍色的，那麽這三條線段也組成我們所需要的同色三角形。因而無論怎樣著色，在這六點之間的所有線段中至少能找到壹個同色三角形。 例3′（六人集會問題）證明在任意6個人的集會上，或者有3個人以前彼此相識，或者有三個人以前彼此不相識。” 例3”：17個科學家中每個人與其余16個人通信，他們通信所討論的僅有三個問題，而任兩個科學家之間通信討論的是同壹個問題。證明：至少有三個科學家通信時討論的是同壹個問題。 解：不妨設A是某科學家，他與其余16位討論僅三個問題，由鴿籠原理知，他至少與其中的6位討論同壹問題。設這6位科學家為B，C，D，E，F，G，討論的是甲問題。 若這6位中有兩位之間也討論甲問題，則結論成立。否則他們6位只討論乙、丙兩問題。這樣又由鴿籠原理知B至少與另三位討論同壹問題，不妨設這三位是C，D，E，且討論的是乙問題。 若C，D，E中有兩人也討論乙問題，則結論也就成立了。否則，他們間只討論丙問題，這樣結論也成立。 三．制造抽屜是運用原則的壹大關鍵 例1 從2、4、6、…、30這15個偶數中，任取9個數，證明其中壹定有兩個數之和是34。 分析與解答 我們用題目中的15個偶數制造8個抽屜： 凡是抽屜中有兩個數的，都具有壹個***同的特點：這兩個數的和是34。現從題目中的15個偶數中任取9個數，由抽屜原理（因為抽屜只有8個），必有兩個數在同壹個抽屜中.由制造的抽屜的特點，這兩個數的和是34。 例2：從1、2、3、4、…、19、20這20個自然數中，至少任選幾個數，就可以保證其中壹定包括兩個數，它們的差是12。 分析與解答在這20個自然數中，差是12的有以下8對：｛20，8｝，｛19，7｝，｛18，6｝，｛17，5｝，｛16，4｝，｛15，3｝，｛14，2｝，｛13，1｝。 另外還有4個不能配對的數｛9｝，｛10｝，｛11｝，｛12｝，***制成12個抽屜（每個括號看成壹個抽屜）.只要有兩個數取自同壹個抽屜，那麽它們的差就等於12，根據抽屜原理至少任選13個數，即可辦到（取12個數：從12個抽屜中各取壹個數（例如取1，2，3，…，12），那麽這12個數中任意兩個數的差必不等於12）。 例3： 從1到20這20個數中，任取11個數，必有兩個數，其中壹個數是另壹個數的倍數。 分析與解答 根據題目所要求證的問題，應考慮按照同壹抽屜中，任意兩數都具有倍數關系的原則制造抽屜.把這20個數按奇數及其倍數分成以下十組，看成10個抽屜（顯然，它們具有上述性質）： ｛1，2，4，8，16｝，｛3，6，12｝，｛5，10，20｝，｛7，14｝，｛9，18｝，｛11｝，｛13｝，｛15｝，｛17｝，｛19｝。 從這10個數組的20個數中任取11個數，根據抽屜原理，至少有兩個數取自同壹個抽屜.由於凡在同壹抽屜中的兩個數都具有倍數關系，所以這兩個數中，其中壹個數壹定是另壹個數的倍數。 例4：某校校慶，來了n位校友，彼此認識的握手問候.請妳證明無論什麽情況，在這n個校友中至少有兩人握手的次數壹樣多。 分析與解答 ***有n位校友，每個人握手的次數最少是0次，即這個人與其他校友都沒有握過手；最多有n-1次，即這個人與每位到會校友都握了手.然而，如果有壹個校友握手的次數是0次，那麽握手次數最多的不能多於n-2次；如果有壹個校友握手的次數是n-1次，那麽握手次數最少的不能少於1次.不管是前壹種狀態0、1、2、…、n-2，還是後壹種狀態1、2、3、…、n-1，握手次數都只有n-1種情況.把這n-1種情況看成n-1個抽屜，到會的n個校友每人按照其握手的次數歸入相應的“抽屜”，根據抽屜原理，至少有兩個人屬於同壹抽屜，則這兩個人握手的次數壹樣多。 在有些問題中，“抽屜”和“物體”不是很明顯的，需要精心制造“抽屜”和“物體”.如何制造“抽屜”和“物體”可能是很困難的，壹方面需要認真地分析題目中的條件和問題，另壹方面需要多做壹些題積累經驗。