抽屜原則

大家知道，兩個(gè)抽屜要放置三只蘋果，那么一定有兩只蘋果放在同一個(gè)抽屜里，更一般地說(shuō)，只要被放置的蘋果數(shù)比抽屜數(shù)目大，就一定會(huì)有兩只或更多只的蘋果放進(jìn)同一個(gè)抽屜，可不要小看這一簡(jiǎn)單事實(shí)，它包含著一個(gè)重要而又十分基本的原則——抽屜原則.

1．  抽屜原則有幾種最常見(jiàn)的形式

原則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ù)雜、甚至感到無(wú)從下手的總是，比如說(shuō)，我們可以斷言在我國(guó)至少有兩個(gè)人出生的時(shí)間相差不超過(guò)4秒鐘，這是個(gè)驚人的結(jié)論，該是經(jīng)過(guò)很多人的艱苦勞動(dòng)，統(tǒng)計(jì)所得的吧！不，只須我們稍動(dòng)手算一下：

不妨假設(shè)人的壽命不超過(guò)4萬(wàn)天（約110歲，超過(guò)這個(gè)年齡數(shù)的人為數(shù)甚少），則

10億人口安排在8億6千4百萬(wàn)個(gè)“抽屜”里，根據(jù)原則1，即知結(jié)論成立.

下面我們?cè)倥e一個(gè)例子：
例1  幼兒園買來(lái)了不少白兔、熊貓、長(zhǎng)頸鹿塑料玩具，每個(gè)小朋友任意選擇兩件，那么不管怎樣挑選，在任意七個(gè)小朋友中總有兩個(gè)彼此選的玩具都相同，試說(shuō)明道理.

解 從三種玩具中挑選兩件，搭配方式只能是下面六種：

（兔、兔），（兔、熊貓），（兔、長(zhǎng)頸鹿），（熊貓、熊貓），（熊貓、長(zhǎng)頸鹿），（長(zhǎng)頸鹿、長(zhǎng)頸鹿）

把每種搭配方式看作一個(gè)抽屜，把7個(gè)小朋友看作物體，那么根據(jù)原則1，至少有兩個(gè)物體要放進(jìn)同一個(gè)抽屜里，也就是說(shuō)，至少兩人挑選玩具采用同一搭配方式，選的玩具相同.

原則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è)a₁，a₂，a₃，…，a₉，a₁₀分別代表不超過(guò)10的十個(gè)自然數(shù)，它們圍成一個(gè)圈，三個(gè)相鄰的數(shù)的組成是（a₁，a₂，a₃），（a₂，a₃，a₄），（a₃，a₄，a₅），…,（a₉，a₁₀，a₁）,（a₁₀，a₁，a₂）共十組.現(xiàn)把它們看作十個(gè)抽屜，每個(gè)抽屜的物體數(shù)是a₁+a₂+a₃，a₂+a₃+a₄，a₃+a₄+a₅，…a₉+a₁₀+a₁，a₁₀+a₁+a₂,由于

（a₁+a₂+a₃）+（a₂+a₃+a₄）+…+（a₉+a₁₀+a₁）+（a₁₀+a₁+a₂）

=3(a₁+a₂+…+a₉+a₁₀)

=3×(1+2+…+9+10)

根據(jù)原則2,至少有一個(gè)括號(hào)內(nèi)的三數(shù)和不少于17,即至少有三個(gè)相鄰的數(shù)的和不小于17.

原則1、原則2可歸結(jié)到期更一般形式：
原則3把m₁+m₂+…+m_n+k(k≥1)個(gè)物體放入n個(gè)抽屜里，那么或在第一個(gè)抽屜里至少放入m₁+1個(gè)物體，或在第二個(gè)抽屜里至少放入m₂+1個(gè)物體，……，或在第n個(gè)抽屜里至少放入m_n+1個(gè)物體.

證明假定第一個(gè)抽屜放入物體的數(shù)不超過(guò)m₁個(gè)，第二個(gè)抽屜放入物體的數(shù)不超過(guò)m₂個(gè)，……，第n個(gè)抽屜放入物體的個(gè)數(shù)不超過(guò)m_n，那么放入所有抽屜的物體總數(shù)不超過(guò)m₁+m₂+…+m_n個(gè)，與題設(shè)矛盾.

例4 有紅襪2雙，白襪3雙，黑襪4雙，黃襪5雙，藍(lán)襪6雙（每雙襪子包裝在一起）若取出9雙，證明其中必有黑襪或黃襪2雙.

證明 除可能取出紅襪、白襪3雙外.還至少?gòu)钠渌�三種顏色的襪子里取出4雙，根據(jù)原理3，必在黑襪或黃襪、藍(lán)襪里取2雙.

上面數(shù)例論證的似乎都是“存在”、“總有”、“至少有”的問(wèn)題，不錯(cuò)，這正是抽屜原則的主要作用.需要說(shuō)明的是，運(yùn)用抽屜原則只是肯定了“存在”、“總有”、“至少有”，卻不能確切地指出哪個(gè)抽屜里存在多少.

2．  制造抽屜是運(yùn)用原則的一大關(guān)鍵

