抽屜原則

2009-08-31 11:13:39網絡來源

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

1．抽屜原則有幾種最常見的形式

原則1 如果把n+k(k≥1)個物體放進n只抽屜里，則至少有一只抽屜要放進兩個或更多個物體：

原則本身十分淺顯，為了加深對它的認識，我們還是運用反證法給予證明；如果每個抽屜至多只能放進一個物體，那么物體的總數至多是n，而不是題設的n+k(k≥1)，這不可能.

原則雖簡單.巧妙地運用原則卻可十分便利地解決一些看上去相當復雜、甚至感到無從下手的總是，比如說，我們可以斷言在我國至少有兩個人出生的時間相差不超過4秒鐘，這是個驚人的結論，該是經過很多人的艱苦勞動，統計所得的吧！不，只須我們稍動手算一下：

不妨假設人的壽命不超過4萬天（約110歲，超過這個年齡數的人為數甚少），則

10億人口安排在8億6千4百萬個“抽屜”里，根據原則1，即知結論成立.

下面我們再舉一個例子：
例1 幼兒園買來了不少白兔、熊貓、長頸鹿塑料玩具，每個小朋友任意選擇兩件，那么不管怎樣挑選，在任意七個小朋友中總有兩個彼此選的玩具都相同，試說明道理.

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

（兔、兔），（兔、熊貓），（兔、長頸鹿），（熊貓、熊貓），（熊貓、長頸鹿），（長頸鹿、長頸鹿）

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

原則2 如果把mn+k(k≥1)個物體放進n個抽屜，則至少有一個抽屜至多放進m+1個物體.證明同原則相仿.若每個抽屜至多放進m個物體,那么n個抽屜至多放進mn個物體,與題設不符，故不可能.

原則1可看作原則2的物例（m=1）

例2正方體各面上涂上紅色或藍色的油漆（每面只涂一種色），證明正方體一定有三個面顏色相同.

證明把兩種顏色當作兩個抽屜，把正方體六個面當作物體，那么6=2×2+2，根據原則二，至少有三個面涂上相同的顏色.

例3 把1到10的自然數擺成一個圓圈，證明一定存在在個相鄰的數，它們的和數大于17.

證明如圖12-1，設a₁，a₂，a₃，…，a₉，a₁₀分別代表不超過10的十個自然數，它們圍成一個圈，三個相鄰的數的組成是（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₁，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)

根據原則2,至少有一個括號內的三數和不少于17,即至少有三個相鄰的數的和不小于17.

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

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

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

證明除可能取出紅襪、白襪3雙外.還至少從其它三種顏色的襪子里取出4雙，根據原理3，必在黑襪或黃襪、藍襪里取2雙.

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

2．制造抽屜是運用原則的一大關鍵

首先要指出的是，對于同一問題，常可依據情況，從不同角度設計抽屜，從而導致不同的制造抽屜的方式.

例5 在邊長為1的正方形內，任意給定13個點，試證：其中必有4個點，以此4點為頂點的四邊開面積不超過（假定四點在一直線上構成面積為零的四邊形）.

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

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

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

合理地制造抽屜必須建立在充分考慮問題自身特點的基礎上.

例6 在一條筆直的馬路旁種樹，從起點起，每隔一米種一棵樹，如果把三塊“愛護樹木”的小牌分別掛在三棵樹上，那么不管怎樣掛，至少有兩棵掛牌的樹之間的距離是偶數（以米為單位），這是為什么？

解如圖12-4（設掛牌的三棵樹依次為A、B、C.AB=a，BC=b，若a、b中有一為偶數，命題得證.否則a、b均為奇數，則AC=a+b為偶數，命題得證.

下面我們換一個角度考慮：給每棵樹上編上號，于是兩棵樹之間的距離就是號碼差，由于樹的號碼只能為奇數和偶數兩類，那么掛牌的三棵樹號碼至少有兩個同為奇數或偶數，它們的差必為偶數，問題得證.

后一證明十分巧妙，通過編號碼，將兩樹間距離轉化為號碼差.這種轉化的思想方法是一種非常重要的數學方法

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

分析設法制造抽屜：（1）不超過50個；（2）每個抽屜的里的數（除僅有的一個外），其中一個數是另一個數的倍數，一個自然數的想法是從數的質因數表示形式入手.

解設第一個抽屜里放進數：1，1×2，1×2²，1×2³，1×2⁴，1×2⁵，1×2⁶；

第二個抽屜時放進數：3，3×2，3×2²，3×2³，3×2⁴，3×2⁵；

第三個抽屜里放進數：5，5×2，5×2²，5×2³，5×2⁴；

………………

第二十五個抽屜里放進數：49，49×2；

第二十六個抽屜里放進數：51.

………………

第五十個抽屜里放進數：99.

那么隨意取出51個數中，必有兩個數同屬一個抽屜，其中一個數是另一個數的倍數.

制造抽屜并非總是一帆風順的，有時要邊制造邊調整、改進.

例8 任意給定7個不同的自然數，求證其中必有兩個整數，其和或差是10的倍數.

分析注意到這些數隊以10的余數即個位數字，以0，1，…，9為標準制造10個抽屜，標以[0]，[1]，…，[9].若有兩數落入同一抽屜，其差是10的倍數，只是僅有7個自然數，似不便運用抽屜原則，再作調整：[6]，[7]，[8]，[9]四個抽屜分別與[4]，[3]，[2]，[1]合并，則可保證至少有一個抽屜里有兩個數，它們的和或差是10的倍數.

