이산수학(Discrete Mathematics) 비둘기 집 원리 (The Pigeonhole Principle) 2013년 봄학기 강원대학교 컴퓨터과학전공 문양세

Pigeonhole Principle (비둘기 집 원리) 4.2 The Pigeonhole Principle A.k.a.(as known as) Dirichlet drawer principle (또한, “디리크레의 서랍 원리”라고도 알려짐) If ≥k+1 objects are assigned to k places, then at least 1 place must be assigned ≥2 objects. (k+1개의 객체(비둘기)가 k개의 장소(상자, 비둘기 집)에 배분된다면, 적어도 한 곳은 두 개 이상의 객체가 배분된다.) In terms of the assignment function: If f:A→B and |A|≥|B|+1, then some element of B has ≥2 preimages under f. That is, f is not one-to-one.

Examples of Pigeonhole Principle (1/3) 4.2 The Pigeonhole Principle 예제(생일 문제): 367명의 사람이 있다면 적어도 두 명은 생일이 같다. 가능한 생일은 366개이고, 사람이 이보다 하나 많다. 장소(생일)는 366개인데, 객체(사람)는 367이므로, 적어도 두 명은 생일이 같게 된다. 예제(성적 부여 문제): 0점에서 100점까지 1점 단위로 채점을 하게 되었을 때, 적어도 두 명의 학생이 점수가 같다 하면, 학생은 몇 명이 있어야 하는가? 가능한 점수(장소)는 0, 1, …, 99, 100의 101개이고, 점수에 할당되는 학생(객체)이 102명이면, 두 명은 점수가 같게 된다.

Examples of Pigeonhole Principle (2/3) 4.2 The Pigeonhole Principle 예제(n의 배수 문제): 정리: 모든 정수 n에 대해서, n의 배수 중에는 0과 1만을 포함하는 십진수가 반드시 존재한다. n을 양의 정수라 하고, n+1개의 정수 1, 11, 111, …, 111  1(1이 n+1개)가 있다고 하자. 어떤 정수를 n으로 나누었을 때, 가능한 나머지의 개수는 최대 n개이다. (나머지의 가능한 범위는 0 ~ n-1 이므로) 따라서, 비둘기 집 원리에 의해 상기 n+1개의 정수 중에서 적어도 두 수는 나머지가 같게 된다. 이들 두 수를 각각 x와 y라 하자(x > y). 이 두 수 x와 y의 차를 z(= x – y)라 했을 때, z는 n으로 나누어 떨어지고, 이 수는 0과 1로만 표현된다. (x%n = y%n 이므로, z%n = 0이 된다.) Please refer to an example in the next slide.

Examples of Pigeonhole Principle (3/3) 4.2 The Pigeonhole Principle Let n = 3. Consider 1, 11, 111, 1111. 1 % 3 = 1 11 % 3 = 2 111 % 3 = 0 1,111 % 3 = 1 1,111 – 1 = 1,110 = 370 x 3 It has only 0’s and 1’s in its expansion. 1,110 mod 3 = 0, so it’s a multiple of 3.

Generalized Pigeonhole Principle (G.P.P.) 4.2 The Pigeonhole Principle If N objects are assigned to k places, then at least one place must be assigned at least N/k objects. (N개의 객체가 k개 장소에 배정된다면, 적어도 한 곳은 N/k개 객체를 가진다.) E.g., there are N=280 students in this class. (학생 280명) There are k=52 weeks in the year. (한 해는 52주) Therefore, there must be at least 1 week during which at least 280/52= 5.38=6 students in the class have a birthday. (일반화된 비둘기 집 원리에 의해서) 최소 6명의 학생은 같은 주에 생일이 들어 있게 된다.

Then the total number of objects is at most Proof of G.P.P. – skip 4.2 The Pigeonhole Principle By contradiction. Suppose every place has < N/k objects, that is, suppose every place has ≤ N/k−1 objects. Then the total number of objects is at most So, there are less than N objects, which contradicts our assumption of N objects! □

예제(생일이 같은 달…): 100명 중에서 적어도 몇 명은 같은 달에 태어났다고 볼 수 있는가? G.P.P. Examples (1/3) 4.2 The Pigeonhole Principle 예제(생일이 같은 달…): 100명 중에서 적어도 몇 명은 같은 달에 태어났다고 볼 수 있는가? 100/12 = 9명 적어도 9명은 태어난 달이 같게 된다.

G.P.P. Examples (2/3) 4.2 The Pigeonhole Principle 예제(카드 문제): 52장의 카드에서 적어도 3장은 같은 무늬가 나오는 것을 보장하기 위해서는 몇 장의 카드를 선택해야 하는가? 2 x 4 + 1 = 9장 8장을 선택하면, 최악의 경우에 같은 색이 두 장씩이고, 여기에 한 장만 추가하면, 적어도 세 장은 같은 무늬가 된다. 적어도 3장의 하트 무늬 카드가 선택되기 위해서는 몇 장을 골라야 하나? 13 x 3 + 3 = 42장 (재수 없게, 최악의 경우에) 클로버, 다이아몬드, 스페이드가 13장씩 선택된다면, 추가로 3장을 더 선택하면 이것은 모두 하트 무늬가 된다.

G.P.P. Examples (3/3) 4.2 The Pigeonhole Principle 예제(야구 경기 문제): 한 달이 30일 때, 야구 팀이 매일 적어도 한 경기씩 경기를 하는데, 45경기 이하를 한다. 그러면, 이 팀이 14경기를 연속적으로 하는 기간이 반드시 존재함을 증명하라. (즉, ith day에서 jth day까지의 경기 합이 반드시 14인 ith day와 jth day가 존재함을 증명하라.) 먼저, kth day까지의 누적 경기 수를 ak라 하면, a1, a2, …, a30은 증가하는 양의 수열이고, 1 ak  45이다. 또한, a1+14, a2+14, …, a30+14 도 증가하는 양의 수열이다. 이때, 60개의 양의 정수 a1, a2, …, a30, a1+14, a2+14, …, a30+14 는 모두 59이하이다. (ak가 45이하이므로) 따라서, 비둘기 집 원리에 의해, 이들 60개 중 적어도 두 개는 같은 수가 된다. 그런데, a1, a2, …, a30는 모두 다른 수이고, a1+14, a2+14, …, a30+14 도 모두 다른 수이므로, ai = aj + 14를 만족하는 i와 j가 반드시 존재한다. 결국, j+1번째 날에서 i번째 날까지는 정확히 14 경기를 하게 된다.