首先要指出的是，對(duì)于同一問(wèn)題，�？梢罁�(jù)情況，從不同角度設(shè)計(jì)抽屜，從而導(dǎo)致不同的制造抽屜的方式.

例5 在邊長(zhǎng)為1的正方形內(nèi)，任意給定13個(gè)點(diǎn)，試證：其中必有4個(gè)點(diǎn)，以此4點(diǎn)為頂點(diǎn)的四邊開(kāi)面積不超過(guò)（假定四點(diǎn)在一直線上構(gòu)成面積為零的四邊形）.

證明如圖12-2把正方形分成四個(gè)相同的小正方形.

因13=3×4+1，根據(jù)原則2，總有4點(diǎn)落在同一個(gè)小正方形內(nèi)（或邊界上），以此4點(diǎn)為頂點(diǎn)的四邊形的面積不超過(guò)小正方形的面積，也就不超過(guò)整個(gè)正方形面積的.

事實(shí)上，由于解決問(wèn)題的核心在于將正方形分割成四個(gè)面積相等的部分，所以還可以把正方形按圖12-3（此處無(wú)圖）所示的形式分割.

合理地制造抽屜必須建立在充分考慮問(wèn)題自身特點(diǎn)的基礎(chǔ)上.

例6 在一條筆直的馬路旁種樹，從起點(diǎn)起，每隔一米種一棵樹，如果把三塊“愛(ài)護(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ù)，問(wèn)題得證.

后一證明十分巧妙，通過(guò)編號(hào)碼，將兩樹間距離轉(zhuǎn)化為號(hào)碼差.這種轉(zhuǎn)化的思想方法是一種非常重要的數(shù)學(xué)方法

例7 從自然數(shù)1，2，3，…99，100這100個(gè)數(shù)中隨意取出51個(gè)數(shù)來(lái)，求證：其中一定有兩個(gè)數(shù)，，它們中的一個(gè)是另一個(gè)的倍數(shù).

分析設(shè)法制造抽屜：（1）不超過(guò)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×2²，1×2³，1×2⁴，1×2⁵，1×2⁶；

第二個(gè)抽屜時(shí)放進(jìn)數(shù)：3，3×2，3×2²，3×2³，3×2⁴，3×2⁵；

第三個(gè)抽屜里放進(jìn)數(shù)：5，5×2，5×2²，5×2³，5×2⁴；

………………

第二十五個(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ù)雜的問(wèn)題須反復(fù)地運(yùn)用抽屜原則，將復(fù)雜問(wèn)題轉(zhuǎn)化為簡(jiǎn)單問(wèn)題.

例9以（x，y，z）表示三元有序整數(shù)組，其中x、y、z為整數(shù)，試證：在任意七個(gè)三元整數(shù)組中，至少有兩個(gè)三元數(shù)組，它們的x、y、z元中有兩對(duì)都是奇數(shù)或都是偶數(shù).

分析 設(shè)七個(gè)三元素組為A₁（x₁，y₁，z₁）、A₂（x₂，y₂，z₂）、…、A₇（x₇，y₇，z₇）.現(xiàn)在逐步探索，從x元開(kāi)始，由抽屜原則，x₁，x2，…，x₇這七個(gè)數(shù)中，必定有四個(gè)數(shù)具有相同的奇偶性，不妨設(shè)這四個(gè)數(shù)是x₁，x₂，x₃，x₄且為偶數(shù)，接著集中考慮A₁、A₂、A₃、A₄這四組數(shù)的y元，若比如y₁，y₂，y₃，y₄中有兩個(gè)是偶數(shù)，則問(wèn)題已證，否則至多有一個(gè)是偶數(shù)，比如y₄是偶數(shù)，這時(shí)我們?cè)賮?lái)集中考慮A₁、A₂、A₃的z元.在z₁，z₂，z₃中，由抽屜原則必有兩個(gè)數(shù)具有相同的奇偶性，如z₁、z₂，這時(shí)無(wú)論它們是奇數(shù)，還是偶數(shù)，問(wèn)題都已得到證明.

下面介紹一個(gè)著名問(wèn)題.

例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í)，問(wèn)題得證；當(dāng)B、C、D三人中有兩人認(rèn)識(shí)，如B、C認(rèn)識(shí)時(shí)，則A、B、C互相認(rèn)識(shí)，問(wèn)題也得證.

本例和上例都采用了舍去保留、化繁為簡(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ù)來(lái)分類，這樣的類只有三個(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ù)來(lái)分類，這種類至多只有四個(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ù)問(wèn)題的特征，制造出放進(jìn)抽屜的物體，則更可收到意想不到的效果.

例12 求證：從任意n個(gè)自然數(shù)a₁，a₂，…，a_n中可以找到若干個(gè)數(shù)，使它們的和是n的倍數(shù).

分析以0，1，…，n-1即被n除的余數(shù)分類制造抽屜的合理的，但把什么樣的數(shù)作為抽屜里的物體呢？扣住“和”，構(gòu)造下列和數(shù)：

S₁=a₁,

S₂=a₁+a₂,

S=a₁+a₂+a₃,

…………

S_n=a₁+a₂+…+a_n，

