1、本系列共15講第十一講 簡單的抽屜原理文檔貢獻者：與你的緣把3個蘋果任意放到兩個抽屜里，可以有哪些放置的方法呢？一個抽屜放一個，另一個抽屜放兩個；或3個蘋果放在某一個抽屜里。盡管放蘋果的方式有所不同，但是總有一個共同的規律：至少 有一個抽屜里有兩個或兩個以上的蘋果。如果把5個蘋果任意放到4個抽屜里，放置的方法更多了，但仍有這樣的結果。由此我們可 以想到，只要蘋果的個數多于抽屜的個數，就一定能保證至少有一 個抽屜里有兩個或兩個以上的蘋果。道理很簡單：如果每個抽屜里 的蘋果都不到兩個（也就是至多有1個），那么所有抽屜里的蘋果數的和就比總數少了。由此得到：抽屜原理：把多于 n個的蘋果放進n個抽屜里，

2、那么至少有一 個抽屜里有兩個或兩個以上的蘋果。如果把蘋果換成了鴿子，把抽屜換成了籠子，同樣有類似的結 論，所以有時也把抽屜原理叫做鴿籠原理。不要小看這個“原理”， 利用它可以解決一些表面看來似乎很難的數學問題。比如，我們從街上隨便找來13人，就可以斷定他們中至少有兩個人屬相（指鼠、牛、虎、兔等十二種生肖）相同。怎樣證明 這個結論是正確的呢？只要利用抽屜原理就很容易把道理講清楚。事實上，由于人數（ 13）比屬相（ 12）多，因此至少有兩個人屬相 相同（在這里，把 13 個人看成 13 個“蘋果”，把 12 種屬相看成 12 個“抽屜”）。應用抽屜原理要注意識別“抽屜”和“蘋果”，蘋果的數目一 定

3、要大于抽屜的個數。例 1：有 5 個小朋友，每人都從裝有許多黑白圍棋子的布袋中任意 摸出 3枚棋子。請你證明，這 5 個人中至少有兩個小朋友摸出的棋 子的顏色的配組是一樣的。分析與解答 首先要確定 3 枚棋子的顏色可以有多少種不同 的情況，可以有： 3 黑，2黑 1 白，1黑 2 白，3白共 4 種配組情況 ， 看作 4個抽屜， 把每人所拿 3 枚棋子按其顏色配組情況放入相應的 抽屜，由于有 5 個蘋果，比抽屜個數多，所以根據抽屜原理，至少 有兩個蘋果在同一個抽屜里， 也就是他們所拿棋子的顏色配組是一 樣的。例 2：一副撲克牌（去掉兩張王牌） ，每人隨意摸兩張牌，至少有多 少人才能保證他們當中

4、一定有兩人所摸兩張牌的花色情況是相同 的？分析與解答 撲克牌中有方塊、梅花、黑桃、紅桃 4 種花色，2 張牌的花色可以有：2 張方塊，2 張梅花，2 張紅桃，2 張黑桃，1 張方塊 1張黑桃， 1張方塊 1張梅花， 1張方塊 1張紅桃，1張梅花1 張黑桃，1 張梅花 1 張紅桃，1 張黑桃 1 張紅桃共計 10 種情 況。 把這 10 種花色配組看作 10 個抽屜， 只要蘋果的個數比抽屜的個數 多 1 就可以有題目所要的結果。所以至少有 11 人。例 3 證明：任意取 8 個自然數，必有兩個數的差是 7 的倍數。分析與解答 在與整除有關的問題中有這樣的性質， 如果兩個 整數a、b,它們除以自然

5、數 m的余數相同，那么它們的差 ab是m 的倍數。根據這個性質，本題只需要證明這 8個自然數中有 2個自 然數，它們除以 7的余數相同。我們可以把所有自然數按 7除所得 的 7 種不同的余數 0、 1、 2、 3、 4、 5、6 分成七類，也就是 7 個抽 屜。任取 8 個自然數， 根據抽屜原理， 必有兩個數在同一個抽屜中 ， 也就是它們除以 7的余數相同， 因此這兩個數的差一定是 7的倍數 。把所有整數按照除以某個自然數m的余數分為m類，叫做m的剩余類或同余類，用0 , 1 , 2，m1表示。每一個類 含有無窮多個數，例如1中含有 1, m 1, 2m 1, 3m 1,。在 研究與整除有關的

