비둘기 집의 원리

비둘기 집의 원리 (Pigeonhole principle)는 만약 n개의 비둘기 집이 있고 n + 1개 이상의 비둘기가 있다면, 적어도 하나의 비둘기 집에는 두 마리 이상의 비둘기가 들어 있다는 기본적인 조합론적 원리이다. 때로는 서랍 원리 (drawer principle) 또는 디리클레 상자 원리 (Dirichlet's box principle)라고도 불린다.

이 원리는 겉보기에는 자명하지만, 의외로 다양한 문제를 해결하는 데 유용하게 사용될 수 있다. 예를 들어, "서울에 사는 사람 중 적어도 두 명은 머리카락 수가 같다"는 주장을 증명할 수 있다. 인간의 머리카락 수는 일반적으로 15만 개를 넘지 않으므로, 15만 개의 "비둘기 집"을 만들고 서울 시민 각각을 "비둘기"로 간주하면, 서울 시민 수가 15만 명을 넘는다는 사실로부터 위 주장이 참임을 알 수 있다.

수학적으로 엄밀하게 표현하면, 비둘기 집의 원리는 다음과 같이 표현할 수 있다. 만약 유한집합 X에서 유한집합 Y로 가는 함수 f가 존재하고, |X| > |Y| 이라면, f는 단사함수가 아니다. 즉, f(x₁) = f(x₂) 를 만족하는 서로 다른 x₁, x₂ ∈ X 가 존재한다.

일반화된 비둘기 집의 원리는 다음과 같다. n개의 비둘기 집이 있고 k n + 1개의 비둘기가 있다면, 적어도 하나의 비둘기 집에는 k + 1마리 이상의 비둘기가 들어 있다.