6.2 비둘기집원리

(1)

6.2 비둘기집 원리

이산수학 <제6장> 계수

이상준 교수

(덕성여대 수학과)

교재 : 이산수학 (7판)

Kenneth H. Rosen 지음, 공은배 등 옮김 강의 슬라이드 : 이상준, 오연주(15)

(2)

비둘기집 원리

예제: 13마리의 비둘기를 12개의 비둘기집에 넣는다면,

적어도 하나의 비둘기집에는 두마리 이상의 비둘기가 들어가게 된다.

증명1: (귀류법) 두마리 이상의 비둘기가 들어간 비둘기집이 없다고 하면 비둘기의 총 마리수는 최대 12이다. 모순!

(3)

정리1: k+1개 이상의 물체를 k개의 상자에 넣는다면,

적어도 하나의 상자에는 두 개 이상의 물체가 들어가게 된다.

증명1: (귀류법)

증명2: (평균값)

따름정리1: k+1개 또는 그 이상의 원소를 가진 집합으로부터 k개의 원소를 가진 집합으로의 함수는 일대일 대응이 아니다.

(4)

예제1: 367명의 사람이 있으면 적어도 두 명은 생일이 같다.

왜냐하면, 가능한 생일은 366(2월29일 포함)개이기 때문이다.

예제2: 영어 단어 27개를 뽑으면 그 중에 같은 문자로 시작되는 단어가 있다.

왜냐하면, 영어 알파벳은 모두 26개이기 때문이다.

예제3: 0점에서 100점까지 1점 단위로 채점되는 기말시험에서 적어도 2명의 학생이 같은 점수가 되는 것을 보장하기 위해서는 몇 명의 학생이 있어야 하는가?

풀이: 기말시험에서 나올 수 있는 가능한 점수는 101가지이다.

비둘기집 원리에 의하면, 102명의 학생이 있으면 적어도 두 명은 같은 점수를 갖게 된다.

(5)

일반화된 비둘기집 원리

정리2: N개의 물체를 k개의 상자에 넣는다면,

적어도 하나의 상자에는 ^!_" 개의 물체가 들어가게 된다.

책의 증명: (귀류법) 물체가 ^!_" − 1개보다 많이 들어가는 상자는 없다고 하자.

그러면물체 수의 합계는많아야 k ^!_" − 1 < 𝑘 ^!

" = 𝑁.

즉 N보다 작게 된다.

N개의 물체가 있다는 사실에 모순이 된다.

교수의 증명: (평균값)

(6)

예제5: 100명의 사람이 있으면 그 중에서 같은 달에 태어난 ^+,,_+- =9명이 있다.

예제7:

a) 52장의 표준 카드에서 적어도 3장은 같은 무늬가 나오는 것을 보장하기 위해 서는 몇 장의 카드를 선택하여야 하는가?

b) 적어도 3개의 하트 무늬 카드가 선택되는 것이 보장되기 위해서는 몇 장을 선 택해야 하는가?

(7)

비둘기집 원리의 응용

예제9: 컴퓨터 실습실에 서버 10대와 워크스테이션 15대가 있다.

서버와 워크스테이션은 케이블로 직접 연결될 수 있다.

각각의 서버는 한 순간에 연결된 하나의 워크스테이션에만 접속될 수 있다.

10대 이하의 워크스테이션이 사용된다면 언제라도 서버들에 접속될 수 있음을 보장 하고자 한다.

필요한 최소의 연결선은 몇 개인가?

정답: 60개의 연결선이 필요하다.

목표:

(Part 1)

60개 미만의 연결선으로는 불가능하다.

증명

(Part 2)

60개의 연결선으로 가능하다.

연결방법

증명

(8)

(Part 1)

60개 미만의 연결선으로 불가능하다.

60개 미만의 연결선이 사용되었다고 하자.

각 서버는 평균적으로 많아야 ^./_+, 대의 워크스테이션에 연결되어 있다.

^./

+, =5 이므로, 5대의 워크스테이션밖에 연결되지 못한 서버가 존재한다.

(평균의 원리)

그 서버에 연결되어 있지 않은 나머지 10대의 워크스테이션이 동시에 컴퓨터 실습실의 서버들로 연결될 수 없다.

(9)

(Part 2)

60개의 연결선으로 가능하다.

연결방법:

워크스테이션을 𝑊₊, 𝑊_-,… , 𝑊_+.라 하고, 서버를 𝑆₊,𝑆_-, … , 𝑆_+,이라 하자.

j=1,2,...,10 에 대해서 𝑊₄를 𝑆₄에 연결하고,

𝑊₊₊, 𝑊_+-, 𝑊₊₅, 𝑊₊₆, 𝑊_+.는 각각 10개 서버 모두에 연결하자.

그러면 총 60개의 연결선이 필요하다.

증명: 위 연결 방법은 항상 10개 이하의 임의의 워크스테이션들이 사용될 때 컴퓨터 실습실의 서버들에 연결될 수 있음을 보이자.

우선, 1≤j≤10인 워크스테이션 𝑊₄가 사용되면 서버 𝑆₄에 연결한다.

그 후에, k≥11인 워크스테이션 𝑊_"이 사용된다면

1≤j≤10사이에 사용되지 않은 워크스테이션 𝑊₄가 반드시 존재하므로

𝑊_"는 서버 𝑆₄에 연결하면 된다.

(1≤j≤10사이에서 포함되지 않은 워크스테이션 𝑊₄만큼의 서버 𝑆₄가 사용가능 하기 때문이다.)

(10)

(11)

(12)

단조 부수열의 존재성

질문: 길이가 n+1인 단조증가 또는 단조감소 부수열을 항상 갖기 위해서는 전체 수열의 길이가 얼마면 될까?

쉬운 질문: 길이가 4인 단조증가 또는 단조감소 부수열을 항상 갖기 위해서는 전체 수열의 길이가 얼마면 될까?

예제: 9개의 항이 있는 수열 중 길이가 4인 단조증가 또는 단조감소 부수열을 가지지 않 은 것이 있다.

예제12: 수열 8,11,9,1,4,6,12,10,5,7은 10개의 항이 있다.

(13)

일반화

정리: 길이가 𝑛^-인 수열 중 단조증가 또는 단조감소하는 길이 n+1의 부수열을 포함 하지 않는 것이 있다.

증명:

(14)

정리3: 𝑛^- + 1개의 서로 다른 실수로 구성된 모든 수열은

단조증가 또는 단조감소하는 길이 n+1의 부수열을 포함한다.

증명:

(15)

비둘기집 원리의 또 다른 응용

더 현명한 방법이 필요한 경우가 있다.

예제10: 한 달이 30일인 어느 달에 야구팀이 매일 적어도 한 경기를 하는데 한 달 동안 총 45경기 이하만 시합한다. 이 팀이 정확히 14경기를 치루어야만 하는 연속된 기간이 한 달 중 반드시 존재함을 증명하라.

증명:

(16)

예제11: 2n이하인 n+1개의 양의 정수 중에는 다른 수의 약수가 되는 정수가 반드시 존재함을 증명하라.

증명:

(17)

예제13: 여섯 명의 그룹에서 두 명이 짝을 지으면 서로 친구이거나 적이라고 가정하 자. 이 그룹에는 세 명이 서로 친구이거나 세 명이 서로 적인 경우가 존재함을 증명 하라.

증명:

6.2 비둘기집원리