1樓:
抽屜原則
大家知道,兩個抽屜要放置三隻蘋果,那麼一定有兩隻蘋果放在同乙個抽屜裡,更一般地說,只要被放置的蘋果數比抽屜數目大,就一定會有兩隻或更多隻的蘋果放進同乙個抽屜,可不要小看這一簡單事實,它包含著乙個重要而又十分基本的原則——抽屜原則. 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,設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) ____根據原則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雙。 證明 除可能取出紅襪、白襪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×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, s=a1+a2+a3, ………… sn=a1+a2+…+an, 其中任意兩個和數之差仍為和數,若他們之中有一是n的倍數,問題得證,否則至少有兩個數被n除餘數相同,則它們的差即它們中若干數(包括1個)的和是n的倍數,問題同樣得證. 例子3 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)兩組(四行),且兩組兩行完全相同. http://www.
A,B,C三人一組工作,其中C是女生。A心特別細,情商很高,非常樂觀活潑開朗,能很快清楚C表達的意
非常一夏 a男和b男同時喜歡c女,a男雖然心機,但是歷練少,在c女面前表現的不夠老練,b男雖然喜歡只是行為很收斂,表現的很含蓄。a.男是想在同事面前也是在b男面前證明,c女是我的,我要追求她,不要和我爭。 小小的雨小點點 都是有心人,做事情也有一套一套的。交朋友可不能馬虎,用第三者的眼光去評判他們兩...
請問字謎 三人同看日的謎底是啥,謎語三人同日來,喜見百花開打一字
三人同看一日,春 字上面三橫和乙個人字重合,下面是乙個 日 字。所以上下拼起來就是乙個 春 字。拼音 ch n 基本釋義 1.一年的第一季 季 農曆正月至三月 節。色。暉 春天的陽光,喻父母的恩情 山 春天的山,山色如黛,喻婦女的眉毛 秋 a 春季和秋季 b 指年月 c 指人的年歲,如 正富 d 指...
孫權 呂蒙 魯肅的三人故事,呂蒙,魯肅,孫權三人是什麼關係
這是 孫權勸學 的故事,還涉及兩個著名成語 吳下阿蒙 刮目相看孫權是呂蒙和魯肅的主公,呂蒙是武將,魯肅是謀士呂蒙原來是個文盲,一次孫權對他說 阿蒙啊,要看書了,不然沒出息 呂蒙不以為意 孫權又說 你看我都是主公了還看書,你現在還是個武將,不看書怎麼給你當大官 於是呂蒙接受了孫權的建議,發憤圖強,三年...