비둘기집 원리
이 문서의 내용은 출처가 분명하지 않습니다. (2013년 1월) |
비둘기집 원리는 n+1개의 물건을 n개의 상자에 넣을 때 적어도 어느 한 상자에는 두 개 이상의 물건이 들어 있다는 원리를 말한다. 보통 비둘기와 비둘기집의 형태로 비유되어 쓰이며, '서랍과 양말'로 비유하여 서랍 원칙 또는 디리클레의 방 나누기 원칙이라고 부르기도 하며 구두 상자의 원리라고도 한다.
증명
편집간단한 귀류법으로 증명할 수 있다. 모든 비둘기가 집에 들어간다는 가정 하에
개의 비둘기집과 마리의 비둘기가 있다고 가정한다.
만약 각 비둘기집에 한 마리 이하의 비둘기만 들어 있다면, 전체 비둘기집에는 많아야 마리의 비둘기가 존재한다. 그런데 비둘기는 모두 마리이므로, 이것은 모순이다. 따라서 어느 비둘기집에는 두 마리 이상의 비둘기가 있다.
이 증명은 대표적인 존재증명이다. 즉, 비둘기가 두 마리 이상 존재하는 집이 정확히 어떤 집인지는 이 증명으로 알아낼 수 없다.
용례
편집- 소프트볼을 하고 싶어하는 5명의 사람이 있다고 할 때, 서로 같은 팀에서 경기를 하고 싶어하지 않지만 팀은 4개 뿐인 경우를 생각해볼 수 있다. 만약 이 사람들이 서로 다른 팀에 들어가고 싶어할 경우, 비둘기집의 원리에 의해 5명의 사람을 한 팀에 한 명씩 4개의 팀으로 나누는 것은 불가능하다는 것을 알 수 있다.
- 해시 테이블에서 가능한 모든 키의 숫자는 테이블 인덱스의 개수보다 많으므로 충돌은 불가피하다. 따라서 어떤 해시 함수도 충돌을 피할 수는 없다. -해시 충돌 참고
- 모든 파일을 임의의 크기 S 이하로 압축하는 비손실 압축 알고리즘은 존재하지 않는다. S 이하의 크기를 갖는 파일의 개수는 정해져 있으므로, 그런 알고리즘이 존재한다면 동일한 파일로 압축되는 두 개의 서로 다른 파일이 반드시 존재할 것이므로 두 파일을 다시 원래대로 복원하는 것이 불가능할 것이다.
- 어느 그룹에 생일이 같은 사람이 반드시 1쌍 이상 존재한다고 말할 수 있으려면, 그 그룹의 인원은 367명 이상이어야 한다. 생일의 경우의 수는 2월29일을 포함하여 366가지 이기 때문이다.
- 앞이 보이지 않는 방에서 4쌍의 다른 양말이 널려 있을 때, 5개 이상의 양말을 고르면, 반드시 양말의 짝을 맞추어 신을 수 있다.
- 13명의 사람들 중 태어난 달이 같은 사람이 최소 2명이상 있다.
비둘기집의 원리의 일반화
편집일반화된 비둘기집 원리는 다음과 같다.
개의 별개의 사물을 개의 용기에 나누어 담으면 적어도 한 개의 용기는 이상의 사물을 담고 있어야 한다. (여기서, 는 보다 작지 않은 최소 정수를 의미한다.)
확률론적으로 일반화된 비둘기집 원리는 다음과 같다.
의 균일한 확률로 개의 비둘기를 무작위로 개의 비둘기집에 넣었다면 확률적으로 적어도 하나의 비둘기집에 두마리 이상의 비둘기가 들어가게 된다.
인 경우와, 인 경우(단, )에 확률은 0인데, 달리 말하면 비둘기가 한마리 밖에 없다고 하면, 충돌(한 비둘기집에 두 마리 이상의 비둘기가 들어가는 일)이 일어날 수 없다는 것이다. (비둘기가 비둘기집보다 많다)이라면 확률은 1이 되고 이런 경우에는 보통의 비둘기집 원리와 같은 일이 일어난다. 그러나 비둘기의 수가 비둘기집의 수를 초과하지 않는다 하더라도 ( ), 비둘기 분배의 무작위적인 성질에 의하여 종종 상당한 확률로 충돌이 일어난다. 예를 들어, 2마리의 비둘기가 무작위로 4개의 비둘기집에 분배된다면, 25%의 확률로 적어도 하나의 비둘기집에 두마리 이상의 비둘기가 들어가게 될 것이며, 5마리의 비둘기를 10개의 비둘기집에 분배한다면 확률은 69.76%가 되고, 10마리의 비둘기를 20개의 비둘기집에 분배하면 그 확률은 약 93.45%가 된다.
