비둘기집 원리

비둘기집 원리는 " 몇 마리의 비둘기가 그보다 작은 갯수의 비둘기집에 나뉘어 들어간다면, 두 마리 이상의 비둘기가 들어있는 비둘기집이 존재한다. " 라는 원리를 말한다. 증명이 필요치 않을 정도로 자명한 원리지만, 굳이 증명하자면 '귀류법'으로 증명할 수 있다. 비둘기와 비둘기집을 상황에 맞는 여러가지 수학적 대상으로 바꾸어넣어 다양한 증명에 이용하며, 경우에 따라서는 비둘기와 비둘기집을 '서랍과 양말' 로 비유하여 서술하기 때문에 '서랍 원칙' 또는 '디리클레의 방 나누기 원칙' 이라고 부르기도 한다.

예제

일견 자명해 보이는 비둘기집 원리는 때로 놀라운 결과를 보여주기도 한다. 예를 들면, 서울에는 머리카락의 수가 같은 사람이 최소한 두 명 존재한다.. 왜냐하면 일반적인 사람의 머리카락 수는 15만개이다. 그러므로 100만개 이상의 머리카락을 가진 사람은 없다고 가정해도 무리가 없다. 서울에는 1000만 명 가량의 사람이 있으므로, 서로 다른 머리카락의 개수를 서로 다른 비둘기집으로 보고, 서울에 사는 사람 각각을 머리카락의 개수에 따라 서로 다른 비둘기집에 할당하면, 같은 머리카락 개수를 가진 사람이 반드시 존재한다는 것을 알 수 있다.

또다른 좀 더 일상적인 예제로는, 소프트볼을 하고 싶어하는 5명의 사람 있다고 할 때, 서로 같은 팀에서 경기를 하고 싶어하지 않지만 팀은 4개 뿐인 경우를 생각해볼 수 있다. 만약 이 사람들이 서로 다른 팀에 들어가고 싶어할 경우, 비둘기집의 원리에 의해 5명의 사람을 한 팀에 한 명씩 4개의 팀으로 나누는 것은 불가능하다는 것을 알 수 있다.

컴퓨터과학에서도 비둘기집 원리의 예를 종종 찾아볼 수 있다. 예를 들어, 해쉬 테이블에서 가능한 모든 키의 숫자는 테이블 인덱스의 개수보다 많으므로 충돌은 불가피하다. 따라서 어떤 해쉬 알고리즘도 충돌을 피할 수는 없다. 또한, 모든 파일을 임의의 크기 S 이하로 압축하는 비손실 압축 알고리즘은 존재하지 않는다. S 이하의 크기를 갖는 파일의 개수는 정해져 있으므로, 그런 알고리즘이 존재한다면 동일한 파일로 압축되는 두 개의 서로 다른 파일이 반드시 존재할 것이므로 두 파일을 다시 원래대로 복원하는 것이 불가능할 것이다.

어느 그룹에 자신이 속해 있을 때, 그 그룹에서 자신과 생일이 같은 사람이 반드시 1명 이상 존재한다고 말할 수 있으려면, 그 그룹의 인원은 367명 이상이어야 한다(2월 29일도 포함). 왜냐하면 1년의 총 날짜의 수는 2월29일을 포함하여 366개 이므로 그룹의 인원이 367명 이상이면 생일이 같은 사람이 반드시 1쌍 이상 존재하기 때문이다.

또 앞이 보이지 않는 방에서 4쌍의 다른 양말이 널려 있을 때, 5개 이상의 양말을 고르면, 반드시 양말의 짝을 맞추어 신을 수 있다.

비둘기집 원리의 일반화

일반화 된 비둘기집 원리는 다음과 같다.

n개의 별개의 사물을 m개의 용기에 나누어 담으면 적어도 한 개의 용기는 $\left\lceil \frac n m \right\rceil$ 이상의 사물을 담고 있어야 한다.(여기서, $\lceil\dots\rceil$는 올림 함수를 의미한다.)

확률론적으로 일반화 된 비둘기집 원리는 다음과 같다.

$\frac 1 m$의 균일한 확률로 n개의 비둘기를 무작위로 m개의 비둘기집에 넣었다면 확률적으로 적어도 하나의 비둘기집에 두마리 이상의 비둘기가 들어가게 된다.

$1 - \frac{m!}{(m-n)!\;m^n} = 1 - \frac{m(m-1)(m-2)\cdots (m-n+1)}{m^n} \!$

n = 0 인 경우와, n = 1인 경우(단, m > 0)에 확률은 0인데, 달리 말하면 비둘기가 한마리 밖에 없다고 하면, 충돌(한 비둘기집에 두 마리 이상의 비둘기가 들어가는 일)이 일어날 수 없다는 것이다. n > m (비둘기가 비둘기집보다 많다)이라면 확률은 1이 되고 이런 경우에는 보통의 비둘기집 원리와 같은 일이 일어난다. 그러나 비둘기의 수가 비둘기집의 수를 초과하지 않는다 하더라도 ($n \le m$), 비둘기 분배의 무작위적인 성질에 의하여 종종 상당한 확률로 충돌이 일어난다. 예를 들어, 2마리의 비둘기가 무작위로 4개의 비둘기집에 분배된다면, 25%의 확률로 적어도 하나의 비둘기집에 두마리 이상의 비둘기가 들어가게 될 것이며, 5마리의 비둘기를 10개의 비둘기집에 분배한다면 확률은 69.76%가 되고, 10마리의 비둘기를 20개의 비둘기집에 분배하면 그 확률은 약 93.45%가 된다..