第十一講簡(jiǎn)單的抽屜原理.doc

第十一講 簡(jiǎn)單的抽屜原理把3個(gè)蘋果任意放到兩個(gè)抽屜里，可以有哪些放置的方法呢？一個(gè)抽屜放一個(gè)，另一個(gè)抽屜放兩個(gè)；或3個(gè)蘋果放在某一個(gè)抽屜里。盡管放蘋果的方式有所不同，但是總有一個(gè)共同的規(guī)律：至少有一個(gè)抽屜里有兩個(gè)或兩個(gè)以上的蘋果。如果把5個(gè)蘋果任意放到4個(gè)抽屜里，放置的方法更多了，但仍有這樣的結(jié)果。由此我們可以想到，只要蘋果的個(gè)數(shù)多于抽屜的個(gè)數(shù)，就一定能保證至少有一個(gè)抽屜里有兩個(gè)或兩個(gè)以上的蘋果。道理很簡(jiǎn)單：如果每個(gè)抽屜里的蘋果都不到兩個(gè)（也就是至多有1個(gè)），那么所有抽屜里的蘋果數(shù)的和就比總數(shù)少了。由此得到：抽屜原理：把多于n個(gè)的蘋果放進(jìn)n個(gè)抽屜里，那么至少有一個(gè)抽屜里有兩個(gè)或兩個(gè)以上的蘋果。如果把蘋果換成了鴿子，把抽屜換成了籠子，同樣有類似的結(jié)論，所以有時(shí)也把抽屜原理叫做鴿籠原理。不要小看這個(gè)“原理”，利用它可以解決一些表面看來(lái)似乎很難的數(shù)學(xué)問(wèn)題。比如，我們從街上隨便找來(lái)13人，就可以斷定他們中至少有兩個(gè)人屬相（指鼠、牛、虎、兔等十二種生肖）相同。怎樣證明這個(gè)結(jié)論是正確的呢？只要利用抽屜原理就很容易把道理講清楚。事實(shí)上，由于人數(shù)（13）比屬相（12）多，因此至少有兩個(gè)人屬相相同（在這里，把13個(gè)人看成13個(gè)“蘋果”，把12種屬相看成12個(gè)“抽屜”）。應(yīng)用抽屜原理要注意識(shí)別“抽屜”和“蘋果”，蘋果的數(shù)目一定要大于抽屜的個(gè)數(shù)。例1：有5個(gè)小朋友，每人都從裝有許多黑白圍棋子的布袋中任意摸出3枚棋子。請(qǐng)你證明，這5個(gè)人中至少有兩個(gè)小朋友摸出的棋子的顏色的配組是一樣的。分析與解答 首先要確定3枚棋子的顏色可以有多少種不同的情況，可以有：3黑，2黑1白，1黑2白，3白共4種配組情況，看作4個(gè)抽屜，把每人所拿3枚棋子按其顏色配組情況放入相應(yīng)的抽屜，由于有5個(gè)蘋果，比抽屜個(gè)數(shù)多，所以根據(jù)抽屜原理，至少有兩個(gè)蘋果在同一個(gè)抽屜里，也就是他們所拿棋子的顏色配組是一樣的。例2：一副撲克牌（去掉兩張王牌），每人隨意摸兩張牌，至少有多少人才能保證他們當(dāng)中一定有兩人所摸兩張牌的花色情況是相同的？分析與解答 撲克牌中有方塊、梅花、黑桃、紅桃4種花色，2張牌的花色可以有：2張方塊，2張梅花，2張紅桃，2張黑桃，1張方塊1張黑桃，1張方塊1張梅花，1張方塊1張紅桃，1張梅花1張黑桃，1張梅花1張紅桃，1張黑桃1張紅桃共計(jì)10種情況。把這10種花色配組看作10個(gè)抽屜，只要蘋果的個(gè)數(shù)比抽屜的個(gè)數(shù)多1就可以有題目所要的結(jié)果。所以至少有11人。例3 證明：任意取8個(gè)自然數(shù)，必有兩個(gè)數(shù)的差是7的倍數(shù)。分析與解答 在與整除有關(guān)的問(wèn)題中有這樣的性質(zhì)，如果兩個(gè)整數(shù)a、b，它們除以自然數(shù)m的余數(shù)相同，那么它們的差ab是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ù)。把所有整數(shù)按照除以某個(gè)自然數(shù)m的余數(shù)分為m類，叫做m的剩余類或同余類，用0，1，2，m1表示。每一個(gè)類含有無(wú)窮多個(gè)數(shù)，例如1中含有1，m1，2m1，3m1，。在研究與整除有關(guān)的問(wèn)題時(shí)，常用剩余類作為抽屜，根據(jù)抽屜原理，可以證明：任意n1個(gè)自然數(shù)中，總有兩個(gè)自然數(shù)的差是n的倍數(shù)。在有些問(wèn)題中，“抽屜”和“蘋果”不是很明顯的，需要精心制造“抽屜”和“蘋果”。如果制造“抽屜”和“蘋果”可能是很困難的，一方面需要認(rèn)真地分析題目中的條件和問(wèn)題，另一方面需要多做一些題積累經(jīng)驗(yàn)。例4：從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)，這兩個(gè)數(shù)的和是34。例5：從1、2、3、4、19、20這20個(gè)自然數(shù)中，至少任選幾個(gè)數(shù)，就可以保證其中一定包括兩個(gè)數(shù)，它們的差是12。分析與解答 在這20個(gè)自然數(shù)中，差是12的有以下8對(duì)：20，8，19，718，617，516，415，314，213，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。例6：從1到20這20個(gè)數(shù)中，任取11個(gè)數(shù)，必有兩個(gè)數(shù)，其中一個(gè)數(shù)是另一個(gè)數(shù)的倍數(shù)。分析與解答 根據(jù)題目所要求證的順題，應(yīng)考慮按照同一抽屜中，任意兩數(shù)都具有倍數(shù)關(guān)系的原則制造抽屜，把這20個(gè)數(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ù)。例7：證明：在任取的5個(gè)自然數(shù)中，必有3個(gè)數(shù)，它們的和是3的倍數(shù)。分析與解答 按照被3除所得的余數(shù)，把全體自然數(shù)分成3個(gè)剩余類，即構(gòu)成3個(gè)抽屜。如何任選的5個(gè)自然數(shù)中，至少有3個(gè)數(shù)在同一個(gè)抽屜，那么這3個(gè)數(shù)除以3得到相同的余數(shù)r，所以它們的和一定是3的倍數(shù)（3r被3整除）。如果每個(gè)抽屜至多有2個(gè)選定的數(shù)，那么5個(gè)數(shù)在3個(gè)抽屜中的分配必為1個(gè)，2個(gè)，2個(gè)，即3個(gè)抽屜中都有選定的數(shù)。在每個(gè)抽屜中各取1個(gè)數(shù)，那么這3個(gè)數(shù)除以3得到的余數(shù)分別為0、1、2。因此，它們的和也一定能被3整除（0+1+2被3整除）。例8：某校校慶，來(lái)了n位校友，彼此認(rèn)識(shí)的握手問(wèn)候。請(qǐng)證明無(wú)論什么情況，在這n位校友中至少有兩人握手的次數(shù)一校多。分析與解答 共有n位校友，每個(gè)人握手的次數(shù)最少是0次，即這個(gè)人與其他校友都沒有握過(guò)手；最多有n1次，即這個(gè)人與每位到會(huì)校友都握了手。校友人數(shù)與握手次數(shù)的不同情況（0，1，2，n1）都是n，還無(wú)法用抽屜原理。然而，如果有一個(gè)校友握手的次數(shù)是0次，那么握手次數(shù)最多的不能多于n2次；如果有一個(gè)校友握手的次數(shù)是n1次，那么握手次數(shù)最少的不能少于1次。不管是前一種狀態(tài)0、1、2、3、n2，還是后一種狀態(tài)1、2、3、n1，握手次數(shù)都只有n1種情況。把這n1種情況看成n1個(gè)抽屜，到會(huì)的n個(gè)校友每人按照其握手的次數(shù)歸入相應(yīng)的“抽屜”，根據(jù)抽屜原理，至少有兩個(gè)人屬于同一抽屜，則這兩個(gè)人握手的次數(shù)一樣多。習(xí) 題 十 一1 某校的小學(xué)生年齡最小的6歲，最大的13歲，從這個(gè)學(xué)校中任選幾位同學(xué)就一定保證其中有兩位同學(xué)的年齡相同？2 中午食堂有5種不同的菜和4種不同的主食，每人只能買一種菜和一種主食，請(qǐng)你證明某班在食堂買飯的21名學(xué)生中，一定至少有兩名學(xué)生所買的菜和主食是一樣的。3 證明：任取6個(gè)自然數(shù)，必有兩個(gè)數(shù)的差是5的倍數(shù)。4 為了歡迎外賓來(lái)校參觀，學(xué)校準(zhǔn)備了紅色、黃色、綠色的小旗，每個(gè)同學(xué)都左右兩手各拿一面彩旗列隊(duì)迎接外賓。至少有多少位同學(xué)才能保證其中至少有兩個(gè)人不但所拿小旗顏色一樣，而且（左，右）順序也相同？5 從10至20這11個(gè)自然數(shù)中，任取7個(gè)數(shù)，證明其中一定有兩個(gè)數(shù)之和是29。6 從1、2、3、20這20個(gè)數(shù)中，