YLL討論網

─═☆〃迅雷疾風〃 · 由 **─═☆〃迅雷疾風〃** 於星期二十月 04, 2005 11:50 pm

鴿籠原理
鴿籠原理是說將 k 個東西分成 n 類，若  則有一類東西之數目大於或等於 r。十隻鴿子分放在九個籠中，必有一籠至少放二隻鴿子。五房客四房間，一定有二房客共一房間。三男追二女，必有二男為情敵。十三人同行，必有二人同月生。五人分十六本書，必然有人至少獨得四本書。這些都是鴿籠原理在生活中常碰到的實例。這樣平凡的道理人人在諸多待人接物中，不假思索屢用不爽。道理雖然簡單，巧妙地運用卻有意想不到的驚奇結果。

-------------------------------------------

廣義的鴿籠原理

給定非負的整數 q1, q2,…,qn，將 k 個東西分為 n 類，若  則一定有某第 i 類東西個數大於或等於 qi 個。這是鴿籠原理一般情況。它的證明很簡單，假若結論不確，即是說第 1 類東西小於 q1，第 2 類小於 q2，……第 n 類小於 qn。則所有東西總和

此與前提矛盾故不可能。當  時即為原來的鴿籠原理。

-------------------------------------------

鴿籠原理的挑戰

善用鴿籠原理常有奇妙驚人的結果，各位讀者，你是不是也想一顯身手，以下是鴿籠原理對你的挑戰。

§3.1. 任意 52個整數中，必定可以選取2個，使得其和或其差為 100 的倍數。

§3.2. 在邊長為1的正三角形上有十點，則必定有二點其距離至大為。

§3.3. 從 1 到 2n 的 2n 個自然數中任取 n+1 個數，必定有二數其一為另一的倍數或因數。

§3.4. 阿德今年高三畢業，距離大專聯考尚有37天。為了有效支配時間，他決定每天最少用1小時，總共用60小時準備數學科目的綜合溫習。不管阿德如何安排他的時間表（時間表以小時為單位），在一段連續的日子裡，阿德將花 13 小時在溫習數學上。

§3.5. 任意給定 mn+1 個自然數，必定有下列二情形之一發生： (i)可找到 m+1 個數 a1,a2, …, am+1 等，其中兩兩互不整除；或 (ii) 可找到 b1,b2, …, bn+1，等 n+1 個數，其中 b1 除盡 b2，b2 除盡 b3，…… bn 除盡 bn+1。
最後，我們以一個小故事結束本文。

§3.6. 世界人口何其多
大華好奇的問小明：「世界上有多少人，你知道嗎？」
小明裝大人樣說：「世界上的人不計其數，但至少比任何人的頭髮數還多。」
大華很有自信的又說：「這樣的話，世界上一定有兩人，他們的頭髮一樣多。」
想一想，為什麼大華那麼肯定而有自信。

☆ ~ 幻星 ~ ☆ · 由 **☆ ~ 幻星 ~ ☆** 於星期三十月 05, 2005 6:47 pm

§3.1. 任意 52個整數中，必定可以選取2個，使得其和或其差為 100 的倍數。

所有數可以寫成
100n,100n+1,100n+2,100n+3,....100n+99
因100n+x不能和100n+x及100n+(100x)同時出現
所以最濫情況的51個數可寫成
100n+x,100+x+1,100n+x+2,....10n+x+50
在來不管怎麼選都宜定是100n+x,100+x+1,100n+x+2,....10n+x+50
100n+x及100n+(100x)
所以任意 52個整數中，必定可以選取2個，使得其和或其差為 100 的倍數。

☆ ~ 幻星 ~ ☆ · 由 **☆ ~ 幻星 ~ ☆** 於星期三十月 05, 2005 6:49 pm

§3.6. 世界人口何其多
大華好奇的問小明：「世界上有多少人，你知道嗎？」
小明裝大人樣說：「世界上的人不計其數，但至少比任何人的頭髮數還多。」
大華很有自信的又說：「這樣的話，世界上一定有兩人，他們的頭髮一樣多。」
想一想，為什麼大華那麼肯定而有自信。

設世界人口數N
則每個最多頭髮數量只能N-1
但有N個人
1,2,3,4,.....n-1只有N-1個不同的數
最後一個數一定在1,2,3,4,.....n-1之間
所以得證

YLL討論網

[文章]抽屜定理-2

[文章]抽屜定理-2