📂보조정리

비둘기집 원리

정리 ¹

유한집합 $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$ 가 적어도 하나 존재한다.

■