비둘기집 원리

‘비둘기 $n+1$마리가 집 $n$개에 들어가면 어떤 집에는 두 마리 이상이 있다.’ 너무 당연해 보이지만, 무엇을 비둘기로, 무엇을 집으로 볼지 잘 정하면 놀라운 존재 증명을 할 수 있다.

핵심 정리

  • $n+1$개 이상의 물건을 $n$개의 상자에 넣으면 어떤 상자에는 $2$개 이상 들어 있다.
  • 일반형: $N$개를 $n$개의 상자에 넣으면 어떤 상자에는 $\left\lceil\frac Nn\right\rceil$개 이상 들어 있다.
상자 4개에 물건 5개를 넣은 그림
물건이 상자보다 많으면 어딘가에는 겹친다
증명 보기

모든 상자에 $\left\lceil\frac Nn\right\rceil-1$개 이하가 들어 있다고 가정하자. $\left\lceil\frac Nn\right\rceil-1<\frac Nn$이므로 전체 개수는 $n\left(\left\lceil\frac Nn\right\rceil-1\right)<n\cdot\frac Nn=N$이 되어 물건이 $N$개라는 데 모순이다. $N=n+1$이면 $\left\lceil\frac{n+1}{n}\right\rceil=2$이다. $\blacksquare$

예제

  • $13$명 중에는 태어난 달이 같은 사람이 반드시 있다. (상자: $12$개월)
  • $1$부터 $10$까지의 수 중 $6$개를 고르면 합이 $11$인 두 수가 반드시 있다. 상자를 $\{1,10\},\{2,9\},\{3,8\},\{4,7\},\{5,6\}$의 $5$개로 만들면 $6$개 중 두 개는 같은 상자에 들어간다.
  • 한 변이 $2$인 정사각형 안에 점 $5$개를 찍으면 거리가 $\sqrt2$ 이하인 두 점이 있다. 정사각형을 한 변이 $1$인 정사각형 $4$개로 나누면 두 점이 같은 작은 정사각형에 들어가고, 그 거리는 대각선 $\sqrt2$ 이하이다.

확인 문제

임의의 정수 $5$개 중에는 그중 $3$개의 합이 $3$의 배수가 되는 것이 반드시 있음을 보이시오.

풀이 보기

$3$으로 나눈 나머지 $0,1,2$를 상자로 보자. 세 상자에 모두 수가 있으면 나머지가 $0,1,2$인 수를 하나씩 골라 합이 $3$의 배수가 된다. 그렇지 않으면 $5$개가 두 상자에만 들어가므로 비둘기집 원리에 의해 어떤 상자에 $3$개 이상이 있고, 그 셋은 나머지가 같으므로 합이 $3$의 배수이다.

정리

  • 무엇을 비둘기(물건)로, 무엇을 집(상자)으로 볼지 정하는 것이 핵심이다.
알림: 보호된 콘텐츠입니다.