標籤:抽屜原理

桌上有十個蘋果,要把這十個蘋果放到九個抽屜里,無論怎樣放,我們會發現至少會有一個抽屜裡面至少放兩個蘋果。這一現象就是我們所說的「抽屜原理」。 抽屜原理的一般含義為:「如果每個抽屜代表一個集合,每一個蘋果就可以代表一個元素,假如有n+1或多於n+1個元素放到n個集合中去,其中必定至少有一個集合里有兩個元素。」 抽屜原理有時也被稱為鴿巢原理(「如果有五個鴿子籠,養鴿人養了6隻鴿子,那麼當鴿子飛回籠中后,至少有一個籠子中裝有至少2隻鴿子」)。它是組合數學中一個重要的原理。

1常見形式

第二抽屜原理
把(mn-1)個物體放入n個抽屜中,其中必有一個抽屜中至多有(m—1)個物體(例如,將3×5-1=14個物體放入5個抽屜中,則必定有一個抽屜中的物體數少於等於3-1=2)。
證明(反證法):若每個抽屜都有不少於m個物體,則總共至少有mn個物體,與題設矛盾,故不可能。

2應用

整除問題
把所有整數按照除以某個自然數m的餘數分為m類,叫做m的剩餘類或同餘類,用[0],[1],[2],…,[m-1]表示.每一個類含有無窮多個數,例如[1]中含有1,m+1,2m+1,3m+1,….在研究與整除有關的問題時,常用剩餘類作為抽屜.根據抽屜原理,可以證明:任意n+1個自然數中,總有兩個自然數的差是n的倍數。(證明:n+1個自然數被n整除餘數至少有兩個相等(抽屜原理),不妨記為m=a1*n+b n=a2*n+b,則m-n整除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個抽屜中(即抽屜中分別為含有餘數為0,1,2的數),我們從這三個抽屜中各取1個(如1~5中取3,4,5),其和(3+4+5=12)必能被3整除.
②若這5個餘數分佈在其中的兩個抽屜中,則其中必有一個抽屜至少包含有3個餘數(抽屜原理),即一個抽屜包含1個餘數,另一個包含4個,或者一個包含2個餘數另一個抽屜包含3個。從餘數多的那個抽屜里選出三個餘數,其代數和或為0,或為3,或為6,均為3的倍數,故所對應的3個自然數之和是3的倍數.
③若這5個餘數分佈在其中的一個抽屜中,很顯然,從此抽屜中任意取出三個餘數,同情況②,餘數之和可被3整除,故其對應的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的倍數.
抽屜原理 - 表述
抽屜原理的一種更一般的表述為:
「把多於kn+1個東西任意分放進n個空抽屜(k是正整數),那麼一定有一個抽屜中放進了至少k+1個東西。」
利用上述原理容易證明:「任意7個整數中,至少有3個數的兩兩之差是3的倍數。」因為任一整數除以3時餘數只有0、1、2三種可能,所以7個整數中至少有3個數除以3所得餘數相同,即它們兩兩之差是3的倍數。
如果問題所討論的對象有無限多個,抽屜原理還有另一種表述:
「把無限多個東西任意分放進n個空抽屜(n是自然數),那麼一定有一個抽屜中放進了無限多個東西。」
抽屜原理的內容簡明樸素,易於接受,它在數學問題中有重要的作用。許多有關存在性的證明都可用它來解決。
染色問題
例1正方體各面上塗上紅色或藍色的油漆(每面只塗一種色),證明正方體一定有三個面顏色相同.
證明:正方形有6個面 由最多[(m-1)÷n]+1 得出[(6-1)÷2]+1=[2.5]+1=3
例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中有兩人也討論乙問題,則結論也就成立了。否則,他們間只討論丙問題,這樣結論也成立。

3狄利克雷

表現形式
把它推廣到一般情形有以下幾種表現形式。
形式一:設把n+1個元素劃分至n個集合中(A1,A2,…,An),用a1,a2,…,an分別表示這n個集合對應包含的元素個數,則:至少存在某個集合Ai,其包含元素個數值ai大於或等於2。
證明:(反證法)假設結論不成立,即對每一個ai都有ai<2,則因為ai是整數,應有ai≤1,於是有:
a1+a2+…+an≤1+1+…+1=n<n+1,這與題設矛盾。
所以,至少有一個ai≥2,即必有一個集合中含有兩個或兩個以上的元素。
形式二:設把nm+1個元素劃分至n個集合中(A1,A2,…,An),用a1,a2,…,an表示這n個集合對應包含的元素個數,則:至少存在某個集合Ai,其包含元素個數值ai大於或等於m+1。
證明:(反證法)假設結論不成立,即對每一個ai都有ai<m+1,則因為ai是整數,應有ai≤m,於是有:
a1+a2+…+an≤m+m+…+m=nm<nm+1,這與題設相矛盾。
所以,至少有存在一個ai≥m+1
知識擴展——高斯函數[x]定義:對任意的實數x,[x]表示「不大於x的最大整數」。例如:[3.5]=3,[2.9]=2,[-2.5]=-3,[7]=7,……一般地,我們有:[x]≤x<[x]+1
形式三:設把n個元素分為k個集合A1,A2,…,Ak,用a1,a2,…,ak表示這k個集合里相應的元素個數,需要證明至少存在某個ai大於或等於[n/k]。
證明:(用反證法)假設結論不成立,即對每一個ai都有ai<[n/k],於是有:
a1+a2+…+ak<[n/k]+[n/k]+…+[n/k] =k?[n/k]≤k?(n/k)=n
k個[n/k] ∴ a1+a2+…+ak<n 這與題設相矛盾。所以,必有一個集合中元素個數大於或等於[n/k]
形式四:設把q1+q2+…+qn-n+1個元素分為n個集合A1,A2,…,An,用a1,a2,…,an表示這n個集合里相應的元素個數,需要證明至少存在某個i,使得ai大於或等於qi。
證明:(用反證法)假設結論不成立,即對每一個ai都有ai<qi,因為ai為整數,應有ai≤qi-1,
於是有:a1+a2+…+an≤q1+q2+…+qn-n <q1+q2+…+qn-n+1這與題設矛盾。
所以,假設不成立,故必有一個i,在第i個集合中元素個數ai≥qi
形式五:證明:(用反證法)將無窮多個元素分為有限個集合,假設這有限個集合中的元素的個數都是有限個,則有限個有限數相加,所得的數必是有限數,這就與題設產生矛盾,所以,假設不成立,故必有一個集合含有無窮多個元素。
練習
1.邊長為1的等邊三角形內有5個點,那麼這5個點中一定有距離小於0.5的兩點;
2.邊長為1的等邊三角形內,若有n²+1個點,則至少存在2點距離小於1/n;
3.任意四個整數中,至少有兩個整數的差能夠被3整除;
4.某校高一某班有50名新生,試說明其中一定有二人的熟人一樣多.
5.某個年級有202人參加考試,滿分為100分,且得分都為整數,總得分為10101分,則至少有3人得分相同.
6.任意367個人中,必有生日相同的人;
7.從任意5雙手套中任取6隻,其中至少有2隻恰為一雙手套;
8.從數1,2,...,10中任取6個數,其中至少有2個數為奇偶性不同;
9.一個木箱里裝一樣的紅,黃,綠,白四種顏色的小球個10個,從箱里任意摸出小球,問至少要摸出10個小球才能保證一定有兩種顏色的小球。
大家都會認為上面所述結論是正確的。這些結論是依據什麼原理得出的呢?這個原理叫做抽屜原理。它的內容可以用形象的語言表述為:
「把m個東西任意分放進n個空抽屜里(m>n),那麼一定有一個抽屜中放進了至少2個東西。」

4一般表述

在上面的第一個結論中,由於一年最多有366天,因此在367人中至少有2人出生在同月同日。這相當於把367個東西放入 366個抽屜,至少有2個東西在同一抽屜里。在第二個結論中,不妨想象將5雙手套分別編號,即號碼為1,2,...,5的手套各有兩隻,同號的兩隻是一雙。任取6隻手套,它們的編號至多有5種,因此其中至少有兩隻的號碼相同。這相當於把6個東西放入5個抽屜,至少有2個東西在同一抽屜里。
抽屜原理的一種更一般的表述為:
「把多於kn+1個東西任意分放進n個空抽屜(k是正整數),那麼一定有一個抽屜中放進了至少k+1個東西。」
利用上述原理容易證明:「任意7個整數中,至少有3個數的兩兩之差是3的倍數。」因為任一整數除以3時餘數只有0、1、2三種可能,所以7個整數中至少有3個數除以3所得餘數相同,即它們兩兩之差是3的倍數。
如果問題所討論的對象有無限多個,抽屜原理還有另一種表述:
「把無限多個東西任意分放進n個空抽屜(n是自然數),那麼一定有一個抽屜中放進了無限多個東西。」
用高斯函數來敘述一般形式的抽屜原理的是:將m個元素放入n個抽屜,則在其中一個抽屜里至少會有
(m-1)÷n+1個元素。
抽屜原理的內容簡明樸素,易於接受,它在數學問題中有重要的作用。許多有關存在性的證明都可用它來解決。
這個問題可以用如下方法簡單明了地證出:
在平面上用6個點A、B、C、D、E、F分別代表參加集會的任意6個人。如果兩人以前彼此認識,那麼就在代表他們的兩點間連成一條紅線;否則連一條藍線。考慮A點與其餘各點間的5條連線AB,AC,...,AF,它們的顏色不超過2種。根據抽屜原理可知其中至少有3條連線同色,不妨設AB,AC,AD同為紅色。如果BC,BD ,CD 3條連線中有一條(不妨設為BC)也為紅色,那麼三角形ABC即一個紅色三角形,A、B、C代表的3個人以前彼此相識:如果BC、BD、CD 3條連線全為藍色,那麼三角形BCD即一個藍色三角形,B、C、D代表的3個人以前彼此不相識。不論哪種情形發生,都符合問題的結論。
六人集會問題是組合數學中著名的拉姆塞定理的一個最簡單的特例,這個簡單問題的證明思想可用來得出另外一些深入的結論。這些結論構成了組合數學中的重要內容-----拉姆塞理論。從六人集會問題的證明中,我們又一次看到了抽屜原理的應用。

5經典練習

系列之二
7、 證明:從1,3,5,……,99中任選26個數,其中必有兩個數的和是100。
解析:將這50個奇數按照和為100,放進25個抽屜:(1,99),(3,97),(5,95),……,(49 ,51)。根據抽屜原理,從中選出26個數,則必定有兩個數來自同一個抽屜,那麼這兩個數的和即為100。
8。 某旅遊車上有47名乘客,每位乘客都只帶有一種水果。如果乘客中有人帶梨,並且其中任何兩位乘客中至少有一個人帶蘋果,那麼乘客中有______人帶蘋果。
解析:由題意,不帶蘋果的乘客不多於一名,但又確實有不帶蘋果的乘客,所以不帶蘋果的乘客恰有一名,所以帶蘋果的就有46人。
9。 一些蘋果和梨混放在一個筐里,小明把這筐水果分成了若干堆,後來發現無論怎麼分,總能從這若干堆里找到兩堆,把這兩堆水果合併在一起后,蘋果和梨的個數是偶數,那麼小明至少把這些水果分成了_______堆。
解析:要求把其中兩堆合併在一起后,蘋果和梨的個數一定是偶數,那麼這兩堆水果中,蘋果和梨的奇偶性必須相同。對於每一堆蘋果和梨,奇偶可能性有4種:(奇,奇),(奇,偶),(偶,奇),(偶,偶),所以根據抽屜原理可知最少分了4+1=5筐。
10。從前25個自然數中任意取出7個數,證明:取出的數中一定有兩個數,這兩個數中大數不超過小數的1.5倍。
證明:把前25個自然數分成下面6組:
1; ①
2,3; ②
4,5,6; ③
7,8,9,10; ④
11,12,13,14,15,16; ⑤
17,18,19,20,21,22,23, ⑥
因為從前25個自然數中任意取出7個數,所以至少有兩個數取自上面第②組到第⑥組中的某同一組,這兩個數中大數就不超過小數的1.5倍。
11.一副撲克牌有四種花色,每種花色各有13張,現在從中任意抽牌。問最少抽幾張牌,才能保證有4張牌是同一種花色的?
解析:根據抽屜原理,當每次取出4張牌時,則至少可以保障每種花色一樣一張,按此類推,當取出12張牌時,則至少可以保障每種花色一樣三張,但還要加上大小怪,所以當抽取第15張牌時,無論是什麼花色,都可以至少保障有4張牌是同一種花色。
13.從1、2、3、4……、12這12個自然數中,至少任選幾個,就可以保證其中一定包括兩個數,他們的差是7?
【解析】在這12個自然數中,差是7的自然樹有以下5對:{12,5}{11,4}{10,3}{9,2}{8,1}。另外,還有2個在該範圍取不到差值為7的配對的數是{6}、{7}。根據抽屜原理,共構造了7個抽屜。只要有兩個數是取自同一個抽屜,那麼它們的差就等於7。這7個抽屜可以表示為{12,5}{11,4}{10,3}{9,2}{8,1}{6}{7},顯然從7個抽屜中取8個數,則一定可以使有兩個數字來源於同一個抽屜,也即作差為7。
系列之四
1. 任意5個自然數中,必可找出3個數,使這三個數的和能被3整除。
分析:解這個問題,注意到一個數被3除的餘數只有0,1,2三個,可以用餘數來構造抽屜。
解:以一個數被3除的餘數0、1、2構造抽屜,共有3個抽屜。任意五個數放入這三個抽屜中,若每個抽屜內均有數,則各抽屜取一個數,這三個數的和是3的倍數,結論成立;若至少有一個抽屜內沒有數,那麼5個數中必有三個數在同一抽屜內,這三個數的和是3的倍數,結論亦成立。
2. 在邊長為1的正方形內,任意放入9個點,證明在以這些點為頂點的三角形中,必有一個三角形的面積不超過1/8.
解:分別連結正方形兩組對邊的中點,將正方形分為四個全等的小正方形,則各個小正方形的面積均為1/4 。把這四個小正方形看作4個抽屜,將9個點隨意放入4個抽屜中,據抽屜原理,至少有一個小正方形中有3個點。顯然,以這三個點為頂點的三角形的面積不超過1/8 。
反思:將邊長為1的正方形分成4個面積均為1/4 的小正方形,從而構造出4個抽屜,是解決本題的關鍵。我們知道。將正方形分成面積均為1/4 的圖形的方法不只一種,如可連結兩條對角線將正方形分成4個全等的直角三角形,這4個圖形的面積也都是1/4 ,但這樣構造抽屜不能證到結論。可見,如何構造抽屜是利用抽屜原理解決問題的關鍵。
3. 班上有50名學生,將書分給大家,至少要拿多少本,才能保證至少有一個學生能得到兩本或兩本以上的書。
解:把50名學生看作50個抽屜,把書看成蘋果 ,根據原理1,書的數目要比學生的人數多,即書至少需要50+1=51本.
4. 在一條長100米的小路一旁植樹101棵,不管怎樣種,總有兩棵樹的距離不超過1米。
解:把這條小路分成每段1米長,共100段,每段看作是一個抽屜,共100個抽屜,把101棵樹看作是101個蘋果 ,於是101個蘋果放入100個抽屜中,至少有一個抽屜中有兩個蘋果 ,即至少有一段有兩棵或兩棵以上的樹 .
你也來試試?
1.飼養員給10隻猴子分桃子,其中至少要有一隻猴子得到7個桃子,飼養員至少要拿來多少個桃子?
2.從13個自然數中,一定可以找到兩個數,它們的差是12的倍數。
3.一個班有40名同學,現在有課外書125本。把這些書分給同學,是否有人會得到4本或4本以上課外書?
4.42隻鴿子飛進5個籠子里,可以保證在鴿子最多的籠子中至少有幾隻鴿子?
上一篇[柯達 Z612]    下一篇 [卡西歐EX-Z300]

相關評論

同義詞:暫無同義詞