비둘기집 원리

위키백과 ― 우리 모두의 백과사전.

이 원리에 영감을 준 비둘기집에 있는 비둘기들. 여기서 n = 7 이고 m = 9이다.
실제 크기로
이 원리에 영감을 준 비둘기집에 있는 비둘기들. 여기서 n = 7 이고 m = 9이다.

비둘기집 원리n마리의 비둘기가 m개의 비둘기집에 들어가 있고 n > m이면, 두 마리 이상의 비둘기가 들어가는 비둘기집이 적어도 하나는 존재한다는 원리를 말한다. 다시 말하자면, m개의 비둘기집에 하나에 한마리씩 비둘기를 넣으면, 최대 m마리가 들어갈 수 있으므로 거기에 한 마리를 더 넣으려면 이미 넣은 곳에 하나 더 넣어야 한다는 말이다. 디리클레의 상자 원리라고도 알려져 있다.

비둘기집의 원리는 개수 세기 문제의 유명한 예 중 하나로, 일대일 대응을 만들 수 없는 무한집합이 들어간 예제를 포함해 `여러가지 문제에 대해 적용할 수 있다. 디오판투스 근사에서 '지겔의 보조정리'는 선형 시스템에서의 정수해의 존재성 증명에 이 원리를 적용한 것이다.

이 원리는 1834년 Schubfachprinzip ("서랍 원리")라는 이름으로 디리클레에 의해 처음 언급된 것으로 알려져 있다. 이 때문에 러시아어 등의 몇몇 언어에서는 이 원리를 디리클레 원리라고 부른다. (조화 함수의 최소 원리를 가리키는 같은 이름의 원리와 혼동하지 말 것)

목차

[편집] 예제

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

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

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

그리말디[1]의 몇가지 예가 더 있다.

[편집] 비둘기집 원리의 일반화

일반화 된 비둘기집 원리는 "n개의 별개의 사물을 m개의 용기에 나누어 담으면 적어도 한 개의 용기는 \lceil n/m \rceil 이상의 사물을 담고 있어야 한다.(여기서, \lceil\dots\rceil는 올림 함수를 의미한다.)"고 기술한다.

확률론적으로 일반화 된 비둘기집 원리는 "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이 되고 이런 경우에는 보통의 비둘기집 원리와 같은 일이 일어난다. 그러나 비둘기의 수가 비둘기집의 수를 초과하지 않는다 하더라도 (nm), 비둘기 분배의 무작위적인 성질에 의하여 종종 상당한 확률로 충돌이 일어난다. 예를 들어, 2마리의 비둘기가 무작위로 4개의 비둘기집에 분배된다면, 25%의 확률로 적어도 하나의 비둘기집에 두마리 이상의 비둘기가 들어가게 될 것이며, 5마리의 비둘기를 10개의 비둘기집에 분배한다면 확률은 69.76%가 되고, 10마리의 비둘기를 20개의 비둘기집에 분배하면 그 확률은 약 93.45%가 된다.

[편집] 참고자료

  1. ((영어)) Grimaldi, Ralph P. Discrete and Combinatorial Mathematics: An Applied Introduction. 4th edn. 1998. ISBN 0-201-19912-2. pp. 244–248.

[편집] 읽을거리

[편집] 바깥 고리