鴿籠原理

標籤: 暫無標籤

81

更新時間: 2013-12-12

廣告

鴿籠原理 (抽屜原理) 「如果有五個鴿子籠,養鴿人養了6隻鴿子,那麼當鴿子飛回籠中后,至少有一個籠子中裝有2隻鴿子。」這個簡單的事實就是著名的鴿籠原理,在我們國家更多地稱為抽屜原理。

鴿籠原理 -介紹

鴿籠原理鴿籠原理
"如果有五個鴿子籠,養鴿人養了6隻鴿子,那麼當鴿子飛回籠中后,至少有一個籠子中裝有2隻鴿子."這個簡單的事實就是著名的鴿籠原理,在我們國家更多地稱為抽屜原理.抽屜原理的更一般的敘述是:有n+1件或n+1件以上的物品要放到n個抽屜中,那麼至少有一個抽屜里有兩個或兩個以上物品.此原理用反證法容易證明其正確性.抽屜原理雖然簡單,但應用卻很廣泛,它可以解答很多有趣的問題,其中有些問題還具有相當的難度.下面我們來研究有關的一些問題.問題1某校初中部有30個班,每班平均52人.已知這些學生的90%都是在1978~1980年這三年出生的,問他們中有同年同月同日出生的嗎
解:全校共有學生52×30=1560人,1978~1980年間出生的有1560×90%=1404人.
而這三年有365×3+1=1096天.
由鴿籠原理知道,至少有兩個同學是同年同月同日出生的.
問題2一個書架有五層,從下至上依次稱第1,第2,…,第5層.今把15冊圖書分別放在書架的各層上,有些層可以不放,證明:無論怎樣放法,書架每層上的圖書冊數以及相鄰兩層內圖書冊數之和,所有這些數中至少有兩個是相等的.
解:我們先把這個實際問題抽象成數學問題.用xi表示第i層放書的冊數(i=1,2,…,5).
若有某個xi=0,則相鄰的一層放書冊數等於它與第i層放書冊數之和,結論成立.下面考慮xi≥1(i=1,2,3,4,5)的情況:
(1)若x1,x2,…,x5中已有兩數相等,結論成立.
(2)若x1,x2,…,x5兩兩不等,再由它們和為15,所以它們分別取1,2,3,4,5.我們容易驗證,在x1+x2,x2+x3,x3+x4,x4+x5這四個數中不可能同時包含6,7,8,9這四個數(請讀者驗證).這四個數與x1,x2,…,x5總共九個數,但只能有8種取值,因此其中必有兩數相等.

廣告

問題3某個信封上兩個郵政編碼M和N均由0,1,2,3,5,6這六個不同數字組成,現有4個郵政編碼如下:A:320651,B:105263,C:612305,D:316250.已知編碼A,B,C各恰有兩個數字的位置與M和N相同,D恰有三個數字的位置與M和N相同,試求M和N解:首先仔細觀察A,B,C.它們雖然均由0,1,2,3,5,6這六個數碼組成,但同一數位上的數字都互不相同.由鴿籠原理知A,B,C三數中各數位上都有一個數字是正確的(即與M和N的相應數字相同).再把D的各數位上的數與A,B,C比較,發現D中第3位的6和第6位的0在A,B,C的第3和第6位上沒有出現,因此這兩個數碼肯定不正確.由已知D有三個數字正確,因此D中的3,1,2,5四個數字中只有一個不對.下面逐個討論驗證:若3不對,則第2位的1對,因此這個數位上只能取6,第2位取1,第3位不能取2,5(因為2,5在第4,5位是對的)所以第3位取0,第4位取2,第五位取5,剩下第6位必取3,此數字為610253.

若1不對,則第1位的3對,第2位只能取0(因2在第4位是對的),第3位上A,B,C的數各為0,5,2,這三個數均不能取(因0已在第2位,而5,2已在第5,4位).因此,這時沒有符合要求的取數法.若2不對,則第1位取3,第2位取1都對.第3位可以取0或2,第4位只能取6,第5位取5.但第6位取A,B,C的數各是1,3,5,這3個數都在前面被取過,因此都不能取.這時也沒有符合要求的取數法.

鴿籠原理 -參考資料

http://www.programfan.com/club/showtxt.asp?id=76291

廣告