抽屜原則
2009-08-31 11:13:39網(wǎng)絡(luò)來源
大家知道,兩個(gè)抽屜要放置三只蘋果,那么一定有兩只蘋果放在同一個(gè)抽屜里,更一般地說,只要被放置的蘋果數(shù)比抽屜數(shù)目大,就一定會(huì)有兩只或更多只的蘋果放進(jìn)同一個(gè)抽屜,可不要小看這一簡(jiǎn)單事實(shí),它包含著一個(gè)重要而又十分基本的原則——抽屜原則.
1. 抽屜原則有幾種最常見的形式
原則1 如果把n+k(k≥1)個(gè)物體放進(jìn)n只抽屜里,則至少有一只抽屜要放進(jìn)兩個(gè)或更多個(gè)物體:
原則本身十分淺顯,為了加深對(duì)它的認(rèn)識(shí),我們還是運(yùn)用反證法給予證明;如果每個(gè)抽屜至多只能放進(jìn)一個(gè)物體,那么物體的總數(shù)至多是n,而不是題設(shè)的n+k(k≥1),這不可能.
原則雖簡(jiǎn)單.巧妙地運(yùn)用原則卻可十分便利地解決一些看上去相當(dāng)復(fù)雜、甚至感到無從下手的總是,比如說,我們可以斷言在我國(guó)至少有兩個(gè)人出生的時(shí)間相差不超過4秒鐘,這是個(gè)驚人的結(jié)論,該是經(jīng)過很多人的艱苦勞動(dòng),統(tǒng)計(jì)所得的吧!不,只須我們稍動(dòng)手算一下:
不妨假設(shè)人的壽命不超過4萬天(約110歲,超過這個(gè)年齡數(shù)的人為數(shù)甚少),則
10億人口安排在8億6千4百萬個(gè)“抽屜”里,根據(jù)原則1,即知結(jié)論成立.
下面我們?cè)倥e一個(gè)例子:
例1 幼兒園買來了不少白兔、熊貓、長(zhǎng)頸鹿塑料玩具,每個(gè)小朋友任意選擇兩件,那么不管怎樣挑選,在任意七個(gè)小朋友中總有兩個(gè)彼此選的玩具都相同,試說明道理.
解 從三種玩具中挑選兩件,搭配方式只能是下面六種:
(兔、兔),(兔、熊貓),(兔、長(zhǎng)頸鹿),(熊貓、熊貓),(熊貓、長(zhǎng)頸鹿),(長(zhǎng)頸鹿、長(zhǎng)頸鹿)
把每種搭配方式看作一個(gè)抽屜,把7個(gè)小朋友看作物體,那么根據(jù)原則1,至少有兩個(gè)物體要放進(jìn)同一個(gè)抽屜里,也就是說,至少兩人挑選玩具采用同一搭配方式,選的玩具相同.
原則2 如果把mn+k(k≥1)個(gè)物體放進(jìn)n個(gè)抽屜,則至少有一個(gè)抽屜至多放進(jìn)m+1個(gè)物體.證明同原則相仿.若每個(gè)抽屜至多放進(jìn)m個(gè)物體,那么n個(gè)抽屜至多放進(jìn)mn個(gè)物體,與題設(shè)不符,故不可能.
原則1可看作原則2的物例(m=1)
例2正方體各面上涂上紅色或藍(lán)色的油漆(每面只涂一種色),證明正方體一定有三個(gè)面顏色相同.
證明把兩種顏色當(dāng)作兩個(gè)抽屜,把正方體六個(gè)面當(dāng)作物體,那么6=2×2+2,根據(jù)原則二,至少有三個(gè)面涂上相同的顏色.
例3 把1到10的自然數(shù)擺成一個(gè)圓圈,證明一定存在在個(gè)相鄰的數(shù),它們的和數(shù)大于17.
證明 如圖12-1,設(shè)a1,a2,a3,…,a9,a10分別代表不超過10的十個(gè)自然數(shù),它們圍成一個(gè)圈,三個(gè)相鄰的數(shù)的組成是(a1,a2,a3),(a2,a3,a4),(a3,a4,a5),…,(a9,a10,a1),(a10,a1,a2)共十組.現(xiàn)把它們看作十個(gè)抽屜,每個(gè)抽屜的物體數(shù)是a1+a2+a3,a2+a3+a4,a3+a4+a5,…a9+a10+a1,a10+a1+a2,由于
(a1+a2+a3)+(a2+a3+a4)+…+(a9+a10+a1)+(a10+a1+a2)
=3(a1+a2+…+a9+a10)
=3×(1+2+…+9+10)
根據(jù)原則2,至少有一個(gè)括號(hào)內(nèi)的三數(shù)和不少于17,即至少有三個(gè)相鄰的數(shù)的和不小于17.
原則1、原則2可歸結(jié)到期更一般形式:
原則3把m1+m2+…+mn+k(k≥1)個(gè)物體放入n個(gè)抽屜里,那么或在第一個(gè)抽屜里至少放入m1+1個(gè)物體,或在第二個(gè)抽屜里至少放入m2+1個(gè)物體,……,或在第n個(gè)抽屜里至少放入mn+1個(gè)物體.
證明假定第一個(gè)抽屜放入物體的數(shù)不超過m1個(gè),第二個(gè)抽屜放入物體的數(shù)不超過m2個(gè),……,第n個(gè)抽屜放入物體的個(gè)數(shù)不超過mn,那么放入所有抽屜的物體總數(shù)不超過m1+m2+…+mn個(gè),與題設(shè)矛盾.
例4 有紅襪2雙,白襪3雙,黑襪4雙,黃襪5雙,藍(lán)襪6雙(每雙襪子包裝在一起)若取出9雙,證明其中必有黑襪或黃襪2雙.
證明 除可能取出紅襪、白襪3雙外.還至少?gòu)钠渌N顏色的襪子里取出4雙,根據(jù)原理3,必在黑襪或黃襪、藍(lán)襪里取2雙.
上面數(shù)例論證的似乎都是“存在”、“總有”、“至少有”的問題,不錯(cuò),這正是抽屜原則的主要作用.需要說明的是,運(yùn)用抽屜原則只是肯定了“存在”、“總有”、“至少有”,卻不能確切地指出哪個(gè)抽屜里存在多少.
2. 制造抽屜是運(yùn)用原則的一大關(guān)鍵
首先要指出的是,對(duì)于同一問題,常可依據(jù)情況,從不同角度設(shè)計(jì)抽屜,從而導(dǎo)致不同的制造抽屜的方式.
例5 在邊長(zhǎng)為1的正方形內(nèi),任意給定13個(gè)點(diǎn),試證:其中必有4個(gè)點(diǎn),以此4點(diǎn)為頂點(diǎn)的四邊開面積不超過(假定四點(diǎn)在一直線上構(gòu)成面積為零的四邊形).
證明如圖12-2把正方形分成四個(gè)相同的小正方形.
因13=3×4+1,根據(jù)原則2,總有4點(diǎn)落在同一個(gè)小正方形內(nèi)(或邊界上),以此4點(diǎn)為頂點(diǎn)的四邊形的面積不超過小正方形的面積,也就不超過整個(gè)正方形面積的.
事實(shí)上,由于解決問題的核心在于將正方形分割成四個(gè)面積相等的部分,所以還可以把正方形按圖12-3(此處無圖)所示的形式分割.
合理地制造抽屜必須建立在充分考慮問題自身特點(diǎn)的基礎(chǔ)上.
例6 在一條筆直的馬路旁種樹,從起點(diǎn)起,每隔一米種一棵樹,如果把三塊“愛護(hù)樹木”的小牌分別掛在三棵樹上,那么不管怎樣掛,至少有兩棵掛牌的樹之間的距離是偶數(shù)(以米為單位),這是為什么?
解如圖12-4(設(shè)掛牌的三棵樹依次為A、B、C.AB=a,BC=b,若a、b中有一為偶數(shù),命題得證.否則a、b均為奇數(shù),則AC=a+b為偶數(shù),命題得證.
下面我們換一個(gè)角度考慮:給每棵樹上編上號(hào),于是兩棵樹之間的距離就是號(hào)碼差,由于樹的號(hào)碼只能為奇數(shù)和偶數(shù)兩類,那么掛牌的三棵樹號(hào)碼至少有兩個(gè)同為奇數(shù)或偶數(shù),它們的差必為偶數(shù),問題得證.
后一證明十分巧妙,通過編號(hào)碼,將兩樹間距離轉(zhuǎn)化為號(hào)碼差.這種轉(zhuǎn)化的思想方法是一種非常重要的數(shù)學(xué)方法
例7 從自然數(shù)1,2,3,…99,100這100個(gè)數(shù)中隨意取出51個(gè)數(shù)來,求證:其中一定有兩個(gè)數(shù),,它們中的一個(gè)是另一個(gè)的倍數(shù).
分析設(shè)法制造抽屜:(1)不超過50個(gè);(2)每個(gè)抽屜的里的數(shù)(除僅有的一個(gè)外),其中一個(gè)數(shù)是另一個(gè)數(shù)的倍數(shù),一個(gè)自然數(shù)的想法是從數(shù)的質(zhì)因數(shù)表示形式入手.
解設(shè)第一個(gè)抽屜里放進(jìn)數(shù):1,1×2,1×22,1×23,1×24,1×25,1×26;
第二個(gè)抽屜時(shí)放進(jìn)數(shù):3,3×2,3×22,3×23,3×24,3×25;
第三個(gè)抽屜里放進(jìn)數(shù):5,5×2,5×22,5×23,5×24;
………………
第二十五個(gè)抽屜里放進(jìn)數(shù):49,49×2;
第二十六個(gè)抽屜里放進(jìn)數(shù):51.
………………
第五十個(gè)抽屜里放進(jìn)數(shù):99.
那么隨意取出51個(gè)數(shù)中,必有兩個(gè)數(shù)同屬一個(gè)抽屜,其中一個(gè)數(shù)是另一個(gè)數(shù)的倍數(shù).
制造抽屜并非總是一帆風(fēng)順的,有時(shí)要邊制造邊調(diào)整、改進(jìn).
例8 任意給定7個(gè)不同的自然數(shù),求證其中必有兩個(gè)整數(shù),其和或差是10的倍數(shù).
分析注意到這些數(shù)隊(duì)以10的余數(shù)即個(gè)位數(shù)字,以0,1,…,9為標(biāo)準(zhǔn)制造10個(gè)抽屜,標(biāo)以[0],[1],…,[9].若有兩數(shù)落入同一抽屜,其差是10的倍數(shù),只是僅有7個(gè)自然數(shù),似不便運(yùn)用抽屜原則,再作調(diào)整:[6],[7],[8],[9]四個(gè)抽屜分別與[4],[3],[2],[1]合并,則可保證至少有一個(gè)抽屜里有兩個(gè)數(shù),它們的和或差是10的倍數(shù).
3. 較復(fù)雜的問題須反復(fù)地運(yùn)用抽屜原則,將復(fù)雜問題轉(zhuǎn)化為簡(jiǎn)單問題.
例9以(x,y,z)表示三元有序整數(shù)組,其中x、y、z為整數(shù),試證:在任意七個(gè)三元整數(shù)組中,至少有兩個(gè)三元數(shù)組,它們的x、y、z元中有兩對(duì)都是奇數(shù)或都是偶數(shù).
分析 設(shè)七個(gè)三元素組為A1(x1,y1,z1)、A2(x2,y2,z2)、…、A7(x7,y7,z7).現(xiàn)在逐步探索,從x元開始,由抽屜原則,x1,x2,…,x7這七個(gè)數(shù)中,必定有四個(gè)數(shù)具有相同的奇偶性,不妨設(shè)這四個(gè)數(shù)是x1,x2,x3,x4且為偶數(shù),接著集中考慮A1、A2、A3、A4這四組數(shù)的y元,若比如y1,y2,y3,y4中有兩個(gè)是偶數(shù),則問題已證,否則至多有一個(gè)是偶數(shù),比如y4是偶數(shù),這時(shí)我們?cè)賮砑锌紤]A1、A2、A3的z元.在z1,z2,z3中,由抽屜原則必有兩個(gè)數(shù)具有相同的奇偶性,如z1、z2,這時(shí)無論它們是奇數(shù),還是偶數(shù),問題都已得到證明.
下面介紹一個(gè)著名問題.
例10 任選6人,試證其中必有3人,他們互相認(rèn)識(shí)或都不認(rèn)識(shí).
分析 用A、B、C、D、E、F表示這6個(gè)人,首先以A為中心考慮,他與另外五個(gè)人B、C、D、E、F只有兩種可能的關(guān)系:認(rèn)識(shí)或不認(rèn)識(shí),那么由抽屜原則,他必定與其中某三人認(rèn)識(shí)或不認(rèn)識(shí),現(xiàn)不妨設(shè)A認(rèn)識(shí)B、C、D三人,當(dāng)B、C、D三人都互不認(rèn)識(shí)時(shí),問題得證;當(dāng)B、C、D三人中有兩人認(rèn)識(shí),如B、C認(rèn)識(shí)時(shí),則A、B、C互相認(rèn)識(shí),問題也得證.
本例和上例都采用了舍去保留、化繁為簡(jiǎn)、逐步縮小考慮范圍的方法.
例11a,b,c,d為四個(gè)任意給定的整數(shù),求證:以下六個(gè)差數(shù)
b-a,c-a,d-a,c-b,d-b,d-c的乘積一定可以被12整除.
證明 把這6個(gè)差數(shù)的乘積記為p,我們必須且只須證明:3與4都可以整除p,以下分兩步進(jìn)行.
第一步,把a(bǔ),b,c,d按以3為除數(shù)的余數(shù)來分類,這樣的類只有三個(gè),故知a,b,c,d中至少有2個(gè)除以3的余數(shù)相同,例如,不妨設(shè)為a,b,這時(shí)3可整除b-a,從而3可整除p.
第二步,再把a(bǔ),b,c,d按以4為除數(shù)的余數(shù)來分類,這種類至多只有四個(gè),如果a,b,c,d中有二數(shù)除以4的余數(shù)相同,那么與第一步類似,我們立即可作出4可整除p的結(jié)論.
設(shè)a,b,c,d四數(shù)除以4的余數(shù)不同,由此推知,a,b,c,d之中必有二個(gè)奇數(shù)(不妨設(shè)為a,b),也必有二個(gè)偶數(shù)(設(shè)為c,d),這時(shí)b-a為偶數(shù),d-c也是偶數(shù),故4可整除(b-a)(d-c),自然也可得出4可整除p.
如果能進(jìn)一步靈活運(yùn)用原則,不僅制造抽屜,還根據(jù)問題的特征,制造出放進(jìn)抽屜的物體,則更可收到意想不到的效果.
例12 求證:從任意n個(gè)自然數(shù)a1,a2,…,an中可以找到若干個(gè)數(shù),使它們的和是n的倍數(shù).
分析以0,1,…,n-1即被n除的余數(shù)分類制造抽屜的合理的,但把什么樣的數(shù)作為抽屜里的物體呢?扣住“和”,構(gòu)造下列和數(shù):
S1=a1,
S2=a1+a2,
S=a1+a2+a3,
…………
Sn=a1+a2+…+an,
其中任意兩個(gè)和數(shù)之差仍為和數(shù),若他們之中有一是n的倍數(shù),問題得證,否則至少有兩個(gè)數(shù)被n除余數(shù)相同,則它們的差即它們中若干數(shù)(包括1個(gè))的和是n的倍數(shù),問題同樣得證.
例子3(北京1990年高一競(jìng)賽)910瓶紅、藍(lán)墨水,排成130行,每行7瓶,證明:不論怎樣排列,紅藍(lán)墨水瓶的顏色次序必定出現(xiàn)下述兩種情況之一種:
(1)至少有三行完全相同;
(2)至少有兩組(四行)每組的兩行完全相同.
解910瓶紅、藍(lán)墨水排成130行,每行7瓶,對(duì)一行來說,每個(gè)位置上有紅藍(lán)兩種可能,因此,一行的紅、藍(lán)墨水排法有27=128種,對(duì)每一種不同排法設(shè)為一種“行式”,共有128種行式.
現(xiàn)有130行,在其中任取129行,依抽屜原則知,必有兩行A、B行式相同.
除A、B外余下128行,若有一行P與A行式相同,知滿足(1)至少有三行A、B、P完全相同,若在這128行中設(shè)直一行5A行或相同,那么這128行至多有127種行式,依抽屜原則,必有兩行C、D具有相同行式,這樣便找到了(A、B),(C、D)兩組(四行),且兩組兩行完全相同.
練習(xí)十二
1. 一個(gè)籃球運(yùn)動(dòng)員在15分鐘內(nèi)將球投進(jìn)籃圈20次,證明總有某一分鐘他至少投進(jìn)兩次.
2. 有黑、白、黃筷子各8只,不用眼睛看,任意地取出筷子來,使得至少有兩雙筷子不同色,那么至少要取出多少只筷子才能做到?
3. 證明:在1,2,3,…,10這十個(gè)數(shù)中任取六個(gè)數(shù),那么這六個(gè)數(shù)中總可以找到兩個(gè)數(shù),其中一個(gè)是另一個(gè)的倍數(shù).
4. 證明:任意502個(gè)整數(shù)中,必有兩個(gè)整數(shù)的和或差是998的倍數(shù).
5. 任意寫一個(gè)由數(shù)字1,2,3組成的30位數(shù),從這30位數(shù)任意截取相鄰三位,可得一個(gè)三位數(shù),證明:在從各個(gè)不同位置上截得的三位數(shù)中至少有兩個(gè)相等.
6. 證明:把任意10個(gè)自然數(shù)用適當(dāng)?shù)倪\(yùn)算符號(hào)連接起來,運(yùn)算的結(jié)果總能被1890整除.
7. 七條直線兩兩相交,所得的角中至少有一個(gè)角小于26°.
8. 用2種顏色涂3行9列共27個(gè)小方格,證明:不論如何涂色,其中必至少有兩列,它們的涂色方式相同.
9. 用2種顏色涂5×5共25個(gè)小方格,證明:必有一個(gè)四角同色的矩形出現(xiàn).
10. 求證存在形如11…11的一個(gè)數(shù),此數(shù)是1987的倍數(shù).
練習(xí)十二
1.15分鐘里在每一分鐘看作一個(gè)抽屜,20次投籃看作20個(gè)物體,根據(jù)原理一即得.
2.至少要。保敝豢曜樱?yàn)椋保敝豢曜又斜赜幸浑p筷子同色,不妨設(shè)它是黃色,則黑色或白色的筷子至少有3只,其中必有一雙同色,即黑色或白色,故。保敝豢曜幼阋员WC成功.但少于11只不行,如。保爸豢曜,閔可能出現(xiàn)8只黃色,黑白各一只,不合要求.
3.將10個(gè)數(shù)分成5組:(1,7),(2,6),(3,9),(4,8),(5,10).任取六個(gè)數(shù)必有兩個(gè)落入同一組,而同組二數(shù)中一數(shù)是另一數(shù)的倍數(shù).
4.每個(gè)整數(shù)被998除,余數(shù)必是0,1,2,…,997中的一個(gè).把這998?jìng)(gè)余數(shù)制造為(0),(1,997),(2,996),…,(497,501),(498),(499),(500)共501個(gè)抽屜,把502個(gè)整數(shù)按被998除的余數(shù)大小分別放入上述抽屜,必有兩數(shù)進(jìn)入同一抽屜.若余數(shù)相同,那么它們的差是998的倍數(shù),否則和為998的倍數(shù).
5.從各種位置上截得的三位數(shù)有28?jìng)(gè),但由1,2,3組成的不同三位數(shù)有3×3×3=27個(gè),故有兩個(gè)截得的三位數(shù)相同.
6.1890=2×3×5×7×9.將10個(gè)數(shù)記為x1,x2,…,x9,x10.10個(gè)數(shù)中至少有兩個(gè)被9除余數(shù)相同,設(shè)為x1,x2則x1-x2可被9整除.同樣剩下8?jìng)(gè)數(shù)中有兩個(gè)數(shù)的差可被7整除,記為x3-x4,剩下6個(gè)數(shù)中有兩個(gè)數(shù)的差可被5整除,記為x5-x6,剩下4個(gè)數(shù)中有兩個(gè)數(shù)的差可被3整除,記為x7-x8.剩下兩數(shù)x9,x10,若有一數(shù)為偶數(shù),則x9,x10可被2整除,否則x9-x10可被2整除.故乘積(x1-x2)(x3-x4)(x5-x6)(x7-x8)x9·x10與(x1-x2)(x3-x4)(x5-x6)(x7-x8)(x9-x10)二者之一必可被1890整除.
7.任選一點(diǎn)P,過P點(diǎn)分別作各線的平行線,則它們把一周角分成14個(gè)彼此相鄰的角,其中至少有一個(gè)角小于26°.
8.用兩種顏色涂1×3的小方格共有8種方法.現(xiàn)有9列,由抽屜原則,必有兩列涂法一樣.
9.設(shè)兩種顏色為紅、藍(lán),考察第一行的涂色.必有三格同色,不妨設(shè)為紅色,且在左邊三列.現(xiàn)考察左邊三列,若下面四行中某一行有兩格同為紅色,則出現(xiàn)四角同紅色矩形,否則每行僅可能一格染紅色,從而四行中必有二行左邊三列中有兩列同染藍(lán)色,從而得到四角同為藍(lán)色的矩形.
10.考慮1,11,…共1987個(gè)數(shù),其中必有一個(gè)是1987的倍數(shù),否則必有兩數(shù)被1987除余數(shù)相同,其差
是1987的倍數(shù).但10i與1987沒有除1外的因數(shù),故是1987倍數(shù)導(dǎo)致矛盾.