비둘기집 원리(Pigeonhole Principle)

 비둘기집 원리는 다음과 같다.

비둘기집 원리.

 n 개의 물건을 r개의 상자에 넣을 때, r<n이라면, 적어도 어떤 한 상자는 두 개 이상의 물건을 포함하게 된다.

^[각주:1]

 증명할 필요도 없이 너무나 당연해보인다. 최대한 고루 상자에 분배한다해도 일대일로 상자가 차고나면 물건이 남기 때문이다. 그러나, 항상 모든 상자가 차있을거라고는 말할 수 없다는 것을 확인하자.(최악의 경우 한 상자에 모든 물건들이 차 있을 수도 있다.)

 예를 들면 훨씬 이해하기 쉽다. 사람의 혈액형은 A, B, O, 그리고 AB형으로 총 4종류가 있다. 사람들이 5명 이상 있다면 그들의 혈액형이 모두 다를 수 없고, 그래서 혈액형이 같은 사람들이 최소한 두명 있을것이라고 단정지을 수 있다.

 여기 비둘기집의 원리가 쓰이는 유명한 문제 2개를 소개한다.

1) 뉴욕시의 모든 주민들은 그의 머리카락 수가 뉴욕시 전체 주민수보다 적다고 한다. 뉴욕시 주민들 중 대머리가 없다고 가정할 때, 머리카락 수가 같은 주민이 적어도 두 사람 있음을 보여라.

 설명 : 뉴욕시 전체 주민수를 N이라고 하자. 머리카락 수는 뉴욕시 전체 주민수보다 작으므로 1, 2, ... N-1개가 가능한데, N-1<N이므로 비둘기집의 원리에 의해 머리카락 수가 같은 뉴욕시 주민이 적어도 두 사람 존재한다.

2) 철수는 검은 양말 10켤레와 흰 양말 10켤레를 가지고 있다. 철수가 양말을 신으려고 서랍을 연 순간 전구가 나가 양말의 색을 구분할 수 없게 되었다. 최소한 몇 개의 양말을 꺼내야 짝이 맞는 양말이 한 켤레 있다고 생각할 수 있을까?

 풀이 : 혹시 21개라고 생각하지는 않았는지..? 3개만 꺼내면 충분하다. 색깔의 종류는 흑과 백 2가지밖에 없으므로 비둘기집의 원리에 의해 3개의 양말 안에는 색이 똑같은 2개의 양말이 존재한다.

 비둘기집의 원리는 매우 간단한 논리이지만, 여러 퍼즐 등에서 생각지도 못한 높은 활용도를 자랑한다. 그런 문제들의 특징은 비둘기집이 쓰인다는 힌트 없이는 풀이를 생각해내기가 꽤 어렵다는 것이다. 그러나, 그렇게 어려운 만큼 문제를 풀었을 때의 만족감 역시 높다고 말할 수 있다. 조합론은 물론 기하학 퍼즐과 정수론 퍼즐 등 앞으로 몇몇 문제들에 그 활용을 보여줄 것이다.

마지막으로 일반화된 비둘기집 원리를 설명한다.

일반화된 비둘기집 원리.

N 개의 물건을 r개의 상자에 넣을 때, 적어도 어떤 한 상자는 ⌈N/r⌉개 이상의 물건을 포함하게 된다.(⌈x⌉는 천장함수(x보다 크거나 같은 정수들 중 최소 정수)이다.)

^[각주:2]

 증명은 귀류법을 이용한다. 만약 모든 상자가 ⌈N/r⌉-1개의 물건을 포함한다면, 물건 총합은,

r*(⌈N/r⌉-1)<r*(N/r)=N

라는 부등식을 만족한다. 이는 모순이므로 적어도 어떤 한 상자는 ⌈N/r⌉개의 물건을 포함해야한다.

2020.10.31. 천장함수 설명 수정

1. 하늘책의 증명 p197 (Aigner, Ziegler 지음, 이상욱 고영미 강미형 옮김, 교우사) [본문으로]
2. Discrete Mathematics And Its Applications p.349 (Kenneth H. Rosen 지음, McGRAW-HILL) [본문으로]