[Discrete Mathematics] 비둘기집 원리(pigeonhole principle)

---

비둘기집 원리

 

$ k $ 개의 비둘기집에 $ n $ 마리의 비둘기가 들어갈 때 $ k < n $ 이라 하면 비둘기가 $ 2 $ 마리 이상 들어있는 비둘기집이 반드시 존재한다는 원리이다. 비둘기와 비둘기집으로 예를 들었지만, 범주의 종류가 정해져 있는 상황에서, 특정 집합에 이를 할당할 경우 과잉 할당이 불가피한 경우를 보여주는 것이다. 즉 최소 하나의 집합 원소에 중복된 할당이 발생함을 보인다.

비둘기가 $ n +1 $ 마리, 비둘기 집이 $ n $ 개라 할 때 한 집당 한 마리의 비둘기가 들어가 있다고 가정하면, 이미 모든 집에는 비둘기가 들어가 있는데 한 마리의 비둘기는 들어가지 못했기 때문에 이 비둘기 한 마리를 어느 집에 할당해도 특정 비둘기 집은 두 마리의 비둘기가 들어가게 된다. 즉 $ n $ 개의 비둘기 집이 존재할 때 비둘기가 $ n $ 마리를 초과한다면, 그리고 모든 비둘기가 비둘기 집에 들어간다면 반드시 두 마리 이상이 들어가 있는 비둘기 집이 존재한다.

 

---

확장

 

$ f $ 가 유한 집합 $ X $ 에서 유한 집합 $ Y $ 로의 함수이고, $ | X | > | Y | $ 라 할 때, $ x_1, x_2 \in X $ $ (x_1 \neq x_2) $ 인 $ x_1, x_2 $ 에 대하여 $ f(x_1) = f(x_2) $ 인 경우가 반드시 존재한다.

나아가 $ f $ 가 유한 집합 $ X $ 에서 유한 집합 $ Y $ 로의 함수이고, $ | X | = n $, $ | Y | = m $ 이며, $ k = \lceil n / m \rceil $ 이라 하자. 그렇다면 $ f(a_1) = f(a_2) = \cdots = f(a_k) $ 를 만족하는 $ k $ 개의 서로 다른 $ a_1, a_2, \dots, a_k \in X $ 가 존재한다.

증명은 다음과 같은데, 모순법을 사용한다.

$ Y = \{ y_1, y_2, \cdots, y_m \} $ 이라 하고 결론을 거짓이라 가정하자. 그렇다면 $ f(x) = y_1 $ 이 되는 $ x \in X $ 는 많아야 $ k - 1$ 개이고, $ f(x) = y_2 $ 가 되는 $ x \in X $ 도 많아야 $ k -1 $ 개이며, 나아가 $ f(x) = y_i $ $ ( i = 1, 2, \cdots, m) $ 이 되는 $ x \in X $ 도 많아야 $ k -1 $ 개 이다. 따라서 정의역의 원소는 많아야 $ m (k-1) $ 개이다.

그러나 $ m (k-1) < m \frac{n}{m} = n $  이므로, 즉 계산된 정의역의 원소의 최대치가 실제 정의역의 원소보다 적으므로 모순이다.