8강. 비둘기집 원리와 포함배제

비둘기 13마리가 집 12개에 들어가면 어떤 집에는 두 마리 이상이 있습니다. 이렇게 당연해 보이는 원리가 의외로 강력한 증명 도구가 됩니다. 이 강에서는 비둘기집 원리와, 겹치는 부분을 더하고 빼서 정확히 세는 포함배제 원리를 다룹니다.

7강의 법칙은 “정확히 몇 개”를 셉니다. 이 강의 두 도구는 조금 다릅니다. 비둘기집 원리는 정확한 수 없이도 “적어도 하나는 있다”를 보이고, 포함배제 원리는 겹치는 부분을 더하고 빼서 정확히 셉니다.

8.1 비둘기집 원리

정리 8.1 (비둘기집 원리). $n + 1$마리 이상의 비둘기가 $n$개의 집에 들어가면, 두 마리 이상이 들어간 집이 있습니다.

증명. 모든 집에 한 마리 이하가 있다면 비둘기는 $n$마리 이하입니다. 대우입니다. □

함수로 말하면, $|A| > |B|$이면 $f : A \to B$는 단사가 아닙니다(5강의 정리 5.4).

예제 8.2. 13명이 있으면 생일이 같은 달인 두 사람이 있습니다(달이 12개).

예제 8.3. $\{1, 2, \dots, 2n\}$에서 $n + 1$개를 고르면 그중 합이 $2n + 1$인 두 수가 있습니다. 집을 $\{1, 2n\}, \{2, 2n-1\}, \dots, \{n, n+1\}$의 $n$쌍으로 잡으면 $n + 1$개 중 두 수가 같은 쌍에 들어갑니다.

예제 8.4. 정수 $n + 1$개 중에는 차가 $n$의 배수인 두 수가 있습니다. $n$으로 나눈 나머지($n$가지)를 집으로 잡습니다.

8.2 일반화된 비둘기집 원리

정리 8.5. $N$마리가 $k$개의 집에 들어가면, 적어도 $\lceil N/k \rceil$마리가 들어간 집이 있습니다.

증명. 모든 집에 $\lceil N/k \rceil - 1$마리 이하가 있다면 전체는 $k(\lceil N/k \rceil - 1) < k \cdot N/k = N$마리 이하이므로 모순입니다. □

예제 8.6. 100명 가운데 같은 달에 태어난 사람은 적어도 $\lceil 100/12 \rceil = 9$명 있습니다.

예제 8.7. 카드 52장(무늬 4개)에서 같은 무늬 3장을 반드시 얻으려면 $2 \cdot 4 + 1 = 9$장을 뽑으면 됩니다. 8장으로는 무늬마다 2장씩일 수 있습니다.

8.3 포함배제 원리

4강의 $|A \cup B| = |A| + |B| - |A \cap B|$를 셋 이상으로 늘립니다.

정리 8.8 (세 집합의 포함배제).

정리 8.9 (포함배제 원리).

증명. 원소 $x$가 정확히 $m \ge 1$개의 $A_i$에 들어 있다고 합시다. 우변에서 $x$는 $\binom{m}{1} - \binom{m}{2} + \binom{m}{3} - \cdots = 1 - \sum_{k=0}^m (-1)^k \binom{m}{k} = 1 - 0 = 1$번 세어집니다(7강의 따름정리 7.13). □

예제 8.10. 1부터 1000까지 2, 3, 5 가운데 어느 것의 배수: $500 + 333 + 200 - 166 - 100 - 66 + 33 = 734$개. 어느 것의 배수도 아닌 수는 $1000 - 734 = 266$개입니다.

8.4 교란순열

정의 8.11 (교란순열). $1, 2, \dots, n$을 늘어놓을 때 어느 $i$도 $i$번째 자리에 오지 않는 순열을 교란순열(derangement)이라 하고 그 수를 $D_n$으로 씁니다.

$n$명이 모자를 맡겼다가 무작위로 돌려받을 때 아무도 자기 모자를 받지 못하는 경우입니다.

정리 8.12. $D_n = n! \displaystyle\sum_{k=0}^{n} \frac{(-1)^k}{k!}$.

증명. $A_i$를 “$i$가 제자리에 있는 순열”이라 하면 $|A_{i_1} \cap \cdots \cap A_{i_k}| = (n-k)!$입니다. 포함배제로 제자리인 것이 하나라도 있는 순열은 $\sum_{k=1}^n (-1)^{k+1} \binom{n}{k}(n-k)!$개이고, $D_n = n! -$ 그것 $= \sum_{k=0}^n (-1)^k \frac{n!}{k!}$입니다. □

$D_1 = 0$, $D_2 = 1$, $D_3 = 2$, $D_4 = 9$, $D_5 = 44$입니다. $D_n / n!$은 $e^{-1} \approx 0.3679$로 갑니다. 사람이 많아져도 아무도 자기 모자를 못 받을 확률은 약 37%로 거의 일정합니다.

8.5 전사함수의 수

정리 8.13. $|A| = m$, $|B| = n$일 때 전사함수 $A \to B$의 수는

증명. $B$의 원소 $b_k$가 치역에 없는 함수의 집합을 $A_k$라 하면, $k$개의 원소를 빼먹는 함수는 $(n-k)^m$개입니다. 전체 $n^m$에서 포함배제로 하나라도 빼먹는 함수를 뺍니다. □

예제 8.14. 6명을 3개 팀에 배정하되 빈 팀이 없게 하는 방법: $3^6 - 3 \cdot 2^6 + 3 \cdot 1^6 = 729 - 192 + 3 = 540$가지입니다.

쓰이는 곳. 해시 충돌이 반드시 생긴다는 증명, 압축 알고리즘의 한계(모든 파일을 줄일 수는 없다), 오류 정정 부호의 한계가 비둘기집 원리입니다. 포함배제는 확률 계산과 데이터베이스 질의 최적화에서 쓰입니다.

8.6 이 장의 요약

• 비둘기집: 무엇이 비둘기이고 무엇이 집인지 정하는 것이 전부입니다. $\lceil N/k \rceil$.
• 포함배제: 홀수 개의 교집합은 더하고 짝수 개는 뺍니다.
• 교란순열 $D_n \approx n!/e$, 전사함수의 수.

문제

5

266

9
44
265

150

4