비둘기집 원리 문서 원본 보기

{{위키데이터 속성 추적}}
{{출처 필요|날짜=2013-1-26}}
[[파일:TooManyPigeons.jpg|섬네일]]
'''비둘기집 원리'''는 n+1개의 물건을 n개의 상자에 넣을 때 적어도 어느 한 상자에는 두 개 이상의 물건이 들어 있다는 원리를 말한다. 보통 비둘기와 비둘기집의 형태로 비유되어 쓰이며, '서랍과 양말'로 비유하여 '''서랍 원칙''' 또는 '''디리클레의 방 나누기 원칙'''이라고 부르기도 하며 '''구두 상자의 원리'''라고도 한다.

== 증명 ==
간단한 귀류법으로 증명할 수 있다. 모든 비둘기가 집에 들어간다는 가정 하에
{{인용문|<math>n</math>개의 비둘기집과 <math>n+1</math>마리의 비둘기가 있다고 가정한다. <br />만약 각 비둘기집에 한 마리 이하의 비둘기만 들어 있다면, 전체 비둘기집에는 많아야 <math>n</math>마리의 비둘기가 존재한다. 그런데 비둘기는 모두 <math>n+1</math>마리이므로, 이것은 모순이다. 따라서 어느 비둘기집에는 두 마리 이상의 비둘기가 있다.}}

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

== 용례 ==

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

== 비둘기집의 원리의 일반화 ==


일반화된 비둘기집 원리는 다음과 같다.
{{인용문|<math>n</math>개의 별개의 사물을 <math>m</math>개의 용기에 나누어 담으면 적어도 한 개의 용기는 <math>\left\lceil \frac n m \right\rceil</math> 이상의 사물을 담고 있어야 한다. (여기서, <math>\lceil x\rceil</math>는 <math>x</math>보다 작지 않은 최소 정수를 의미한다.)}}

확률론적으로 일반화된 비둘기집 원리는 다음과 같다.
{{인용문|<math>\frac 1 m</math>의 균일한 확률로 <math>n</math>개의 비둘기를 무작위로 <math>m</math>개의 비둘기집에 넣었다면 확률적으로 적어도 하나의 비둘기집에 두마리 이상의 비둘기가 들어가게 된다.}}
::<math>1 - \frac{m!}{(m-n)!\;m^n} = 1 - \frac{m(m-1)(m-2)\cdots (m-n+1)}{m^n} \!</math>
<math>n = 0</math> 인 경우와, <math>n = 1</math>인 경우(단, <math>m > 0</math>)에 확률은 0인데, 달리 말하면 비둘기가 한마리 밖에 없다고 하면, 충돌(한 비둘기집에 두 마리 이상의 비둘기가 들어가는 일)이 일어날 수 없다는 것이다. <math>n > m</math> (비둘기가 비둘기집보다 많다)이라면 확률은 1이 되고 이런 경우에는 보통의 비둘기집 원리와 같은 일이 일어난다. 그러나 비둘기의 수가 비둘기집의 수를 초과하지 않는다 하더라도 (<math>n \le m</math>), 비둘기 분배의 무작위적인 성질에 의하여 종종 상당한 확률로 충돌이 일어난다. 예를 들어, 2마리의 비둘기가 무작위로 4개의 비둘기집에 분배된다면, 25%의 확률로 적어도 하나의 비둘기집에 두마리 이상의 비둘기가 들어가게 될 것이며, 5마리의 비둘기를 10개의 비둘기집에 분배한다면 확률은 69.76%가 되고, 10마리의 비둘기를 20개의 비둘기집에 분배하면 그 확률은 약 93.45%가 된다.
== 같이 보기 ==
* [[선택 공리]]
* [[힐베르트 호텔]]
* [[다항 정리]]
* [[램지의 정리]]

[[분류:수학 정리]]
[[분류:이산수학]]
[[분류:이산수학 정리]]
[[분류:램지 이론]]