이산수학(Discrete Mathematics) - 비둘기 집 원리 (The Pigeonhole Principle)

이산수학(Discrete Mathematics) 비둘기집원리(The Pigeonhole Principle) 이산수학(Discrete Mathematics) 비둘기집원리(The Pigeonhole Principle) Pigeonhole Principle ( 비둘기집원리) 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) Examples of Pigeonhole Principle (1/3) 4.2 The Pigeonhole Principle 예제 1(생일 문제 ): 367명의 사람이 있다면 적어도 두 명은 생일이 같다 . . 가능한 생일은 366개이고, 사람이 이보다 하나 많다 . . 장소(생일)는 366개인데, 객체(사람)는 367이므로, 적어도 두 명은 생 일이 같게 된다 . 예제 3(성적 부여 문제 ): 0점에서 100점까지 1점 단위로 채점을 하게 되었을 때 , 적어도 두 명의 학생이 점수가 같다 하면 , 학생은 몇 명이 있어야 하는가 ? . 가능한 점수 (장소)는 0, 1, …, 99, 100 의 101개이고, . 점수에 할당되는 학생 (객체)이 102명이면, 두 명은 점수가 같게 된다 . Examples of Pigeonhole Principle (2/3) Examples of Pigeonhole Principle (2/3) 4.2 The Pigeonhole Principle 예제 4(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) 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.) 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명의 학생은 같은 주에 생일이 들어 있게 된다 . Proof of G.P.P. Proof of G.P.P. 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 ........111NNNkkkNkkk ........ .... . So, there are less than N objects, which contradicts our assumption of N objects! □ G.P.P. Examples (1/3) G.P.P. Examples (1/3) 4.2 The Pigeonhole Principle 예제 5(생일이 같은 달 …): 100명 중에서 적어도 몇 명은 같은 달에 태어났다고 볼 수 있는가 ? . .100/12. = 9명 . 적어도 9명은 태어난 달이 같게 된다 . G.P.P. Examples (2/3) G.P.P. Examples (2/3) 4.2 The Pigeonhole Principle 예제 7(카드 문제 ): 52장의 카드에서 적어도 3장은 같은 무늬가 나오는 것을 보장하기 위해 서는 몇 장의 카드를 선택해야 하는가 ? . 2 x 4 + 1 = 9 장 . 8장을 선택하면 , 최악의 경우에 같은 색이 두 장씩이고 , 여기에 한 장만 추가 하면, 적어도 세 장은 같은 색이 된다 . 적어도 3장의 하트 무늬 카드가 선택되기 위해서는 몇 장을 골라야 하나 ? . 13 x 3 + 3 = 42 장 . (재수 없게 , 최악의 경우에 ) 클로버, 다이아몬드, 스페이드가 13장씩 선택된 다면, 추가로 3장을 더 선택하면 이것은 모두 하트 무늬가 된다 . G.P.P. Examples (3/3) G.P.P. Examples (3/3) 4.2 The Pigeonhole Principle 예제 9(야구 경기 문제 ): 한 달이 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 경기를 하게 된다 .