비둘기 집의 원리

최근 수정 시각:

분류


1. 개요2. 증명3. 확장4. 예시5. 실제로 비둘기에 적용한다면?

1. 개요[편집]

비둘기집 원리는 간단하게 말해서 n+1n+1개의 물건을 nn개의 상자에 넣은 경우, 최소한 한 상자에는 그 물건이 반드시 두 개 이상 들어있다는 원리를 말한다. 보통 비둘기와 비둘기집의 형태로 비유되어 쓰이기 때문에, 비둘기 집의 원리라고 불린다.

2. 증명[편집]

귀류법을 이용해 증명이 가능하다. n+1n+1마리의 비둘기와 nn개의 비둘기집이 있다고 가정할때, 모든 비둘기집엔 한 마리의 비둘기만 들어간다고 하자. 이 때 모든 비둘기집에 총 nn마리의 비둘기만 들어간다고 하면 모순이 발생하는데 모든 비둘기집에 비둘기가 한 집당 한 마리씩만 들어가게 제한하면 어느 집에도 들어가지 못한 비둘기 한 마리가 남을 수밖에 없으므로 어느 비둘기집에는 반드시 22마리 이상의 비둘기가 존재한다.

사실 너무나 당연하고 직관적이어서 이게 증명씩이나 필요한지, '정리'라는 이름을 가지고 있어야 하는지 의문이 들 수도 있지만, 실제 생활에서 뿐만 아니라 많은 수학/과학 문제를 해결할 때 이 원리가 사용되며 이름이 없으면 불편해서 편의상 적당히 이름을 붙인 것이다.

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개 이상 들어 있게 된다.

  • 해시 테이블에서 어떤 해시 함수라도 충돌은 불가피하다.

  • 어떤 집단에 367명(윤년의 2월 29일도 고려해야 하기 때문)이 있으면 생일이 같은 사람이 반드시 1쌍 이상 존재한다.[1]

5. 실제로 비둘기에 적용한다면?[편집]

어쩌다 이런 문단이 생긴거지

조류는 알을 하나의 둥지에만 낳기 때문에 자연적으로는 비둘기 두 마리가 한 집을 쓸 일은 없다. 물론 뻐꾸기는 예외적인 경우이므로 제외.

억지로 두 마리 비둘기를 한 우리에 넣어놓고 문을 걸어 잠근다면 평화의 상징(...)의 한 쪽이 죽을 때까지 맞짱까는 걸 볼 수 있다. 이렇게 해서 다른 어미가 죽어 알이 4개가 되면 자기 알인지 아닌지에 관계없이 먼저 알을 깨고 나온 두마리의 새끼만 보살피고 나머지 두 개의 알은 포란하지 않아 죽어버린다.

[1] 확률로 따지면 훨씬 더 적은 수로도 가능할 것이다. 계산을 단순화하기 위해 윤년은 고려하지 않는다 치면 사람이 n명 있을 때 생일이 같은 사람이 한 쌍이라도 있을 확률은, 1에서 그 사람들이 모두 생일이 다를 확률을 빼면 된다. 생일이 모두 다를 확률은 1*(364/365)*(363/365)...*(365-n+1/365)이다. 계산해보면 알겠지만 당장 23명만 넘어가도 그 확률은 50%를 넘기 시작하고, 70명 쯤에서 이미 99.9%쯤 된다.