[이산수학] 비둘기집 이론(Pigeonhole Principle)

비둘기집 이론(Pigeonhole Principle)

비둘기집 이론 
 : n개의 비둘기집에 n+1마리의 비둘기를 나누어 넣는다면, 적어도 한 집에는 2마리가 들어간다는 이론

---

증명 - 모순 증명법(Contradiction)

   p : 비둘기집(x)이 n개, 비둘기(y)가 k마리라면 (k ≥ n + 1)

   q : 적어도 한 집에는 두 마리 이상이 들어간다

 

   Contradiction : ￢(p→q) = p∧￢q

   즉, p이고 q가 아니면 거짓이다를 증명하면 비둘기집 이론 성립.

  ￢q : 한 집에는 비둘기가 1마리 이하이다.

   한 집에 비둘기가 한 마리 이하라면 총 비둘기 수 k는 k ≤ n이 된다.

   이때 p의 조건에서 k ≥ n + 1이라는 조건이 있었고, 이는 true이기에 동시에 성립할 수 없음.

   모순이 일어나므로, 비둘기집 이론은 True.

---

그냥 상식선에서 생각해봐도 너무나도 당연한 이론.

하지만 이를 이용해 얻을 수 있는 정리나 법칙이 여럿 존재한다.

 

• 일대일함수의 조건
  f : X→Y라는 함수가 있을 때, |X| = k+1, |Y| = k라면 일대일함수가 될 수 없음. (적어도 하나의 Y는 2개의 X와 연결됨)
• 모든 자연수의 배수는 0, 1로만 나타낼 수 있는 수를 배수로 가진다.
  임의의 n을 정하고, n+1개의 1을 아래와 같이 나열.
  

  1
  1	1
  1	1	1
  1	1	1	1
  1	1	1	1	1

  n = 4라고 가정했을 때, 위와 같이 나열할 수 있다.
  각 수 1, 11, 111, 1111, 11111을 4로 나누면 나머지가 같은 수가 최소 하나는 존재한다.
  (0, 1, 2, 3의 4가지가 나머지가 될 수 있는데, 수는 5개이기 때문)
  {1, 11, 111, 1111, 11111}의 나머지를 살펴보면 {1, 3, 3, 3, 3}이 된다.
  이때 나머지가 같은 두 수를 빼주면 4의 배수이면서 나머지가 없는 수가 완성된다. 11111 - 1111 = 10000
  이때 나열된 수끼리 뺄셈을 하게 되면 0과 1만 나올 수 있음.
  ∴ 모든 자연수의 배수는 0, 1로만 나타낼 수 있는 수를 배수로 가진다.

너무나도 당연한 이론이지만, 이러한 재미있는 사실들을 이끌어 낼 수 있다.

그리고 n과 k가 1차이가 아닌, 더 큰 차이가 나는 경우도 성립한다.

일반화된 비둘기집 이론(Generalized Pigeonhole Principle)
 : n개의 비둘기집에 k마리의 비둘기를 나누어 넣는다면, 적어도 한 집에는 ⌈n/k⌉마리가 들어간다는 이론

---

증명 - 모순 증명법(Contradiction)

   p : 비둘기집(x)이 n개, 비둘기(y)가 k마리라면
   q : 적어도 한 집에는 ⌈n/k⌉마리 이상이 들어간다

  ￢q : 한 집에는 비둘기가 ⌈n/k⌉ - 1마리 이하이다.

 

   한 집에 ⌈n/k⌉ - 1마리 이하가 들어가므로, n ≤ k(⌈n/k⌉ - 1)

   이때 ceiling lemma로 인해 n ≤ k(⌈n/k⌉ - 1) < k(n/k + 1 - 1) = n (ceiling lemma : x ≤ ⌈x⌉ < x+1)

   이를 정리하면 n < n이라는 수식이 나오는데, 이는 성립할 수 없음.

   모순이 일어나므로 일반화된 비둘기집 이론은 True.

---