📂レンマ

ハトの巣原理

定理 ¹

有限集合 $A_{1} , \cdots , A_{n}$ が 互いに素で、これらの 和集合 の 基数 がある $r \in \mathbb{N}$ に対して $nr$ より大きいと仮定しよう。すると基数が $r$ より大きい集合 $A_{k}$ が少なくとも一つ存在する: $$ \left| A_{1} \cup \cdots \cup A_{n} \right| > nr \implies \exists k : \left| A_{k} \right| > r $$

説明

鳩ノ巣原理^{pigeonhole principle}は、その名の通り「鳩小屋の数より鳩の数が多いとき、少なくとも一つの鳩小屋に二羽以上の鳩が入っている」という原理を形式化したものだ。組合せ論全般で日常的に使われ、場合によってはこれが定理かもしれないと考える人もいるほどだ。

証明

背理法で証明する。任意の $k$ について $\left| A_{k} \right| \le r$ と仮定すると、$A_{k}$ たちが互いに素であると仮定したので $\bigcup_{k=1}^{n} A_{k}$ の基数は次のようになる。 $$ \begin{align*} & \left| A_{1} \cup \cdots \cup A_{n} \right| \\ =& \left| A_{1} \right| + \cdots + \left| A_{n} \right| \\ \le& \underbrace{r + \cdots + r}_{n \text{ times }} \\ =& nr \end{align*} $$ これは仮定と矛盾するから、$\left| A_{k} \right| > r$ を満たす $k$ が少なくとも一つ存在する。

■