2-6. 鴿籠原理

Define Pigeonhole Principle

$m$ 隻鴿子欲飛入 $n$ 個籠子中，其中 $m$ > $n$，則存在至少一個籠子內含至少 2 (廣義: $\lceil \dfrac{m}{n} \rceil$)隻鴿子，鴿籠原理(pigeonhole principle)又稱抽屜原理(Dirichlet drawer/box principle)

函數的觀念:

• 每個定義域的元素皆要有對應 $\Rightarrow$ 每隻鴿子皆要飛入某個籠子
• 不可一對多 $\Rightarrow$ 一隻鴿子不能同時飛入多個籠子

$\rightarrow$ 若有 $n$ 個鴿籠，則至少要有 $n$ + $1$ 隻鴿子才可保證必有某個鴿籠至少含 2 隻鴿子