비둘기집 원리
위키백과 ― 우리 모두의 백과사전.
비둘기집 원리는 n마리의 비둘기가 m개의 비둘기집에 들어가 있고 n > m이면, 두 마리 이상의 비둘기가 들어가는 비둘기집이 적어도 하나는 존재한다는 원리를 말한다. 다시 말하자면, m개의 비둘기집에 하나에 한마리씩 비둘기를 넣으면, 최대 m마리가 들어갈 수 있으므로 거기에 한 마리를 더 넣으려면 이미 넣은 곳에 하나 더 넣어야 한다는 말이다. 디리클레의 상자 원리라고도 알려져 있다.
비둘기집의 원리는 개수 세기 문제의 유명한 예 중 하나로, 일대일 대응을 만들 수 없는 무한집합이 들어간 예제를 포함해 `여러가지 문제에 대해 적용할 수 있다. 디오판투스 근사에서 '지겔의 보조정리'는 선형 시스템에서의 정수해의 존재성 증명에 이 원리를 적용한 것이다.
이 원리는 1834년 Schubfachprinzip ("서랍 원리")라는 이름으로 디리클레에 의해 처음 언급된 것으로 알려져 있다. 이 때문에 러시아어 등의 몇몇 언어에서는 이 원리를 디리클레 원리라고 부른다. (조화 함수의 최소 원리를 가리키는 같은 이름의 원리와 혼동하지 말 것)
목차 |
[편집] 예제
일견 자명해 보이는 비둘기집 원리는 때로 놀라운 결과를 보여주기도 한다. 예를 들면, 서울에는 머리카락의 수가 같은 사람이 최소한 두 명 존재한다.. 왜냐하면 일반적인 사람의 머리카락 수는 15만개이다. 그러므로 100만개 이상의 머리카락을 가진 사람은 없다고 가정해도 무리가 없다. 서울에는 1000만 명 가량의 사람이 있으므로, 서로 다른 머리카락의 개수를 서로 다른 비둘기집으로 보고, 서울에 사는 사람 각각을 머리카락의 개수에 따라 서로 다른 비둘기집에 할당하면, 같은 머리카락 개수를 가진 사람이 반드시 존재한다는 것을 알 수 있다.
또다른 좀더 일상적인 예제로는, 소프트볼을 하고 싶어하는 사람 중에, 서로 같이 경기하고 싶어하지 않는 사람이 5명이지만, 팀이 4개 뿐인 경우를 생각해볼 수 있다. 만약 이 사람들이 서로 다른 팀에 들어가고 싶어할 경우, 비둘기집의 원리에 의해 5명의 사람을 한 팀에 한명씩 4개 의 팀으로 나누는 것은 불가능하다는 것을 알 수 있다.
컴퓨터과학에서도 비둘기집 원리의 예를 종종 찾아볼 수 있다. 예를 들어, 해쉬 테이블에서 가능한 모든 키의 숫자는 테이블 인덱스의 개수보다 많으므로 충돌은 불가피하다. 따라서 어떤 해쉬 알고리즘도 충돌을 피할 수는 없다. 또한, 모든 파일을 임의의 크기 S 이하로 압축하는 비손실 압축 알고리즘은 존재하지 않는다. S 이하의 크기를 갖는 파일의 개수는 정해져 있으므로, 그런 알고리즘이 존재한다면 동일한 파일로 압축되는 두 개의 서로 다른 파일이 반드시 존재할 것이므로 두 파일을 다시 원래대로 복원하는 것이 불가능할 것이다.
그리말디[1]의 몇가지 예가 더 있다.
[편집] 비둘기집 원리의 일반화
일반화 된 비둘기집 원리는 "n개의 별개의 사물을 m개의 용기에 나누어 담으면 적어도 한 개의 용기는 이상의 사물을 담고 있어야 한다.(여기서,
는 올림 함수를 의미한다.)"고 기술한다.
확률론적으로 일반화 된 비둘기집 원리는 "1/m의 균일한 확률로 n개의 비둘기를 무작위로 m개의 비둘기집에 넣었다면 확률적으로 적어도 하나의 비둘기집에 두마리 이상의 비둘기가 들어가게 된다."고 기술한다.
n = 0 인 경우와, n = 1인 경우(단, m > 0)에 확률은 0인데, 달리 말하면 비둘기가 한마리 밖에 없다고 하면, 충돌(한 비둘기집에 두 마리 이상의 비둘기가 들어가는 일)이 일어날 수 없다는 것이다. n > m (비둘기가 비둘기집보다 많다)이라면 확률은 1이 되고 이런 경우에는 보통의 비둘기집 원리와 같은 일이 일어난다. 그러나 비둘기의 수가 비둘기집의 수를 초과하지 않는다 하더라도 (n ≤ m), 비둘기 분배의 무작위적인 성질에 의하여 종종 상당한 확률로 충돌이 일어난다. 예를 들어, 2마리의 비둘기가 무작위로 4개의 비둘기집에 분배된다면, 25%의 확률로 적어도 하나의 비둘기집에 두마리 이상의 비둘기가 들어가게 될 것이며, 5마리의 비둘기를 10개의 비둘기집에 분배한다면 확률은 69.76%가 되고, 10마리의 비둘기를 20개의 비둘기집에 분배하면 그 확률은 약 93.45%가 된다.
[편집] 참고자료
- ↑ ((영어)) Grimaldi, Ralph P. Discrete and Combinatorial Mathematics: An Applied Introduction. 4th edn. 1998. ISBN 0-201-19912-2. pp. 244–248.
[편집] 읽을거리
- 기수
- 램지의 정리
- 생일 역설
[편집] 바깥 고리
- ((영어)) cut-the-knot 사이트에 게재된 비둘기집 원리
- ((영어)) "The strange case of The Pigeon-hole Principle"; 에츠허르 데이크스트라가 이 원리의 해석과 변형을 연구함.