6.1 비둘기집 원리

제6장에서는 특정 종류의 수량이나 패턴, 혹은 배치와 관련된 문제를 다루기 위한 조합론의 근본적인 원리를 살펴보려 한다. 

 

만일 비둘기가 $n$마리 있고 비둘기집이 $(n-1)$개가 있다면, 비둘기들이 비둘기 집을 찾아 들어가는 모든 가능한 경우를 고려할 때, 우리는 확신에 가득차며, 명백한 하나의 사실을 발견하게 된다. 

 

"적어도 어느 한 비둘기 집에는 2마리 이상의 비둘기가 있다." 

 

비둘기가 $n$이상으로 충분히 많다면 이런 일은 반드시 발생한다. 그러므로 우리가 궁금한 것은 이런 일이 일어나는 '최소수의 존재'이다. 

 

비둘기집 원리는 어느 비둘기집에 두 마리 이상의 비둘기가 있는지에 대해서는 알려지지 않는다. 단지 그런 수량을 갖는 비둘기 집의 존재성을 보장한 뿐이다. 즉, 특정한 수량의 존재성과 관련한 문제를 다룰 때 유용하다. 

 

이 간단한 관찰을 일반화시킨 명제는 다음과같다. 

---

비둘기집 원리
"어떤 두 자연수 $k$와 $n$에 대해 만약 $kn+1$개 이상의 대상을 $n$개의 상자에 담을때, 상자 중 어느 하나는 적어도 $(k+1)$개의 대상들을 포함한다."

 

비둘기집의 원리의 증명은 결론을 부정하면 쉽게 해결된다. 만약 $(k+1)$개 이상의 대상을 담고 있는 상자가 없다면 모든 상자는 기껏해야 $k$개의 대상들을 포함한다. 즉, $n$개의 상자에 들어간 대상들의  총 개수는 기껏해야 $kn$개이므로 이는 가정에 모순된다. 

---

비둘기집 원리는 다음과 같은 명제로 표현하는 것이 더 일반적이다.

 

"임의의 자연수 $q_i, i = 1, 2,\cdots, n$에 대하여 
   $q_1+q_2+\cdots+q_n -n+1$
개의 대상을 $n$개의 상자에 넣을 때, 첫번째 상자에 적어도 $q_1$개 이상이 들어 있거나 , 또는 두번째 상자에 적어도 q_2개  이상이 들어 있거나, \cdots, 또는 $n$번째 상자에 적어도 q_n개 이상의 대상이 들어있다." 

 

간단히 말하면,

   $q_1+q_2+\cdots+q_n -n+1$

개 이상의 대상을 $n$개의 상자에 담는다면 적어도 $q_i$개의 대상이 들어 있는 $i$번째 상자가 존재한다는 것을 말한다. 

이것에 대한 이해를 도울 문제가 하나 있다. 

사과, 배, 귤이 들어 있는 과일 바구니를 만드는데, 적어도 8개의 사과, 또는 적어도 6개의 배, 또는 적어도 9개의 귤이 들어 있기 위한 최소의 과일 수는 몇 개일까? 

충분한 사과,배,귤 상자에서
   $(8-1)+(6-1)+(9-1)=20$
개의 과일을 과일 바구니에 담으면 조건이 성립하지 않는 하나의 예가 존재한다. 사과 7개, 배 5개, 귤 8개가 바로 그 경우에 해당한다. 여기에 과일 하나만 더 추가하면 조건이 성립된다. 추가한 과일의 종류는 사과, 배, 귤 중 어느 것이라도 상관없다. 따라서 구하는 최소의 과일 수는
   $8+6+9-3+1=21$
이다.  즉, 사과,배,귤 상자에서 $21$개의 과일을 무작위로 과일 바구니에 담으면 적어도 $8$개의 사과, 또는 적어도 $6$개의 배, 또는 적어도 $9$개의 귤이 들어 있게 된다. 

---

비둘기집 원리를 적용할때 우리는 무엇이 '비둘기' 이고 무엇이 '비둘기집'인지 또는 무엇이 '대상'이고 무엇이 '상자'인지 구별할 수 있어야 한다. 

다음 몇 가지 예제를 풀어본다. 

[예제 1]

어느 여행작가는 30동안 45개 도시를 방문하면서 글을 쓴다고 한다. 매일 적어도 한 도시 이상을 방문할 때 그가 정확히 14개 도시를 방문한 어떤기간이 존재함을 증명하여라. 

왜 14개의 도시일까? 

15개이상의 도시이면 안되는걸까? 결론부터 얘기하면 14개 도시가 마지노선이다. 

우선, 처음부터 $k$일 동안 방문한 도시의 개수를 $n_k$라 하자. 그러면
   $1≤ n_1 < n_2 < \cdots < n_k ≤ 45$
를 만족한다. 이때, 우리는 적당한 자연수 $i, j$가 존재하여
   $n_j = n_i + 14 \ (1\leq i<j\leq 30)$
임을 보이면 충분하다. 그러면  $i$일부터 $j$일의 기간이 정확히 $14$개의 도시를 방문한 기간이다. 

이때
   $15 \leq n_1 +14  < n_2 +14  < \cdots < n_{30} +14 ≤ 59$
이므로 '비둘기(또는 대상)'는 60개의
   $n_1, n_2, \cdots, n_{30}, n_1 +14, n_2 +14, \cdots, n_{30} +14$
이고 '비둘기집(또는 상자)'은 1에서 59까지의 자연수이다. 

'비둘기집 원리'에 의해 총 60개 대상 중 같은 것이 적어도 2개 존재해야 한다. 그런데
   $n_1 < n_2 < \cdots < n_{30}$
이므로 $n_1, n_2, \cdots , n_{30}$끼리 같을 수 없다. 
또한, 
   $n_1 +14 < n_2 +14 < \cdots < n_{30} +14$
