Pigeonhole Principle

비둘기집 원리

• 기본 정의

  $n+1$마리의 비둘기를 $n$개의 비둘기집에 넣으면, 적어도 하나의 비둘기집에는 2마리 이상의 비둘기가 들어가야 한다.

• 수학적인 정의

  $k$개의 상자에 $n$개의 항목을 넣을 때, $n > k$라면 어떤 상자에는 최소한 2개 이상의 항목이 들어가야 한다.

일반형

$k$개의 상자에 $n$개의 항목을 넣는다면, 어떤 상자에는 최소 $\left\lceil \frac{n}{k} \right\rceil$개의 항목이 들어가야 한다.
만약 $15$개의 사과를 $4$개의 바구니에 넣으려면, 어떤 바구니에는 최소 $\left\lceil \frac{15}{4} \right\rceil = 4$개의 사과가 들어가야 한다.

응용 예제

1. 생일 문제

같은 반에 $30$명이 있다면, 생일이 같은 사람이 반드시 존재할까?
만약 반의 인원이 $370$명이라면, 그 때에는 생일이 같은 사람이 반드시 존재할까?

1년은 총 365일로 이루어져있다고 생각하면, 반 인원이 30명일 때에는 $30 \leq 365$이므로, 반드시 생일이 같은 사람이 존재한다고 보기 어렵다.

하지만 반 인원이 370명이 된다면, $370 \geq 365$이므로, 이 때에는 생일이 같은 사람이 반드시 존재한다고 얘기할 수 있다.

2. 정수 차이

$10$개의 서로 다른 정수가 있을 때, 어떤 두 수의 차가 $9$의 배수가 되는 쌍이 반드시 존재하는가?

수들을 $9$로 나눈 나머지를 고려한다고 할 때, 가능한 나머지의 경우의 수는 $\vert \lbrace 0 \cdots 8 \rbrace \vert = 9$이다.

수가 총 10개 있으므로, 어떤 쌍은 반드시 자신들을 $9$로 나눈 나머지가 같을 수밖에 없다!

활용 방안

어떤 상황에 대해서 이를 만족하는 해가 반드시 존재한다를 증명할 수 있는 강력한 원리로 주로 쓰인다.