3．較復雜的問題須反復地運用抽屜原則，將復雜問題轉化為簡單問題.

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

分析設七個三元素組為A₁（x₁，y₁，z₁）、A₂（x₂，y₂，z₂）、…、A₇（x₇，y₇，z₇）.現在逐步探索，從x元開始，由抽屜原則，x₁，x2，…，x₇這七個數中，必定有四個數具有相同的奇偶性，不妨設這四個數是x₁，x₂，x₃，x₄且為偶數，接著集中考慮A₁、A₂、A₃、A₄這四組數的y元，若比如y₁，y₂，y₃，y₄中有兩個是偶數，則問題已證，否則至多有一個是偶數，比如y₄是偶數，這時我們再來集中考慮A₁、A₂、A₃的z元.在z₁，z₂，z₃中，由抽屜原則必有兩個數具有相同的奇偶性，如z₁、z₂，這時無論它們是奇數，還是偶數，問題都已得到證明.

下面介紹一個著名問題.

例10 任選6人，試證其中必有3人，他們互相認識或都不認識.

分析用A、B、C、D、E、F表示這6個人，首先以A為中心考慮，他與另外五個人B、C、D、E、F只有兩種可能的關系：認識或不認識，那么由抽屜原則，他必定與其中某三人認識或不認識，現不妨設A認識B、C、D三人，當B、C、D三人都互不認識時，問題得證；當B、C、D三人中有兩人認識，如B、C認識時，則A、B、C互相認識，問題也得證.

本例和上例都采用了舍去保留、化繁為簡、逐步縮小考慮范圍的方法.

例11a，b，c，d為四個任意給定的整數，求證：以下六個差數

b-a，c-a，d-a，c-b，d-b，d-c的乘積一定可以被12整除.

證明把這6個差數的乘積記為p，我們必須且只須證明：3與4都可以整除p，以下分兩步進行.

第一步，把a，b，c，d按以3為除數的余數來分類，這樣的類只有三個，故知a，b，c，d中至少有2個除以3的余數相同，例如，不妨設為a，b，這時3可整除b-a，從而3可整除p.

第二步，再把a，b，c，d按以4為除數的余數來分類，這種類至多只有四個，如果a，b，c，d中有二數除以4的余數相同，那么與第一步類似，我們立即可作出4可整除p的結論.

設a，b，c，d四數除以4的余數不同，由此推知，a，b，c，d之中必有二個奇數（不妨設為a，b），也必有二個偶數（設為c，d），這時b-a為偶數，d-c也是偶數，故4可整除(b-a)(d-c)，自然也可得出4可整除p.

如果能進一步靈活運用原則，不僅制造抽屜，還根據問題的特征，制造出放進抽屜的物體，則更可收到意想不到的效果.

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

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

S₁=a₁,

S₂=a₁+a₂,

S=a₁+a₂+a₃,

…………

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

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

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

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

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

解910瓶紅、藍墨水排成130行，每行7瓶，對一行來說，每個位置上有紅藍兩種可能，因此，一行的紅、藍墨水排法有2⁷=128種，對每一種不同排法設為一種“行式”，共有128種行式.

現有130行，在其中任取129行，依抽屜原則知，必有兩行A、B行式相同.

除A、B外余下128行，若有一行P與A行式相同，知滿足（1）至少有三行A、B、P完全相同，若在這128行中設直一行5A行或相同，那么這128行至多有127種行式，依抽屜原則，必有兩行C、D具有相同行式，這樣便找到了（A、B），（C、D）兩組（四行），且兩組兩行完全相同.

練習十二

1．一個籃球運動員在15分鐘內將球投進籃圈20次，證明總有某一分鐘他至少投進兩次.

2．有黑、白、黃筷子各8只，不用眼睛看，任意地取出筷子來，使得至少有兩雙筷子不同色，那么至少要取出多少只筷子才能做到？

3．證明：在1，2，3，…，10這十個數中任取六個數，那么這六個數中總可以找到兩個數，其中一個是另一個的倍數.

4．證明：任意502個整數中，必有兩個整數的和或差是998的倍數.

5．任意寫一個由數字1，2，3組成的30位數，從這30位數任意截取相鄰三位，可得一個三位數，證明：在從各個不同位置上截得的三位數中至少有兩個相等.

6．證明：把任意10個自然數用適當的運算符號連接起來，運算的結果總能被1890整除.

7．七條直線兩兩相交，所得的角中至少有一個角小于26°.

8．用2種顏色涂3行9列共27個小方格，證明：不論如何涂色，其中必至少有兩列，它們的涂色方式相同.

9．用2種顏色涂5×5共25個小方格，證明：必有一個四角同色的矩形出現.

10．求證存在形如11…11的一個數，此數是1987的倍數.

練習十二

1．15分鐘里在每一分鐘看作一個抽屜，20次投籃看作20個物體，根據原理一即得.

2.至少要取１１只筷子．因為１１只筷子中必有一雙筷子同色，不妨設它是黃色，則黑色或白色的筷子至少有３只，其中必有一雙同色，即黑色或白色，故取１１只筷子足以保證成功．但少于１１只不行，如取１０只筷子，閔可能出現８只黃色，黑白各一只，不合要求．

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

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

５．從各種位置上截得的三位數有２８個，但由１，２，３組成的不同三位數有３×３×３＝２７個，故有兩個截得的三位數相同．

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