鴿籠原理

鴿籠原理 (pigeonhole principle):$n+1$ 隻鴿子放進 $n$ 個籠子,必有一籠至少 2 隻。廣義版:$N$ 隻放 $n$ 籠,必有一籠至少 $\lceil N/n\rceil$ 隻。它顯然到不像定理,威力卻在於選對「籠子」。

反向問法「至少要幾個才保證」用最壞情況思考:要保證某籠有 $k$ 個,先讓每籠塞 $k-1$ 個(共 $n(k-1)$)都還不夠,再加 1 就一定行:$n(k-1)+1$。

算例:13 人必有兩人同月生日;要保證 3 人同月需 $12\times2+1 = 25$ 人;任取 5 個整數必有兩個除以 4 同餘。

經典應用:任意 $n+1$ 個不超過 $2n$ 的正整數中必有一個整除另一個;無損壓縮不可能對所有檔案都變小;Ramsey 理論「6 人中必有 3 人互識或互不識」。