비둘기집의 원리

Pigeonhole Principle.

개요

“비둘기집 [math]\displaystyle{ n }[/math] 채에 비둘기 [math]\displaystyle{ n+1 }[/math] 마리를 나눠 넣으면, 비둘기가 두 마리 이상 들어 있는 집이 적어도 하나는 꼭 존재한다.”라는 원리이다. 서랍 원리라고도 한다.

좀 더 일반적으로는 아래와 같다.

비둘기 집 “[math]\displaystyle{ n }[/math] 채에 비둘기 [math]\displaystyle{ m }[/math]마리를 나눠 넣으면, 비둘기가 [math]\displaystyle{ \left\lfloor \tfrac{m-1}{n} \right\rfloor + 1 }[/math] 마리 이상 들어 있는 집이 적어도 하나는 꼭 존재한다.” 참고로, [math]\displaystyle{ m }[/math]이 [math]\displaystyle{ n }[/math]의 배수라면 [math]\displaystyle{ \tfrac{m}{n} }[/math] 마리 이상이라는 뜻이다.

꼭 기억해야 할 점은, [math]\displaystyle{ \left\lfloor \tfrac{m-1}{n} \right\rfloor + 1 }[/math] 마리가 정확히 들어 있는 집이 존재한다고 보장할 순 없고, 둘 이상 있는지도 보장할 수 없다는 것이다. 보장할 수 있는 것은 오직 [math]\displaystyle{ \left\lfloor \tfrac{m-1}{n} \right\rfloor + 1 }[/math] 마리 이상 들어 있는 집이 적어도 하나 있다는 것뿐이다.

증명

귀류법을 이용한다.

모든 집에 비둘기가 [math]\displaystyle{ \left\lfloor \tfrac{m-1}{n} \right\rfloor }[/math] 마리 이하로 들어 있다고 하면, 총 비둘기 수는 [math]\displaystyle{ n \cdot \left\lfloor \tfrac{m-1}{n} \right\rfloor \lt n \cdot \tfrac{m-1}{n} = m-1 \lt m }[/math]이 되어 모순이다.

변형

굉장히 간단한 원리인 만큼 변형 또한 다양하다. 증명도 비슷하게 하면 된다. 쉬운 것부터 하나하나 보자.

• 비둘기집이 [math]\displaystyle{ n }[/math]채 있고 비둘기가 [math]\displaystyle{ n-1 }[/math]마리 있을 때, 빈 집이 꼭 존재한다.빈집털이
• 비둘기집이 [math]\displaystyle{ n }[/math]채가 있는데 [math]\displaystyle{ i }[/math]번째 비둘기집마다 각각 자연수 [math]\displaystyle{ a_i }[/math]가 적혀 있다고 하자. 만약 비둘기가 [math]\displaystyle{ \sum a_i -n+1 }[/math]마리 있으면 적혀 있는 수보다 비둘기 수가 더 많은 집이 있다.
  • 가장 간단한 형태는 [math]\displaystyle{ a_1 = a_2 = ... = a_n = 2 }[/math]이다.
• 실수 [math]\displaystyle{ x_1 , x_2 , ... , x_n }[/math]가 [math]\displaystyle{ n }[/math]개 있을 때, 평균 이상인 수 [math]\displaystyle{ x_i }[/math]가 존재한다.
  • 만약 [math]\displaystyle{ \sum_{i=1}^{n} x_i = n+1 }[/math]이고 수들을 0을 포함한 자연수로 제한하면 간단한 형태가 된다.
• 확률변수 [math]\displaystyle{ X }[/math]가 있을 때, [math]\displaystyle{ X }[/math]가 [math]\displaystyle{ E(X) }[/math]이상일 확률이 0보다 크다. 비슷하게 [math]\displaystyle{ E(X) }[/math]이하일 확률도 0보다 크다.
  • 비둘기 [math]\displaystyle{ n+1 }[/math]마리를 비둘기집 [math]\displaystyle{ n }[/math]채에 넣어두고 확률변수 [math]\displaystyle{ X }[/math]를 각 비둘기집에 들어 있는 비둘기 수라고 하면 간단한 형태가 된다.

예시

실생활에 적용할 수 있는 상황이 많다.

• 리브레 위키에는 위키러가 8,597명 있고, 이 중에서 생일이 같은 사람이 24명 이상 있다. [math]\displaystyle{ \left \lfloor \tfrac{ 8,597-1 }{366} \right \rfloor + 1 = 24 }[/math]
• 대한민국 서울에 사는 사람들 중 머리카락 수가 같은 사람이 2명 이상 있다. 대머리 두 명 찾는 게 그렇게 어렵나
• 한 반에 있는 학생들의 시험 점수가 서로 같지 않으면 반 1등은 평균보다 잘 봤다. 애초에 평균은 안중에 없고 전교에서 노시는 분
• 6명이 있을 때, 서로 친구가 아니거나 서로 친구인 세 명이 있다. 램지의 정리라고 한다.
• 어떤 모임이든 친구 수가 같은 두명이 있다.
• 무손실 압축 알고리즘이 모든 파일에 대해서 잘 되는 것은 아니다.
• 소녀시대 멤버 중 생일 요일이 서로 같은 사람이 적어도 2명 존재한다.
• 8강에 5명의 테란이 올라갔을 때 적어도 하나 이상의 세상에서 재일 재밌는 테테전이 있다