抽屜問題,在數學問題中有一類與「存在性」有關的問題,如367個人中至少有兩個人是同一天過生日,這類問題在生活中非常常見,它所依據的理論,我們稱之為「抽屜原理」。抽屜原理又名狄利克雷原則,是符合某種條件的對象存在性問題有力工具。那麼我們一起來看看什麼事抽屜原理。
一、【抽屜問題的數量關係】
基本的抽屜原則是:如果把n+1個物體(也叫元素)放到n個抽屜中,那麼至少有一個抽屜中放著2個或更多的物體(元素)。抽屜原則可以推廣為:如果有m個抽屜,元素的個數是抽屜個數的k倍多一些,那麼至少有一個抽屜要放(k+1)個或更多的元素。
二、【抽屜問題的解題思路和方法】
目前,處理抽屜原理問題最基本和常用的方法是運用「最不利原則」,構造「最不利」「點最背」的情形。
例1:不透明的箱子中有紅、黃、藍、綠四種顏色的球各20個,一次至少摸出多少個球才能保證摸出兩個相同顏色的球?
分析:解決這個問題要考慮最不利的情況,因為有4種顏色,想要摸出兩個相同顏色的球。那麼最不利的情況就是,每種顏色的各摸出一個,這時再摸一個球,一定與前幾個球有顏色相同的。因此至少要摸4+1=5(個)球。
例2:袋子中有2個紅球,3個黃球,4個籃球,5個綠球,一次至少摸出多少個球就能保證摸到兩種顏色的球?
分析:解決這個問題要考慮最不利情況,想要摸出兩種顏色的球,最不利的情況應該是將一種顏色的球都拿出來時,不論接下來摸的球是什麼顏色都與之前顏色不同。因為4種球的個數各不相同,所以最不利的情況應該是先將個數最多的球都拿出來,接下來摸的球都一定與之前顏色不同。因此至少摸出5+1=6(個)球
例3:一次數學競賽共5道選擇題,評分標準為:基礎分5分,答對一題得3分,答錯扣1分,不答不得分。要保證至少有4人得分相同,最少需要多少人參加競賽?
分析:1、本題考察的是抽屜原理的相關知識,解決本題的關鍵是要知道得分一共有多少種不同的情況,進而從最壞的情況開始考慮解決問題。
2、一共有5題,且有5分的基礎分,那麼每道題就有1分的基礎分。也就相當於答對一題得4分,答錯不得分,不答得1分。
這次數學競賽的得分情況有以下幾種:
5題全對的只有1種情況:得20分;
對4題的有2種情況:1題答錯得16分,1題沒答得17分;
對3題的有3種情況:2題全錯得12分,只錯1題得13分,2題不做得14分;
對2題的有4種情況:3題全錯得8分,只錯2題得9分,只錯1題得10分;3題全不答得11分;
對1題的有5種情況:4題全錯得4分,只錯3題得5分,只錯2題得6分,只錯1題得7分,4題全不答得8分;
答對0題有6 種情況:5題全錯得0分;錯4題得1分,錯3題得2分,錯2題得3分,錯1題得4分,5題全不答得5分。
我們發現從0分到20分,只有19分、18分、15分這三個分數沒有,其它都有,所以一共有20+1-3=18(種)不同的得分。
要保證有四人得分相同,最少需要18×3+1 = 55(人)參加競賽。
抽屜原理雖然簡單,但應用卻很廣泛,它可以解答很多有趣的問題,其中有些問題還具有相當的難度。下面我們來研究有關的一些問題。
(一)整除問題
把所有整數按照除以某個自然數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的倍數.
(二)面積問題
(三)染色問題
例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個校友每人按照其握手的次數歸入相應的「抽屜」,根據抽屜原理,至少有兩個人屬於同一抽屜,則這兩個人握手的次數一樣多。
在有些問題中,「抽屜」和「物體」不是很明顯的,需要精心製造「抽屜」和「物體」.如何製造「抽屜」和「物體」可能是很困難的,一方面需要認真地分析題目中的條件和問題,另一方面需要多做一些題積累經驗。