- 상위 항목 : 수학 관련 정보
1 개요
비둘기집 원리는 간단하게 말해서 [math]n+1[/math]개의 물건을 [math]n[/math]개의 상자에 넣은 경우, 최소한 한 상자에는 그 물건이 반드시 두 개 이상 들어있다는 원리를 말한다. 보통 비둘기와 비둘기집의 형태로 비유되어 쓰이기 때문에, 비둘기집의 원리라고 불린다.
2 증명
귀류법을 이용해 증명이 가능하다. [math]n+1[/math]마리의 비둘기와 [math]n[/math]개의 비둘기집이 있다고 가정할때, 모든 비둘기집엔 한 마리의 비둘기만 들어간다고 하자. 이 때 모든 비둘기집에 총 [math]n[/math]마리의 비둘기만 들어간다고 하면 모순이 발생하는데 모든 비둘기집에 비둘기가 한 집당 한 마리씩만 들어가게 제한하면 어느 집에도 들어가지 못한 비둘기 한 마리가 남을 수밖에 없으므로 어느 비둘기집에는 반드시 [math]2[/math]마리 이상의 비둘기가 존재한다.
사실 너무나 당연하고 직관적이어서 이게 증명씩이나 필요한지, '정리'라는 이름을 가지고 있어야 하는지 의문이 들 수도 있지만, 실제 생활에서 뿐만 아니라 많은 수학/과학 문제를 해결할 때 이 원리가 사용되며 이름이 없으면 불편해서 편의상 적당히 이름을 붙인 것이다.
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는 0 이상의 정수)
4 예시
가장 간단한 예를 들자면 공이 3개가 있는데, 공을 적당히 나누어 2개의 상자에 나누어 넣어야 한다. 그렇다면, 어떤 방법으로 나누어 넣더라도 반드시 둘중 하나의 상자에는 공이 2개 이상 들어 있게 된다.
만약에 당신이 101마리의 낙타를 갖고 있고 이를 5명에게 나누어 주어야 한다고 가정을 해 보자. (단, 낙타를 죽여서 나눠 가진다거나 팔아서 돈을 나눠가지는 경우는 없다고 가정한다.) 101마리를 5명에게 똑같이 나눈다면 모두 20마리씩 받고 1마리가 남게 된다. 어떻게 나누든 당신은 최소한 어느 한 사람에게는 21마리 이상의 낙타를 줄 수밖에 없게 된다.17마리를 3사람에게 나누어주려면 9마리 6마리 2마리 나누어주어야 하는 암묵의 룰이 있다
다른 예로, 바둑돌 50개를 7명에게 나누어 주는 상황을 가정해 보자. 50개를 한 개도 빠짐없이 7명에게 나누어 주어야 한다면, 7명에게 7개씩 균등하게 나누어 주면 1개가 남고 이 1개 남은 것까지 주어야 하므로 어떻게 나누든 최소한 어느 한 명은 8개 이상 갖게 된다.
5 사례
- 13명의 사람 중에 같은 달에 태어난 사람이 1쌍 이상 존재한다.
- 서울에서 머리카락의 수가 같은 사람이 최소 2명이 존재한다.
- 해시 테이블에서 어떤 해시 함수라도 충돌은 불가피하다.
- 어떤 집단에 367명(2월 29일도 고려해야 하기 때문)이 있으면 생일이 같은 사람이 1쌍 이상 존재한다.
6 실제로 비둘기에 적용한다면?
어쩌다 이런 문단이 생긴거지.
조류는 알을 하나의 둥지에만 낳기 때문에 비둘기 두마리가 한 집을 쓸 일은 없다. 물론 뻐꾸기는 예외적인 경우이므로 제외.
굳이 해보려 하는 사람들은 비둘기가 득실한 에어컨 실외기 뒤 쪽에 칸막이를 설치 해보자. 두마리 비둘기가 난 둥지와 알을 칸막이 쪽으로 가까이 옮기고 칸막이를 제거하면 비둘기집 원리를 증명할 수 있다. 요점은 그게 아니잖아
억지로 두마리 비둘기를 한 우리에 넣어놓고 문을 걸어 잠군다면 평화의 상징(...)이 한 쪽이 죽을 때까지 맞짱까는 걸 볼 수 있다. 이렇게 해서 다른 어미가 죽어 알이 4개가 되면 자기 알인지 아닌지에 관계없이 먼저 알을 깨고 나온 두마리의 새끼만 보살피고 나머지 두 개의 알은 포란하지 않아 죽어버린다.