비둘기집 원리(Pigeonhole Principle)

이 글에서는 비둘기집 원리와 그 응용에 대해 설명합니다.

1. 역사적 배경

유한집합에서, $n+1$개의 개체를 $n$개 이하의 집합으로 쪼개면 적어도 하나의 집합이 둘 이상의 원소를 가지게 된다는 것은 조금만 생각해도 알 수 있는 내용이고, 귀류법을 통해 정확한 증명도 가능합니다. 이것을 비둘기집 원리라고 합니다.

이 간단한 개념을 수학적 원리로 활용할 생각을 처음 한 사람은 디리끌레(Peter Gustav Lejeune Dirichlet, 1805-1859, Germany)입니다. 1834년 그는 이 원리를 Schubfachprinzip이라는 이름으로 발표했습니다. Schubfach는 서랍이라는 뜻을 가진 독일어 입니다. 디리끌레가 처음 이 원리를 설명할 때는 서랍에 진주를 나눠넣는 모델을 가지고 설명했습니다. 그래서, 비둘기집 원리는 ‘디리끌레의 서랍원리’라고도 부릅니다.

디리끌레가 사용했던 “서랍”이라는 단어는 pigeonhole이라는 단어로 점차 바꿔서 사용이 되었습니다. pigeonhole로 바뀌던 당시의 pigeonhole의 뜻은 아래 사진과 같은 개방형 선반에 가깝습니다.

스텐포드 대학의 Pigeon-hole messageboxes. Stacalusa [CC0], via Wikimedia Commons

디리끌레 시대에 이해되었던 pigeonhole의 개념은 독일어가 아닌 지역을 거쳐가면서 점차 오해가 생기기 시작했고, 결국 영어로 된 문서들이 역으로 독일어로 번역이 되는 과정에서 ‘비둘기집’이라는 뜻을 가지게 되었습니다.(Karl-Heinz Zimmermann, Diskrete Mathematik, Self Publishing, 2006)

에르되시 팔(Paul Erdös, 1913-1996)을 비롯한 몇몇 수학자들은 데데킨트(Richard Dedekind, 1831-1916)가 Was sind und was sollen die Zahlen(What are and What should the numbers be, 수는 무엇이며 무엇이 되어야 하는가; 1888)에서 유한집합을 다음과 같이 정의한 것을 수학적으로 비둘기집 원리를 잘 표현한 것으로 보아 비둘기집 원리를 데데킨트의 원리라 부르기도 했습니다.

집합 $X$가 유한집합이라는 것은 $X$의 진부분집합 $Y$가 무엇이 되든 $X$에서 $Y$로의 일대일대응을 만들 수 없다는 것이다.

2. 비둘기집 원리의 증명

비둘기집의 원리는 근본적으로 위에서 언급한 유한집합의 정의와 동일합니다. 하지만, 증명을 위해서 우리가 증명할 문장을 명시할 필요가 있겠죠. 여기서는 비둘기집의 원리를 다음과 같은 형태로 다루겠습니다.

$n$개의 서랍에 $n$개가 넘는 진주를 넣었다면 적어도 하나의 서랍에는 둘 이상의 진주가 들어있다.

증명: 귀류법

모든 서랍에 한 개 이하의 진주가 있다면 서랍에 들어 있는 진주는 많아야 $n$개이므로 모순이다. 따라서, 적어도 하나의 서랍에는 하나가 넘는 진주가 들어있어야 한다.

증명: 수학적 귀납법

편의상 정리의 문장을 $A(n)$이라 하자.

$A(1)$은 가정과 결론이 같은 문장의 조건문이므로 당연히 성립한다. 이제, $A(n)$이 성립한다고 가정하자.

$n+1$개의 서랍에 $n+1$개가 넘는 진주를 넣었다고 하자. 이제 하나의 서랍을 열어보자.

Case 1: 열린 서랍에 진주가 하나 넘게 있을 때
이 서랍이 둘 이상의 진주를 포함하는 서랍이 된다.

