비둘기 집의 원리
1. 개요
Pigeonhole Principle
비둘기집 원리는 간단하게 말해서 $$n+1$$개의 물건을 $$n$$개의 상자에 넣은 경우, 최소한 한 상자에는 그 물건이 반드시 두 개 이상 들어있다는 원리를 말한다. 보통 비둘기와 비둘기집의 형태로 비유되어 쓰이기 때문에, 비둘기 집의 원리라고 불린다.
2. 증명
귀류법을 이용해 증명이 가능하다.
$$n+1$$마리의 비둘기와 $$n$$개의 비둘기집이 있다고 가정할 때 모든 비둘기집에 비둘기가 빠짐없이 들어가야 하고, 한 집당 한 마리씩만 존재한다고 가정하면, 비둘기집에 최대 $$n$$마리의 비둘기만이 존재할 수 있게 되는데, 비둘기의 숫자는 $$n+1$$마리이기에 어느 집에도 들어가지 못한 비둘기 한 마리가 남을 수밖에 없게 되므로 전제조건들 사이에 모순이 발생하게 된다. 따라서 모든 비둘기집에 한마리의 비둘기만 들어가야 한다는 제한은 성립할 수 없으며, 이에 따라 어느 비둘기집에는 반드시 2마리 이상의 비둘기가 존재하게 된다. 비둘기 집의 원리에 대한 문제를 구할 때에 아니면 표현할 때에는 올림 기호를 사용한다.
사람으로 치면, 다섯 명이 4개 집에 나눠 들어가면 2인가구가 생긴다는 것. 사실 너무나 당연하고 직관적이어서 이게 증명씩이나 필요한지, '정리'라는 이름을 가지고 있어야 하는지 의문이 들 수도 있지만, 실제 생활에서 뿐만 아니라 많은 수학/과학 문제를 해결할 때 이 원리가 사용되며 이름이 없으면 불편해서 편의상 적당히 이름을 붙였다.
3. 확장
n+2 마리의 비둘기와 n개의 비둘기집이 있다고 가정하자. 비둘기집의 원리에 의해서 어느 하나의 비둘기집에는 2마리 이상 있는 것은 분명하다. 하지만, 2개 이상의 비둘기집에 비둘기가 2마리 이상 존재하는 것은 아니다. n-1개의 비둘기집에는 모두 한마리씩 있고, 1개의 비둘기집에는 3마리가 들어갈 수도 있다. 또 같은 이유로, 3마리가 들어간 비둘기집이 반드시 존재하는 것도 아니다. n-2개의 비둘기집에 1마리씩, 그리고 2마리씩 2군데 들어갈 수도 있다. 비둘기의 수가 증가한다고 해서, 그에 맞게 간단히 확장되는 것은 아니다.
다만, 비둘기가 2n+1 마리로 증가한다면, 이때는 3마리 이상 들어간 비둘기집이 최소 1군데 있다는 것이 보장된다. 일반화 하면 '''비둘기가 kn+1 마리이고 비둘기집이 n개이면, 최소한 하나의 비둘기집에는 k+1 마리 이상의 비둘기가 들어간다.''' (k는 자연수)
4. 예시
가장 간단한 예를 들자면 공이 3개가 있는데, 공을 적당히 나누어 2개의 상자에 나누어 넣어야 한다. 그렇다면, 어떤 방법으로 나누어 넣더라도 공을 쪼개버리지 않는 이상은 반드시 둘 중 하나의 상자에는 공이 2개 이상 들어 있게 된다.
- 어떤 집단에 367명(윤년의 2월 29일도 고려해야 하기 때문)이 있으면 생일이 같은 사람이 반드시 1쌍 이상 존재한다.
- 위는 100%확률의 조건이고, 구체적인 확률로 따지면 훨씬 더 적은 수로도 가능할 것이다. 계산을 단순화하기 위해 윤년은 고려하지 않는다고 치면 사람이 n명 있을 때 생일이 같은 사람이 한 쌍이라도 있을 확률은, 1에서 그 사람들이 모두 생일이 다를 확률을 빼면 된다. 생일이 모두 다를 확률은 1*(364/365)*(363/365)...*(365-n+1/365)이다. 계산해보면 알겠지만 23명만 넘어가도 그 확률은 50%를 넘기 시작하고, 30명은 약 70%, 50명은 약 97%, 70명 쯤에서 이미 99.9%쯤 된다.
- 로또의 경우는 365 대신 8,145,060을 넣고 구하면 되는데, 이 경우 0.1% 정도인 8,661 게임에서 이미 99%가 되어버리며, 0.5%인 40,725 게임만 되어도 44나인(소수점 뒤에 9가 44개)이 되어 버린다. 즉, 로또 독식은 꿈도 꾸지 말라는 얘기.
- 이를 일반화 시켜서 가능한 경우의 수가 n이고 시행 횟수가 k일 때, 비둘기 집의 원리에 걸릴 확률은 $$1 - ({_{n}\textrm{P}_{k}}/{{n}^{k}})$$이다. n이 충분히 커진다고 수용 가능한 k가 정비례해서 커지지는 않는지라, 생일 문제라고 따로 이름이 붙었다.
5. 실제로 비둘기에 적용한다면?
조류는 알을 하나의 둥지에만 낳기 때문에 자연적으로는 비둘기 두 마리가 한 둥지를 쓸 일은 없다. 물론 뻐꾸기는 예외적인 경우이므로 제외.
여기서 말하는 '비둘기집'은 닭장처럼 큰 우리를 하나 혹은 여러개 쌓아올려 만든 새장에 가깝다. 구글에 pigeon cage를 검색하면 나온다. 각 층마다 비둘기를 한 쌍 정도 키우는데 따라서 입구가 층마다 있어 입구의 개수가 여러개다. 따라서 출입구의 개수는 비둘기의 수보다 적거나 같은 것. 층이 나누어지지 않은 큰 새장에서도 출입구를 여러 개 두는 경우도 있다. 큰 새장에서 비둘기들은 각 쌍별로 둥지를 따로 쓴다.