비둘기의 수가 비둘기집의 개수보다 많다면 (그리고 비둘기들이 모두 비둘기집으로 들어간다면) 반드시 어떤 비둘기집에는 두 마리 이상의 비둘기가 들어 있다. 좀 더 구체적으로 \(n+1\)마리 혹은 더 많은 비둘기를 \(n\)개의 비둘기집에 배정하면, 비둘기 중 적어도 두 마리는 같은 비둘기집에 배정된다. 더 일반적으로는, 비둘기의 수가 비둘기 집의 수의 \(k\)배 보다 더 많다면, 반드시 어떤 비둘기집에는 \(k+1\)마리 이상의 비둘기가 들어가 있다. 이러한 원리를 비둘기집의 원리라 부르는데 이를 처음봤을 때는 그닥 고급수학처럼 보이지는 않는다. 사실 비둘기집의 원리의 일반화 중 대부분은 기초적인 조합론을 공부하는 우리의 목표를 넘어서는 것들이다. 재미있으면서도 그다지 자명하지는 않아보이는 비둘기집과 관련된 예제를 살펴보자.
자명하지 않은 하나의 예로 어느 세 점도 일직선 상에 있지 않으며 한 평면 상에 있는 \(6\)개의 점을 생각하자. 이들 점으로 만든 각 쌍마다 빨간색 혹은 초록색인 선분으로 이어져 있을 때, 적어도 세 개의 점이 같은 색으로 서로 이어져 있어 하나의 삼각형을 이룸을 보여라. 다소 어려워 보이는 이 문제의 해법을 아래에서 읽기 전에 책을 잠시 내려 놓고 풀이를 직접 시도해보라. 점 \(A\)와 연결된 \(5\)개의 선분 중 적어도 \(3\)개는 비둘기집의 원리에 의해 같은 색인 선분이다. 이 같은 색으로 연결된 \(A\)가 아닌 세 점을 \(D, E, F\)라 부르자. 그리고 편의상 선분의 색은 빨간색이라 하자. 선분 \(\overline{DE}, \overline{EF}, \overline{FD}\) 중 하나가 빨간색이라면 원하는 결과를 얻는다. 그리고 이 세 선분 중 빨간색인 것이 없다면, 즉 이 세 선분이 모두 초록색이면 역시 원하는 결과를 얻는다.
Pigeonhole Problems.
- 동일한 흰색 양말 \(10\)개와 동일한 검은색 양말 \(10\)개가 양말함에 들어있다. 직접 보지 않고 양말을 꺼낼 때, 짝이 맞는 양말이 확실히 얻기 위해서는 몇 개의 양말을 꺼내야 하는가?
- 하나의 카드 덱에서 카드를 뽑을 때, 동일한 짝패 두 장 이상을 확실히 얻기 위해서는 몇 장의 카드를 뽑아야 하는가?
- 하나의 방에 들어간 사람 중에서 생일이 같은 사람이 반드시 적어도 세 명은 있기 위해서는 그 방에 몇 명이 들어가야 하는가?
- 빨간공 \(12\)개, 흰공 \(20\)개, 파란공 \(7\)개, 초록공 \(8\)개가 들어있는 상자에서 공을 뽑을 때, 같은 색의 공을 \(10\)개 이상 얻는다는 확신을 얻기 위해서는 몇 개의 공을 뽑아야 하는가?
- 커플 \(n\)쌍이 있고 그 중에서 사람을 뽑을 때, 적어도 한 커플은 포함되도록 뽑으려면 몇 명을 뽑아야 하는가?
- 사람 \(20\)명이 들어 있는 방이 있을 때, 이 방안에 서로 친구인 사람 수가 동일한 사람이 적어도 두 명이 존재함을 보여라.
- 평면 상의 격자점을 생각하자. 이 점들 중 임의의 \(5\)개의 점을 잡고, 이들을 연결하여 \(10\)개의 선분을 얻었을 때, 이 선분들 중 적어도 하나는 다른 격자점을 포함함을 보여라.
- 적어도 \(6\)명이 모인 파티에서는 서로가 모르는 세 명이 있거나, 서로가 아는 세 명이 있음을 보여라.