📂レンマ

ハトの巣原理

定理 ¹

有限集合 $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$ が少なくとも一つ存在する。

■