鴿籠原理的一般性敘述及證明

Question

把m隻鴿子全部關進n個籠子裡(m,n為正整數)，則至少有一個籠子有x隻以上的鴿子。試以m,n表示x的最大值，並證明。


題目詳述：
(1)所有的鴿子都要關進籠子裡，相反的，我並沒有說所有的籠子裡都要有鴿子，所以有的籠子裡可以沒有任何鴿子。
(2)以實例說明吧！有121隻鴿子，關進13個籠子裡，我可以說至少有一個籠子有2隻以上的鴿子，我可以說至少有一個籠子有7隻以上的鴿子，我還能說至少有一個籠子有10隻以上的鴿子，這些都對，但我不能說至少有一個籠子有11隻以上的鴿子，它不一定對，所以x=10就是m=121，n=13時的最大值，m,n為其他數時，x的最大值也可能會改變，而我現在要一般化，以m,n表示x的最大值。
(3)證明應該包括兩部份：第一部份，x可使「至少有一個籠子有x隻以上的鴿子」這個敘述恆真；第二部份，該x值是最大值。亦即當x更大時，「至少有一個籠子有x隻以上的鴿子」就不一定為真了。
(4)這個證明我自己應該會證(如果我沒推理錯誤的話)，會在這裡問，多少是為了豐富知識+的內容，既然鴿籠原理很有名，那就來個一般化吧！

Answer 1

x = ┌m/n┐若非則每個籠子最多┌m/n┐-1隻鴿子則最多只有n(┌m/n┐-1)隻鴿子但m/n≦┌m/n┐＜m/n+1m/n-1≦┌m/n┐-1＜m/nm-n≦n(┌m/n┐-1)＜n所以最多只有n-1隻鴿子與已知的n隻鴿子矛盾

2005-06-15 08:46:58 補充：
當平均分配時
每個籠子不是┌m/n┐隻就是└m/n┘隻
那如果有一個籠子有┌m/n┐+1隻
那總數就超過n了

Answer 2

我見過所有證明鴒籠原理的都是用反證法。你可以把題目改寫成：設 A, B 為兩非空有限集合，f: A --> B，那麼對於 B 內的某一元素 j, f^{-1}{j} 至少有 |A|/|B| 個元素。
－－－證明，若非，則對所有 B 內的元素 j, f^{-1}(j) 的元素個數都少於 |A|/|B|，所以全加起來，|A| = Σ_B f^{-1}(j) < Σ_B |A|/|B| = |B||A|/|B| = |A|，矛盾。

2005-06-18 04:55:53 補充：
阿克真的要一般化麼？那麼要變一個看起來不是那麼明顯的。
(1)設 a, b 為自然數，n = ab+1 及 {x_i}為 n 個項數的數列，那麼必有一個單調增加，共有 a+1 項的子數列，或是有一個單調減少，共有 b+1 項的子數列。命題中的增加及減少兩詞可互換。

2005-06-18 05:16:34 補充：
(2)Sperner 定理：設 T 為一個有 t 元素的集合，且有一堆 T 的子集合，他們之間並不互相包含，那麼這堆子集合最大的個數為 C(t, [t/2])。
(3) Schur 引理：對每一自然數 k, 都有正整數 s(k) 使得無論如何分割 {1, ..., s(k)} 成 k 類，其中一類中必有三個整數 x, y, z，使得 x + y = z。〔x, y 容許相等〕

2005-06-18 05:17:03 補充：
隨便舉一個從此引伸的數學問題：設有 n 個球，以號碼 {1, 2, ..., n} 代表，現要分別把它們放進三個箱子裡，而且規定任何滿足 x+y=z 的三個號碼球都不能同一箱子裡，這問題有解的 n 最大是多少？

Answer 3

一般用的時候，似乎m必須大於n，其實不必，3隻鴿子5個籠子，你可以說至少有一個籠子有1隻鴿子呀！

2005-06-14 18:04:55 補充：
dd：
你沒有說明為什麼┌m/n┐是最大值。亦即當x≧┌m/n┐+1時，「至少有一個籠子有x隻以上的鴿子」就不一定成立了，為什麼呢？

Answer 4

請問m恆大於n嗎?

2005-06-14 01:55:13 補充：
不是證明矛盾吧!
因為m不恆大於n會使這個證明比較複雜一點
而且x=m/n會在這個不恆大於之下矛盾
不過我不太懂┌和┐代表的數學符號@@