이산수학(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 경기를
하게
된다
.