抽屜原理又稱鴿巢原理,最經(jīng)典的例子莫過于下例了:
一個(gè)養(yǎng)鴿人養(yǎng)了10只鴿子,但只準(zhǔn)備了9個(gè)鴿巢,他發(fā)現(xiàn),無論這些鴿子如何歸巢,必然至少有一個(gè)鴿巢內(nèi)的鴿子不少于2只。
一般的表述方法如下:
第一原理:
(1)把多于n個(gè)的物體放到n個(gè)抽屜里,則至少有一個(gè)抽屜里的東西不少于兩件。
(2)把多于mn(m乘以n)個(gè)的物體放到n個(gè)抽屜里,則至少有一個(gè)抽屜里有不少于m+1的物體。
(3)把無窮多件物體放入n個(gè)抽屜,則至少有一個(gè)抽屜里 有無窮個(gè)物體。
第二原理:
把(mn-1)個(gè)物體放入n個(gè)抽屜中,其中必有一個(gè)抽屜中至多有(m—1)個(gè)物體
抽屜原理 桌上有十個(gè)蘋果,要把這十個(gè)蘋果放到九個(gè)抽屜里,無論怎樣放,有的抽屜可以放一個(gè),有的可以放兩個(gè),有的可以放五個(gè),但最終我們會(huì)發(fā)現(xiàn)至少我們可以找到一個(gè)抽屜里面至少放兩個(gè)蘋果。這一現(xiàn)象就是我們所說的抽屜原理。
抽屜原理的一般含義為:“如果每個(gè)抽屜代表一個(gè)集合,每一個(gè)蘋果就可以代表一個(gè)元素,假如有n+1或多于n+1個(gè)元素放到n個(gè)集合中去,其中必定至少有一個(gè)集合里至少有兩個(gè)元素。”
抽屜原理有時(shí)也被稱為鴿巢原理(“如果有五個(gè)鴿子籠,養(yǎng)鴿人養(yǎng)了6只鴿子,那么當(dāng)鴿子飛回籠中后,至少有一個(gè)籠子中裝有2只鴿子”)。它是德國數(shù)學(xué)家狄利克雷首先明確的提出來并用以證明一些數(shù)論中的問題,因此,也稱為狄利克雷原理。它是組合數(shù)學(xué)中一個(gè)重要的原理。
一. 抽屜原理最常見的形式
原理1 把多于n個(gè)的物體放到n個(gè)抽屜里,則至少有一個(gè)抽屜里有2個(gè)或2個(gè)以上的物體。
[證明](反證法):如果每個(gè)抽屜至多只能放進(jìn)一個(gè)物體,那么物體的總數(shù)至多是n,而不是題設(shè)的n+k(k≥1),這不可能.
原理2 把多于mn個(gè)的物體放到n個(gè)抽屜里,則至少有一個(gè)抽屜里有m+1個(gè)或多于m+1個(gè)的物體。
[證明](反證法):若每個(gè)抽屜至多放進(jìn)m個(gè)物體,那么n個(gè)抽屜至多放進(jìn)mn個(gè)物體,與題設(shè)不符,故不可能.
原理1 2都是第一抽屜原理的表述
第二抽屜原理:
把(mn-1)個(gè)物體放入n個(gè)抽屜中,其中必有一個(gè)抽屜中至多有(m—1)個(gè)物體。
[證明](反證法):若每個(gè)抽屜都有不少于m個(gè)物體,則總共至少有mn個(gè)物體,與題設(shè)矛盾,故不可能
二.應(yīng)用抽屜原理解題
抽屜原理的內(nèi)容簡明樸素,易于接受,它在數(shù)學(xué)問題中有重要的作用。許多有關(guān)存在性的證明都可用它來解決。
例1:400人中至少有兩個(gè)人的生日相同.
解:將一年中的366天視為366個(gè)抽屜,400個(gè)人看作400個(gè)物體,由抽屜原理1可以得知:至少有兩人的生日相同.
又如:我們從街上隨便找來13人,就可斷定他們中至少有兩個(gè)人屬相相同.
“從任意5雙手套中任取6只,其中至少有2只恰為一雙手套?!?
“從數(shù)1,2,。,10中任取6個(gè)數(shù),其中至少有2個(gè)數(shù)為奇偶性不同?!?
例2: 幼兒園買來了不少白兔、熊貓、長頸鹿塑料玩具,每個(gè)小朋友任意選擇兩件,那么不管怎樣挑選,在任意七個(gè)小朋友中總有兩個(gè)彼此選的玩具都相同,試說明道理.
解 :從三種玩具中挑選兩件,搭配方式只能是下面六種:(兔、兔),(兔、熊貓),(兔、長頸鹿),(熊貓、熊貓),(熊貓、長頸鹿),(長頸鹿、長頸鹿)。把每種搭配方式看作一個(gè)抽屜,把7個(gè)小朋友看作物體,那么根據(jù)原理1,至少有兩個(gè)物體要放進(jìn)同一個(gè)抽屜里,也就是說,至少兩人挑選玩具采用同一搭配方式,選的玩具相同.
上面數(shù)例論證的似乎都是“存在”、“總有”、“至少有”的問題,不錯(cuò),這正是抽屜原則的主要作用.(需要說明的是,運(yùn)用抽屜原則只是肯定了“存在”、“總有”、“至少有”,卻不能確切地指出哪個(gè)抽屜里存在多少.)
抽屜原理雖然簡單,但應(yīng)用卻很廣泛,它可以解答很多有趣的問題,其中有些問題還具有相當(dāng)?shù)碾y度。下面我們來研究有關(guān)的一些問題。
(一) 整除問題
把所有整數(shù)按照除以某個(gè)自然數(shù)m的余數(shù)分為m類,叫做m的剩余類或同余類,用[0],[1],[2],…,[m-1]表示.每一個(gè)類含有無窮多個(gè)數(shù),例如[1]中含有1,m+1,2m+1,3m+1,….在研究與整除有關(guān)的問題時(shí),常用剩余類作為抽屜.根據(jù)抽屜原理,可以證明:任意n+1個(gè)自然數(shù)中,總有兩個(gè)自然數(shù)的差是n的倍數(shù)。
桌上有十個(gè)蘋果,要把這十個(gè)蘋果放到九個(gè)抽屜里,無論怎樣放,我們會(huì)發(fā)現(xiàn)至少會(huì)有一個(gè)抽屜里面放兩個(gè)蘋果。
這一現(xiàn)象就是我們所說的“抽屜原理”。 抽屜原理的一般含義為:“如果每個(gè)抽屜代表一個(gè)集合,每一個(gè)蘋果就可以代表一個(gè)元素,假如有n+1或多于n+1個(gè)元素放到n個(gè)集合中去,其中必定至少有一個(gè)集合里有兩個(gè)元素。”
抽屜原理有時(shí)也被稱為鴿巢原理(“如果有五個(gè)鴿子籠,養(yǎng)鴿人養(yǎng)了6只鴿子,那么當(dāng)鴿子飛回籠中后,至少有一個(gè)籠子中裝有2只鴿子”)。它是組合數(shù)學(xué)中一個(gè)重要的原理。
證法一:
用反證法。
假設(shè)任何三個(gè)孩子分到糖的和都小于45。
現(xiàn)設(shè)5個(gè)孩子分到糖的數(shù)量分別是
a,b,c,d,e
設(shè)k=a+b+c
易知k又有d+e=76-k
根據(jù)鴿巢原理,a,b,c三個(gè)數(shù)中至少有一個(gè)不小于k/3
無妨設(shè)a≥k/3
從而
a+d+e≥k/3+ 76-k=76-2k/3 ①
再據(jù)前面的假設(shè),應(yīng)有
a+d+e綜合①,②得
76-2k/3解之得
k>46.5
這與前面的k
證法二:
仍然用反證法.
假設(shè)任何三個(gè)孩子分到糖的和都小于45。
現(xiàn)設(shè)5個(gè)孩子分到糖的數(shù)量分別是
a,b,c,d,e
則從這5個(gè)數(shù)中任取3個(gè),共有10種情況。
且有:
a+b+ca+b+d……
c+d+e把這10個(gè)式子相加,便有
6(a+b+c+d+e)從而a+b+c+d+e這與a+b+c+d+e=76矛盾。證完。
佛祖割肉救鴿子的故事,出自《六度集經(jīng)》卷一《薩波達(dá)王本生》 。
釋迦牟尼佛過去世行菩薩道當(dāng)中,受到忉利天天主的測試。測試釋迦牟尼佛是不是真的在行菩薩道,是不是真的有布施心。所以他就化為老鷹追趕一只鴿子,鴿子驚慌飛跑,逃進(jìn)釋迦牟尼佛的懷抱。因?yàn)獒屽饶材岱鸢l(fā)心行菩薩道,內(nèi)心充滿著對(duì)眾生的慈悲,沒有對(duì)眾生嗔恨、傷害的念頭,那種心念所散發(fā)出來的心波,能夠感動(dòng)到動(dòng)物,使動(dòng)物一看到他的身相,接觸到他的影子,就有一種安慰的、無懼的感覺。所以,這只小鴿子投進(jìn)了釋迦牟尼佛的懷抱,感覺到生命的被救與安穩(wěn)。這時(shí)追趕過來的老鷹就跟釋迦牟尼佛說:“這只鴿子是我的獵物,應(yīng)該還給我,否則我會(huì)當(dāng)下餓死。有了這只鴿子,就有了我的生命,沒有這只鴿子,就沒有我的生命。你同情這只鴿子,難道你就不同情我嗎?”釋迦牟尼佛為了救鴿子,也為了同情老鷹,不惜跟老鷹商量,要割下自己的肉來喂鷹。“好,可以呀!這只鴿子肉有多重,你所割下來的肉也必須有多重!”釋迦牟尼佛就割下身上的肉跟鴿子的體重相秤量,結(jié)果切下一塊,重量不如鴿子,再切下一塊,還是不夠。最后舍命全身秤量,才與鴿子的重量相等。這個(gè)時(shí)候,忉利天王感動(dòng)了,他現(xiàn)出天王之身,然后向這一位菩薩匍伏頂禮、贊嘆,是真菩薩,必定成佛,同時(shí)請菩薩將來成佛的時(shí)候,務(wù)必也要度他。
這個(gè)故事是為了凸顯佛祖那種濟(jì)世為懷,普度眾生的精神。
放鴿子,現(xiàn)在這個(gè)詞主流的意思是說不遵守諾言,帶有欺騙的含義。
另一方面,比較少見的是警察或江湖上的黑話含義:利用色相勾引這個(gè)嫖客,然后進(jìn)行其他的違法犯罪活動(dòng),它不簡簡單單地是一個(gè)賣淫,而是通過賣淫這種手段,獲取更大的利益。這種東西有多種情況,有利用色相勾引以后,進(jìn)行搶劫的,有進(jìn)行盜竊的,等等,進(jìn)行敲詐的。
要說放鴿子的來歷,目前至少有3中說法: 1.源于舊上海的彩票,俗稱“白鴿票”,一般都有去無回,它也可能是老北京養(yǎng)鴿子的爺們兒的慘痛教訓(xùn),鴿子放出去就回不來——有專門裹人家鴿子的人在那兒等著呢。 真正的由來是:古時(shí)候人們通信都是用鴿子來通信的,有一次兩個(gè)人約定,到時(shí)候給我來信.但其中一人,只給放來鴿子沒有寫信.另一人就說,你怎么只放鴿子.不履行諾言.放鴿子就這樣來了. 2.本意是指一種誘拐別人名貴鴿子的行為。
具體方法是訓(xùn)練出一種專用的“誘鴿”,在別人放飛鴿子時(shí),放出自己的“誘鴿”,混到鴿群中。“誘鴿”會(huì)誘騙鴿群迷失方向,把它們引回到偷竊者的鴿籠中。
后來這個(gè)詞的含義就發(fā)生了引申,成為了違約和欺詐行為的代名詞。 3.舊中國上海灘一種詐騙伎倆 以女人到雇主要做保姆,或小妾為名然后卷走被騙人的財(cái)物,黑道上稱為“放鴿子”。
鴿巢原理是抽屜原理.抽屜原理又稱鴿巢原理,它是組合數(shù)學(xué)的一個(gè)基本原理,最先是由德國數(shù)學(xué)家狄利克雷明確地提出來的,因此,也稱為狄利克雷原理。鴿巢原理,又名狄利克雷抽屜原理、鴿巢原理。
其中一種簡單的表述法為:若有n個(gè)籠子和n+1只鴿子,所有的鴿子都被關(guān)在鴿籠里,那么至少有一個(gè)籠子有至少2只鴿子。
另一種為:若有n個(gè)籠子和kn+1只鴿子,所有的鴿子都被關(guān)在鴿籠里,那么至少有一個(gè)籠子有至少k+1只鴿子。
拉姆齊定理是此原理的推廣。
常見形式
第一抽屜原理
原理1: 把多于n個(gè)的物體放到n個(gè)抽屜里,則至少有一個(gè)抽屜里的東西不少于兩件。
證明(反證法):如果每個(gè)抽屜至多只能放進(jìn)一個(gè)物體,那么物體的總數(shù)至多是n,而不是題設(shè)的n+k(k≥1),故不可能。
原理2 :把多于mn(m乘以n)個(gè)的物體放到n個(gè)抽屜里,則至少有一個(gè)抽屜里有不少于m+1的物體。
證明(反證法):若每個(gè)抽屜至多放進(jìn)m個(gè)物體,那么n個(gè)抽屜至多放進(jìn)mn個(gè)物體,與題設(shè)不符,故不可能。
原理3 :把無窮多件物體放入n個(gè)抽屜,則至少有一個(gè)抽屜里 有無窮個(gè)物體。
原理1 、2 、3都是第一抽屜原理的表述。
第二抽屜原理
把(mn-1)個(gè)物體放入n個(gè)抽屜中,其中必有一個(gè)抽屜中至多有(m—1)個(gè)物體。
證明(反證法):若每個(gè)抽屜都有不少于m個(gè)物體,則總共至少有mn個(gè)物體,與題設(shè)矛盾,故不可能。
學(xué)習(xí)鳥網(wǎng)站是免費(fèi)的綜合學(xué)習(xí)網(wǎng)站,提供各行各業(yè)學(xué)習(xí)資料、學(xué)習(xí)資訊供大家學(xué)習(xí)參考,如學(xué)習(xí)資料/生活百科/各行業(yè)論文/中小學(xué)作文/實(shí)用范文實(shí)用文檔等等!
聲明:本網(wǎng)站尊重并保護(hù)知識(shí)產(chǎn)權(quán),根據(jù)《信息網(wǎng)絡(luò)傳播權(quán)保護(hù)條例》,如果我們轉(zhuǎn)載的作品侵犯了您的權(quán)利,請?jiān)谝粋€(gè)月內(nèi)通知我們,我們會(huì)及時(shí)刪除。
蜀ICP備2020033479號(hào)-4 Copyright ? 2016 學(xué)習(xí)鳥. 頁面生成時(shí)間:0.286秒