鴿籠原理

鴿籠原理：
　　m 隻鴿子欲放入 n 個鴿籠中，其中 m > n，則至少有一個鴿籠包含至少二隻鴿子。

看起來很像廢話的一個定理，卻還蠻厲害的。先來個例題。

< 例1 >:
　　證明任意 n+1 個正整數，必有二數相減被 n 整除。

<證明>:
　　考慮任意 n+1 個正整數 A1, A2, A3, ..., An+1
　　令 Bi = Ai mod n, 即 Bi 為 Ai 除以 n 的餘數, 1 < i < n+1
　　則 Bi 屬於 {0, 1, 2, ..., n-1}

　　將 B1, B2, B3, ..., Bn+1 視為 n+1 隻鴿子, 0, 1, 2, ..., n-1 視為 n 個鴿籠
　　由鴿籠原理知至少一個鴿籠有至少二隻鴿子, 即存在 i, j, i != j 使得 Bi = Bj
　　--> Ai mod n = Aj
　　不失一般性令 Ai > Aj, 則 n 整除 (Ai - Aj) 。


< 例2 >:
　　1 ~ 9 的正整數中，任取六個不重複，必定包含二個數的和為 10。

<證明>:
　　將 1 ~ 9 分成五堆 {1, 9}, {2, 8}, {3, 7}, {4, 6}, {5}
　　由鴿籠原理知要從 1 ~ 9 的正整數中取 6 個數不重複, 至少會有二數取自同一堆
　　則此二數的和為 10。


鴿籠原理的推廣：
　　m 隻鴿子欲放入 n 個鴿籠中，其中 m> n，則至少有一個鴿籠包含至少┌m/n┐ 隻鴿子。

< 例3 >:
　　證明六個人中必有三人彼此相識或三人彼此不相識。

<證明>:
　　考慮任意六個人 a, b, c, d, e, f, 將 b, c, d, e, f 分成二堆, 一堆為與 a 相識者, 另一堆為與 a 不相識者, 由鴿籠原理知至少有一對有至少 ┌5/2┐ = 3 個人, 分成下列二種情形:

　　(1) 若與 a 相識那堆有至少三個人:
　　　不失一般性令 b, c, d 與 a 相識, 若 b, c, d 中有二人相識, 則此二人加上 a 共三人彼此相識, 得證。否則 b, c, d 三人彼此不認識, 亦得證。

　　(2) 若不與 a 相識那堆有至少三個人:
　　　不失一般性令 b, c, d 與 a 不相識, 若 b, c, d 中有二人不相識, 則此二人加上 a 共三人彼此不相識, 得證。否則, b, c, d 三人彼此認識, 亦得證。


　　相信這定理還可以用在許多日常生活的事情中，呵呵...