6、問題時，常用剩余類作為抽屜，根據抽屜原理， 可以證明：任意 n+1個自然數中，總有兩個自然數的差是n的倍數。在有些問題中，“抽屜”和“蘋果”不是很明顯的，需要精心 制造“抽屜”和“蘋果”。如果制造“抽屜”和“蘋果”可能是很 困難的，一方面需要認真地分析題目中的條件和問題，另一方面需 要多做一些題積累經驗。例4:從2、4、6、30這15個偶數中，任取9個數，證明其中 一定有兩個數之和是 34。分析與解答 我們用題目中的15個偶數制造8個抽屜：凡是抽屜中有兩個數的，都具有一個共同的特點：這兩個數的 和是34。現從題目中的15個偶數中任取9個數，由抽屜原理（因為抽 屜只有8個），必有兩個數在同一個抽

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

8、數中任意兩個數的差必不等于 12。例 6：從 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 個數，根據抽屜原理，至 少有兩個數取自同一個抽屜， 由于凡在同一抽屜中的兩個數都具有 倍數關系，所以這兩個數中，其中一

9、個數一定是另一個數的倍數。 例 7：證明：在任取的 5 個自然數中，必有 3 個數，它們的和是 3 的倍數。分析與解答 按照被 3 除所得的余數， 把全體自然數分成 3 個剩余類，即構成 3 個抽屜。如何任選的 5 個自然數中，至少有 3 個數在同一個抽屜，那么這 3個數除以3得到相同的余數r，所以它 們的和一定是3的倍數（3r被3整除）。如果每個抽屜至多有 2個選定的數， 那么 5個數在 3 個抽屜中 的分配必為 1 個，2個，2個，即 3 個抽屜中都有選定的數。在每 個抽屜中各取 1個數， 那么這 3 個數除以 3 得到的余數分別為 0、1、 2。因此，它們的和也一定能被3 整除（ 0+1

10、+2 被 3 整除）。例 8：某校校慶，來了 n 位校友，彼此認識的握手問候。請證明無 論什么情況，在這 n 位校友中至少有兩人握手的次數一校多。分析與解答 共有 n 位校友，每個人握手的次數最少是 0 次 ，即這個人與其他校友都沒有握過手；最多有n-1次，即這個人與每位到會校友都握了手。校友人數與握手次數的不同情況（ 0， 1，2,，n1）都是n,還無法用抽屜原理。然而，如果有一個校友握手的次數是 0 次，那么握手次數最多的不能多于n2次；如果有一個校友握手的次數是n1次，那么握手次數最少的不能少于1次。不管是前一種狀態 0、1、2、3、n 2,還是后一種狀態 1、2、3、n 1,握手次數都

11、只有 n1 種情況。把這n1種情況看成n1個抽屜，到會的n個校友每人 按照其握手的次數歸入相應的“抽屜”,根據抽屜原理,至少有兩個人屬于同一抽屜，則這兩個人握手的次數一樣多。習題十一1 某校的小學生年齡最小的 6 歲， 最大的 13 歲，從這個學校中 任選幾位同學就一定保證其中有兩位同學的年齡相同？2 中午食堂有 5 種不同的菜和 4種不同的主食，每人只能買一 種菜和一種主食，請你證明某班在食堂買飯的 21 名學生中， 一定至少有兩名學生所買的菜和主食是一樣的。3 證明：任取 6個自然數，必有兩個數的差是 5 的倍數。4 為了歡迎外賓來校參觀，學校準備了紅色、黃色、綠色的小 旗，每個同學都左右兩手各拿一面彩旗列隊迎接外賓。至少 有多少位同學才能保證其中至少有兩個人不但所拿小旗顏色 一樣，而且（左，右）順序也相同？5 從 10至 20這 11個自然數中，任取 7個數，證明其中一定有 兩個數之和是 29。6. 從1、2、3、