Case 2: 열린 서랍에 진주가 하나 이하로 있을 때
그러면 열리지 않은 서랍은 $n$개이고, 이들 서랍에 들어 있는 진주의 개수는 $n$개가 넘는다. 따라서, 수학적 귀납법에 의해 아직 열리지 않은 서랍 중 어느 하나에는 둘 이상의 진주가 있어야 한다.

Case 1, Case 2에 의하여 $A(n+1)$도 성립함을 확인할 수 있다. 그러므로, 수학적 귀납법에 의해 $A(n)$은 모든 자연수 $n$에 대해 성립한다.

3. 적용예

여기서는 비둘기집 원리를 이용해서 설명할 수 있는 사실들을 (정석에 들어있는 내용이 아닌 것으로) 소개해 보겠습니다.

(1) 디리끌레의 근사정리(Dirichlet's Approximation Theorem)

임의의 무리수 $\alpha$와 2 이상의 자연수 $Q$에 대해 다음 부등식을 만족하는 두 정수 $p$, $q$($0 \lt q \lt Q$)가 존재한다. $$|q \alpha - p | \leq \frac 1 Q$$

이 정리는 1840년에 디리끌레가 비둘기집 원리를 이용해서 증명한 정리입니다. 단순해 보이는 비둘기집 원리가 얼마나 강력한 도구가 될 수 있는지를 보여준 첫 번째 예라 할 수 있고, 개념적으로는 모든 무리수는 유리수를 통해 얼마든지 가깝게 근사할 수 있다는 내용을 담고 있습니다.

증명을 위해 다음과 같은 $Q+1$개의 수를 생각합시다.(단, $[x]$는 $x$보다 작거나 같은 정수 중 최댓값을 표현하는 기호입니다.) $$0, \quad 1, \quad \alpha - [\alpha], \quad 2\alpha -[2 \alpha], \quad (Q-1)\alpha -[(Q-1)\alpha] $$

이 수들은 모두 0이상 1이하의 값을 가집니다. 또한, $\alpha$가 무리수이므로 이 수들은 모두 다른 수입니다. 이제, 구간 $[0,1]$을 $Q$등분하면 비둘기집 원리에 의해 어느 한 구간에는 위 수 중 두 수가 들어있게 됩니다. 어떤 두 수가 되었든 두 수의 차는 $|q \alpha -p|$ ($0 \lt q \lt Q$)의 꼴로 쓸 수 있고 그 값이 $1/Q$ 이하가 되므로 위 정리가 증명됩니다.

(2) 연속합

임의의 정수 $a_1$, $a_2$, $\cdots$, $a_n$이 주어져 있으면 적당한 연속합 $a_k + a_{k+1} + \cdots + a_{k+m}$은 $n$의 배수다.

증명: $S_k = a_1 + a_2 + \cdots +a_k$($k=1$, 2, $\cdots$, $n$)라 하겠습니다. 만약 $S_k$ 중 하나가 $n$의 배수라면 더 증명할 것이 없습니다. 만약 $S_k$가 모두 $n$의 배수가 아니라면 $S_k$를 $n$으로 나눈 나머지는 1, 2, $\cdots$, $n-1$의 값만 가질 수 있다. 그런데, $S_k$의 값은 $n$개이므로 비둘기집 원리에 의해 적어도 두 개의 수는 $n$으로 나눈 나머지가 같게 됩니다. 이 두 수를 $S_i$, $S_j$($i \lt j$)라 하면 $S_j - S_i = a_{i+1} + \cdots + a_j$는 $n$으로 나누어 떨어진다.

(3) 중국인의 나머지 정리

서로소인 두 자연수 $m$, $n$이 있고, 두 정수 $a$, $b$가 $0 \le a \lt m$, $0 \le b \lt n$을 만족한다고 하자. 그러면 $x \equiv a (\text{mod } m)$이고 $x \equiv b (\text{mod }n)$인 정수 $x$가 있다.

증명: $m$으로 나눠서 $a$가 남는 다음과 같은 $n$개의 수를 생각해 보겠습니다. $$a, \quad a+m, \quad a+2m, \quad \cdots, \quad a+(n-1)m$$ 우리는 이 수들를 $n$으로 나눌 때 중 적어도 하나는 나머지가 $b$라는 것을 증명하려고 합니다.

위 $n$개의 수 중 나머지가 $b$인 수가 없다고 하면 $n$으로 나눈 나머지로 가능한 값이 $n-1$가지만 가능하게 되므로 적어도 두 수는 $n$으로 나눈 나머지가 같아야 합니다. 이 두 수를 $a + q_1 m$, $a+ q_2 m$이라 합시다.

그러면 두 수의 차 $(a+q_1 m) - (a+q_2 m) = (q_1 -q_2)m$은 $n$으로 나누어 떨어져야 합니다. 하지만 $m$, $n$이 서로소였으므로 $n$이 $q_1 - q_2$를 나눠야 하는데 $0 \lt |q_1 -q_2 | \lt n$이므로 이는 모순이 됩니다. 따라서, 위 $n$개의 수 중 적어도 하나는 나머지가 $b$가 되어야 합니다.

(4) Anti Magic Square

** 이 부분은 Steven H. Weintraub의 The Induction Book을 참고했습니다.

$n$차 Anti Magic Square란 $n \times n$ 정사각행렬로 행, 열, 대각선의 숫자의 합이 모두 다른 것을 말합니다. 예를 들면 다음과 같은 것들이 있습니다. $$ \left[ \begin{matrix} 9 & 4 & 5 \\ 10 & 3 & -2 \\ 6 & 9 & 7 \end{matrix} \right] , \quad \left[ \begin{matrix} 7&3&6&9 \\ 4&-9 & 5 & 3 \\ 8& 1& 3& 7 \\ 3& 9 & 0 & 5 \end{matrix} \right] $$ 다음과 같은 결과는 비둘기집 원리를 이용해서 설명이 가능합니다.

행렬의 모든 성분이 $-1$, $0$, $1$로 가지는 $n$차 anti magic square는 존재하지 않는다.

증명: $-1$, 0, 1만을 성분으로 하는 $n$차 정사각행렬의 행, 열, 대각선의 합으로 가능한 값은 $-n$, $-n+1$, $\cdots$, $n$으로 $2n+1$개인데, $n$차 정사각행렬은 행이 $n$개, 열이 $n$개, 대각선이 두 개이므로 이 행렬이 anti magic square가 되려면 $2n+2$개의 서로 다른 합이 필요하다. 따라서, $-1$, $0$, $1$로는 anti magic square는 존재하지 않는다.

4. 비둘기집 원리의 일반화

비둘기집 원리는 여러 가지 방식으로 일반화가 가능합니다. 유한집합 버전 중 복잡한 기호를 최대한 적게 사용한 꼴은 아마도 다음이 아닐까 합니다.

$nk+1$개가 넘는 진주가 $n$개의 서랍에 들어있다면 적어도 하나의 서랍에는 $k+1$개의 진주가 들어있다.

여기까지는 각 서랍에 들어가게 될 진주의 숫자를 일정한 숫자 $k$를 기준으로 해서 관찰하지만, 이 숫자를 일반화하면 다음과 같은 비둘기집 원리도 생각해낼 수 있습니다.

$r_1$, $r_2$, $\cdots$, $r_n$을 자연수라 하고, 1, 2, $\cdots$, $n$의 번호가 붙은 $n$개의 서랍이 있다고 하자. 이 서랍에 $\displaystyle{\sum_{i=1}^n r_i -n+1}$개의 진주를 나눠 넣는다면 적어도 한 자연수 $k$($1 \leq k \leq n$)에 대해서는 $k$번 서랍에 $r_k$개 이상의 진주가 들어있어야 한다.

비둘기집 원리를 무한집합으로도 확장할 수 있는데, 이 분야로 오면 원리라기보다는 Ordinal number의 정의라고 봐야 합니다.