이므로 $n_1 +14, n_2 +14, \cdots, n_{30} +14$끼리 같을 수 없다. 

따라서
   $n_j = n_i + 14$
를 만족하는 자연수 $i, j(1\leq i<j\leq 30)$가 반드시 존재한다. 

이 문제에서 '14'라는 수는 의미있는 특정한 수량이다. 

---

비둘기집 원리는 다음 문제와 같이, 패턴과 관련된 문제를 다룰 때도 유용하다. 

[예제 2]

$n$개의  정점 중 어느 두 점도 변으로 연결되어 있는 그래프를 '완전그래프'하고 $K(n)$으로 나타낸다. $K(6)$의 변을 무작위로  red와 blue로 채색하면 red $K(3)$가 있든지 아니면 blue $K(3)$가 있음을 보여라. 

$K(6)$의 한 정점 를 택한다. 어느 정점을 택하든 상관없다. $\rm P$에 연결된 변 중 '비둘기집 원리'에 의해 적어도 3개는 같은 색이다. 이 색을 red라 하자. blue라 해도 상관없다. 그 red 변의 3개의 끝점을 $\rm A, B, C$라 하자. 이제 우리는 다음과 같은 바램을 가져본다. 

완전그래프이므로 $\rm A, B, C$는 서로 변으로 연결되어 있다. 삼각형 $\rm ABC$가 blue $K(3)$라면 아주 좋다. 문제는 바로 해결된다. 그렇지 않을 때를 생각하자. 
삼각형  $\rm A, B, C$가 blue $K(3)$가 아니면 변 $\rm AB, BC, CA$중 적어도 하나는 red이다. 

일반성을 잃지않고 변 $\rm AB$가 red라고 하자. 이때 삼각형 $\rm PAB$ 는 red $K(3)$이다. 증명은 완성된다. 

---

[예제3] 

5개의 자연수로 이루어진 집합 $A = \left\{a_1, a_2, a_3, a_4, a_5\right\}$의 어떤 순열 $v_1, v_2, v_3, v_4, v_5$에 대하여 곱

   $(v_1-a_1)\times (v_2-a_2)\times\cdots\times(v_5-a_5)$
가 항상 짝수임을 보여라. 

이 문제에 비둘기집의 원리를 어떻게 적용해야 할까? 

우선, 정수의 기본성질에 의해 
   $v_i-a_i$
는 정수이고, 정수들의 곱이 짝수가 되기 위해서는 적어도 한 정수는 짝수여야 한다.
따라서
   $v_i-a_i, i=1,2,3,4,5$
중 짝수가 존재하는지 확인하면 충분하다. 

두 정수의 차가 
   (짝수)-(짝수), (홀수)-(홀수)
인 경우에 짝수가 된다. 즉, $v_i$와 $a_i$가 동일한 홀짝성을 갖는 경우가 있는지를 살펴 보아야 한다, 

이런 문제는 사실 정수에 대한 기본 지식없이는 비둘기집의 원리를 적용하는 정확한 지점을 찾기 어렵다. 

이제 우리는 5개의 수들의 '홀짝성'이 문제를 푸는 중요한 역할을 하리라는 것을 알수 있다. 비둘기집의 원리에 의해 동일한 '홀짝성'을 갖는 원소가 적어도 3개 존재한다. '비둘기'가 5개의 수이고 '비둘기집'은 짝수, 홀수 

이것을 편의상 
   $\left\{a_1, a_2, a_3\right\}$
라 하자. 그런데 이것은 
   $\left\{v_1, v_2, v_3\right\}$
과 서로소일 수 없다.  적어도 공통원소가 하나는 존재하여야 한다(왜일까?). 일반성을 잃지 않고
   $v_3 = a_1$
이라 하면, 
   $v_3-a_3 = a_1-a_3$
이고, $a_1$과 $a_3$는 같은 홀짝성을 가지므로 짝수이다. 이상에 의해 증명은 완성된다. 

---

[예제 4] 

임의의 $n^2+1$개의 실수로 이루어진 수열

   $a(1), a(2), \cdots, a(n^2+1)$

은 길이 $n+1$의 증가부분수열 혹은 길이 $n+1$의 감소부분수열을 포함함을 증명하여라. 

이 문제의 핵심은 길이 $n+1$의 증가부분수열 혹은 길이 $n+1$의 감소부분수열이 존재하느냐하는것이다. 만약, 길이 $n+1$의 증가 부분수열이 없다면, 길이 $n+1$의 감소부분수열이 있어야 함을 의미한다. 

길이 $n+1$의 증가 부분수열이 없다고 가정하자. $a(k)$로 시작하는 가장 긴 증가부분수열의 길이를 $T(a(k))$라고 하면 가정에 의해 
   $1 \leq T(a(k)) \leq n \ (k=1,2,\cdots,n^2+1)$
이므로 비둘기집 원리에 의해 다음을 만족하는 $k_1, k_2, \cdots, k_{n+1}$가 존재한다. 

   $T(a(k_1)) = T(a(k_2)) = \cdots = T(a(k_{n+1})),\ 1 \leq k_1 < k_2 < \cdots < k_1 ≤ n^2+1$

 

만약 
   $a(k_i)< a(k_{i+1})$
이라면,
   $k_i < k_{i+1}$
이고 
   $T(a(k_i)) > T(a(k_{i+1}))$이므로 모순!
그러므로 
   $a(k(i)) ≥  a(k(i+1)), (i=1,2,\cdots ,n)$
이다. 따라서
   $a(k_1) \geq a(k_2) \geq \cdots \geq a(k_{n+1})$
을 얻는다. 이것은 길이 $n+1$의 감소부분수열이다.