抽屜原則

抽屜原則

抽屜原則是德國數學家狄利克雷首先明確的提出來並用以證明一些數論中的問題,因此,也稱為狄利克雷原則。它是組合數學中一個重要的原理。把它推廣到一般情形有以下幾種表現形式。

舉例

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

常見形式

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

原則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.
證明 設a1,a2,a3,…,a9,a10分別代表不超過10的十個自然數,它們圍成一個圈,三個相鄰的數的組成是(a1,a2,a3),(a2,a3,a4),(a3,a4,a5),…,(a9,a10,a1),(a10,a1,a2)共十組.現把它們看作十個抽屜,每個抽屜的物體數是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) =165=16*10+5(m=16,k=5)
根據原則2,至少有一個括弧內的三數和不少於17,即至少有三個相鄰的數的和不小於17.
原則1、原則2可歸結到更一般形式:

原則3

把m1+m2+…+mn+k(k≥1)個物體放入n個抽屜里,那么或在第一個抽屜里至少放入m1+1個物體,或在第二個抽屜里至少放入m2+1個物體,……,或在第n個抽屜里至少放入mn+1個物體。
證明 假定第一個抽屜放入物體的數不超過m1個,第二個抽屜放入物體的數不超過m2個,……,第n個抽屜放入物體的個數不超過mn,那么放入所有抽屜的物體總數不超過m1+m2+…+mn個,與題設矛盾。
例4 有紅襪2雙,白襪3雙,黑襪4雙,黃襪5雙,藍襪6雙(每雙襪子包裝在一起)若取出9雙,證明其中必有黑襪、藍襪或黃襪2雙。
證明 除可能取出紅襪2雙、白襪3雙外.還至少從其它三種顏色的襪子裡取出4雙,根據原理3,必在黑襪或黃襪、藍襪里取2雙。上面數例論證的似乎都是“存在”、“總有”、“至少有”的問題,不錯,這正是抽屜原則的主要作用.需要說明的是,運用抽屜原則只是肯定了“存在”、“總有”、“至少有”,卻不能確切地指出哪個抽屜里存在多少。

製造抽屜

製造抽屜是運用原則的一大關鍵 ____首先要指出的是,對於同一問題,常可依據情況,從不同角度設計抽屜,從而導致不同的製造抽屜的方式.

例5

在邊長為1的正方形內,任意給定13個點,試證:其中必有4個點,以此4點為頂點的四邊形面積不超過 1/4(假定四點在一直線上構成面積為零的四邊形).
證明 如圖12-2把正方形分成四個相同的小正方形。因13=3×4+1,根據原則2,總有4點落在同一個小正方形內(或邊界上),以此4點為頂點的四邊形的面積不超過小正方形的面積,也就不超過整個正方形面積的 1/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×22,1×23,1×24,1×25,1×26;第二個抽屜時放進數:3,3×2,3×22,3×23,3×24,3×25;第三個抽屜里放進數:5,5×2,5×22,5×23,5×24;………………第二十五個抽屜里放進數: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元中有兩對都是奇數或都是偶數.
分析 設七個三元素組為A1(x1,y1,z1)、A2(x2,y2,z2)、…、A7(x7,y7,z7).現在逐步探索,從x元開始,由抽屜原則,x1,x2,…,x7這七個數中,必定有四個數具有相同的奇偶性,不妨設這四個數是x1,x2,x3,x4且為偶數,接著集中考慮A1、A2、A3、A4這四組數的y元,若比如y1,y2,y3,y4中有兩個是偶數,則問題已證,否則至多有一個是偶數,比如y4是偶數,這時我們再來集中考慮A1、A2、A3的z元.在z1,z2,z3中,由抽屜原則必有兩個數具有相同的奇偶性,如z1、z2,這時無論它們是奇數,還是偶數,問題都已得到證明. 下面介紹一個著名問題.

例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互相認識,問題也得證.本例和上例都採用了捨去保留、化繁為簡、逐步縮小考慮範圍的方法.

例11

a,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個自然數a1,a2,…,an中可以找到若干個數,使它們的和是n的倍數.
分析以0,1,…,n-1即被n除的餘數分類製造抽屜的合理的,但把什麼樣的數作為抽屜里的物體呢?扣住“和”,構造下列和數: S1=a1, S2=a1+a2, S3=a1+a2+a3, ………… Sn=a1+a2+…+an, 其中任意兩個和數之差仍為和數,若他們之中有一是n的倍數,問題得證,否則至少有兩個數被n除餘數相同,則它們的差即它們中若干數(包括1個)的和是n的倍數,問題同樣得證.

例13

910瓶紅、藍墨水,排成130行,每行7瓶,證明:不論怎樣排列,紅藍墨水瓶的顏色次序必定出現下述兩種情況之一種:(1)至少有三行完全相同;(2)至少有兩組(四行)每組的兩行完全相同.
解 910瓶紅、藍墨水排成130行,每行7瓶,對一行來說,每個位置上有紅藍兩種可能,因此,一行的紅、藍墨水排法有27=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)兩組(四行),且兩組兩行完全相同

熱門詞條

聯絡我們