Pigeon Hole 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{ n }[/math]개의 실수 [math]\displaystyle{ x_1 , x_2 , ... , x_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]를 각각의 비둘기집에 있는 비둘기 마리수라고 하면 간단한 형태가 된다.
예시
실생활에 적용할 수 있는 상황이 많다.
- 리브레 위키에는 1631명 이상의 위키러가 있고 이 중 생일이 같은 5명을 찾을 수 있다. [math]\displaystyle{ \left\lfloor \tfrac{1631-1}{366} \right\rfloor + 1 = 5 }[/math][1]
- 대한민국 서울에 사는 사람들 중에 머리카락 수가 같은 두 명이 있다.
대머리 두 명 찾는게 그렇게 어렵나 - 반에서 학생들의 시험 점수가 같지 않으면 반 1등은 평균보다 잘 봤다.
애초에 평균은 안중에 없고 전교에서 노시는 분 - 6명의 사람이 있을 때, 서로 친구가 아니거나 서로 친구인 세 명이 있다. 램지의 정리라고 한다.
- 사람이 모여 있는 모임에서 친구 수가 같은 두명이 있다.[2]
- 무손실 압축 알고리즘이 모든 파일에 대해서 잘 되는 것은 아니다.
- 소녀시대 멤버 중 생일의 요일이 같은 서로 사람이 적어도 2명 존재한다.