其中任意兩個(gè)和數(shù)之差仍為和數(shù)，若他們之中有一是n的倍數(shù)，問(wèn)題得證，否則至少有兩個(gè)數(shù)被n除余數(shù)相同，則它們的差即它們中若干數(shù)（包括1個(gè)）的和是n的倍數(shù)，問(wèn)題同樣得證.

例子3（北京1990年高一競(jìng)賽）910瓶紅、藍(lán)墨水，排成130行，每行7瓶，證明：不論怎樣排列，紅藍(lán)墨水瓶的顏色次序必定出現(xiàn)下述兩種情況之一種：

（1）至少有三行完全相同；

（2）至少有兩組（四行）每組的兩行完全相同.

解910瓶紅、藍(lán)墨水排成130行，每行7瓶，對(duì)一行來(lái)說(shuō)，每個(gè)位置上有紅藍(lán)兩種可能，因此，一行的紅、藍(lán)墨水排法有2⁷=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只，不用眼睛看，任意地取出筷子來(lái)，使得至少有兩雙筷子不同色，那么至少要取出多少只筷子才能做到？

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)連接起來(lái)，運(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è)它是黃色，則黑色或白色的筷子至少有３只，其中必有一雙同色，即黑色或白色，故�。保敝豢曜幼阋员ＷC成功．但少于１１只不行，如取１０只筷子，閔可能出現(xiàn)８只黃色，黑白各一只，不合要求．

３．將１０個(gè)數(shù)分成５組：（１，７），（２，６），（３，９），（４，８），（５，１０）．任取六個(gè)數(shù)必有兩個(gè)落入同一組，而同組二數(shù)中一數(shù)是另一數(shù)的倍數(shù)．

４．每個(gè)整數(shù)被９９８除，余數(shù)必是０，１，２，…，９９７中的一個(gè)．把這９９８?jìng)�(gè)余數(shù)制造為（０），（１，９９７），（２，９９６），…，（４９７，５０１），（４９８），（４９９），（５００）共５０１個(gè)抽屜，把５０２個(gè)整數(shù)按被９９８除的余數(shù)大小分別放入上述抽屜，必有兩數(shù)進(jìn)入同一抽屜．若余數(shù)相同，那么它們的差是９９８的倍數(shù)，否則和為９９８的倍數(shù)．

５．從各種位置上截得的三位數(shù)有２８?jìng)�(gè)，但由１，２，３組成的不同三位數(shù)有３×３×３＝２７個(gè)，故有兩個(gè)截得的三位數(shù)相同．

６．１８９０＝２×３×５×７×９．將１０個(gè)數(shù)記為ｘ_１，ｘ_２，…，ｘ_９，ｘ_１０．１０個(gè)數(shù)中至少有兩個(gè)被９除余數(shù)相同，設(shè)為ｘ_１，ｘ_２則ｘ_１－ｘ_２可被９整除．同樣剩下８?jìng)�(gè)數(shù)中有兩個(gè)數(shù)的差可被７整除，記為ｘ_３－ｘ­_４，剩下６個(gè)數(shù)中有兩個(gè)數(shù)的差可被５整除，記為ｘ_５－ｘ_６，剩下４個(gè)數(shù)中有兩個(gè)數(shù)的差可被３整除，記為ｘ_７－ｘ_８．剩下兩數(shù)ｘ_９，ｘ_１０，若有一數(shù)為偶數(shù)，則ｘ_９，ｘ_１０可被２整除，否則ｘ_９－ｘ_１０可被２整除．故乘積（ｘ_１－ｘ_２）（ｘ_３－ｘ_４）（ｘ_５－ｘ_６）（ｘ_７－ｘ_８）ｘ_９·ｘ_１０與（ｘ_１－ｘ_２）（ｘ_３－ｘ_４）（ｘ_５－ｘ_６）（ｘ_７－ｘ_８）（ｘ_９－ｘ_１０）二者之一必可被１８９０整除．

７．任選一點(diǎn)Ｐ，過(guò)Ｐ點(diǎn)分別作各線的平行線，則它們把一周角分成１４個(gè)彼此相鄰的角，其中至少有一個(gè)角小于２６°．

８．用兩種顏色涂１×３的小方格共有８種方法．現(xiàn)有９列，由抽屜原則，必有兩列涂法一樣．

９．設(shè)兩種顏色為紅、藍(lán)，考察第一行的涂色．必有三格同色，不妨設(shè)為紅色，且在左邊三列．現(xiàn)考察左邊三列，若下面四行中某一行有兩格同為紅色，則出現(xiàn)四角同紅色矩形，否則每行僅可能一格染紅色，從而四行中必有二行左邊三列中有兩列同染藍(lán)色，從而得到四角同為藍(lán)色的矩形．

１０．考慮１，１１，…共１９８７個(gè)數(shù)，其中必有一個(gè)是１９８７的倍數(shù)，否則必有兩數(shù)被１９８７除余數(shù)相同，其差

是１９８７的倍數(shù)．但１０^ｉ與１９８７沒(méi)有除１外的因數(shù)，故是１９８７倍數(shù)導(dǎo)致矛盾．