비둘기집 원리

파일:TooManyPigeons.jpg

비둘기집 원리는 n+1개의 물건을 n개의 상자에 넣을 때 적어도 어느 한 상자에는 두 개 이상의 물건이 들어 있다는 원리를 말한다. 보통 비둘기와 비둘기집의 형태로 비유되어 쓰이며, '서랍과 양말'로 비유하여 서랍 원칙 또는 디리클레의 방 나누기 원칙이라고 부르기도 하며 구두 상자의 원리라고도 한다.

증명

간단한 귀류법으로 증명할 수 있다. 모든 비둘기가 집에 들어간다는 가정 하에

$n$
개의 비둘기집과
$n + 1$
마리의 비둘기가 있다고 가정한다.
만약 각 비둘기집에 한 마리 이하의 비둘기만 들어 있다면, 전체 비둘기집에는 많아야
$n$
마리의 비둘기가 존재한다. 그런데 비둘기는 모두
$n + 1$
마리이므로, 이것은 모순이다. 따라서 어느 비둘기집에는 두 마리 이상의 비둘기가 있다.

이 증명은 대표적인 존재증명이다. 즉, 비둘기가 두 마리 이상 존재하는 집이 정확히 어떤 집인지는 이 증명으로 알아낼 수 없다.

용례

소프트볼을 하고 싶어하는 5명의 사람이 있다고 할 때, 서로 같은 팀에서 경기를 하고 싶어하지 않지만 팀은 4개 뿐인 경우를 생각해볼 수 있다. 만약 이 사람들이 서로 다른 팀에 들어가고 싶어할 경우, 비둘기집의 원리에 의해 5명의 사람을 한 팀에 한 명씩 4개의 팀으로 나누는 것은 불가능하다는 것을 알 수 있다.
해시 테이블에서 가능한 모든 키의 숫자는 테이블 인덱스의 개수보다 많으므로 충돌은 불가피하다. 따라서 어떤 해시 함수도 충돌을 피할 수는 없다. -해시 충돌 참고
모든 파일을 임의의 크기 S 이하로 압축하는 비손실 압축 알고리즘은 존재하지 않는다. S 이하의 크기를 갖는 파일의 개수는 정해져 있으므로, 그런 알고리즘이 존재한다면 동일한 파일로 압축되는 두 개의 서로 다른 파일이 반드시 존재할 것이므로 두 파일을 다시 원래대로 복원하는 것이 불가능할 것이다.
어느 그룹에 생일이 같은 사람이 반드시 1쌍 이상 존재한다고 말할 수 있으려면, 그 그룹의 인원은 367명 이상이어야 한다. 생일의 경우의 수는 2월29일을 포함하여 366가지 이기 때문이다.
앞이 보이지 않는 방에서 4쌍의 다른 양말이 널려 있을 때, 5개 이상의 양말을 고르면, 반드시 양말의 짝을 맞추어 신을 수 있다.
13명의 사람들 중 태어난 달이 같은 사람이 최소 2명이상 있다.

비둘기집의 원리의 일반화

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

$n$
개의 별개의 사물을
$m$
개의 용기에 나누어 담으면 적어도 한 개의 용기는
$⌈ \frac{n}{m} ⌉$
이상의 사물을 담고 있어야 한다. (여기서,
$⌈ x ⌉$
는
$x$
보다 작지 않은 최소 정수를 의미한다.)

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

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

1 - \frac{m!}{(m - n)! m^{n}} = 1 - \frac{m (m - 1) (m - 2) \dots (m - n + 1)}{m^{n}}

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

같이 보기