2025년, 코딩은 선택이 아닌 필수!

2025년 모든 학교에서 코딩이 시작 됩니다. 먼저 준비하는 사람만이 기술을 선도해 갑니다~

강의자료/이산수학문제풀이

[정보올림피아드 대비]12. 비둘기집의 원리를 이용한 문제

원당컴1 2022. 11. 10. 09:10
비둘기집의 원리는 다음과 같습니다.
비둘기집은 2개이고 비둘기는 3마리입니다.
비둘기가 저녁에 잠을 자기 위해 들어가야 되는데~
그렇다면 반드시 한개의 비둘기 집에는 비둘기가 2마리 이상 존재하게 된다는 원립니다.

이러한 원리를 다음과 같이 정의 됩니다.
n개의 배둘기집과 n+1마리의 비둘기가 있다고 가정한다.
만약 각 비둘기집에 한마리 이하의 비둘기만 들어 있다면, 전체 비둘기집에는 많아야 n마리의 비둘기가 존재한다. 그런데 비둘기는 모두 n+1마리 이므로 이것은 모순이다. 따라서 어느 비둘기집에는 두마리 이상의 비둘기가 있다.

이것을 일반화된 원리로 정의를 하면 다음과 같이 정의 된다.
n개의 별개의 사물을 m개의 용기에 담으면 적어도 한개의 용기는 n/m 이상의 사물을 담고 있어야 한다.

1. 어느 지역은행은 고객들에게 ATM 카드를 사용할 때 필요한 4자리 코드를 신청하도록 하였다. 코드의 첫 두 자리는 알파벳 문자이어야 하고, 세번째와 네번째 두 자리는 숫자로 구성되어야 한다. 이 은행에는 75000명의 고객이 있다. 적어도 두명의 고객은 같은 코드를 선택하게 됨을 증명하여라

문제풀이)

더보기

먼저 코드를 만드는 경우가 몇가지인지 원소의 갯수를 세어보면 첫째자리와 넷째자리가 알파벳이므로 26*26

둘째자리와 셋째자리가 숫자이므로 10*10 이므로 모든 경우는 26 * 10 * 10 * 26 = 67600 가지가 나온다.

하지만 고객은 이것보다 큰 75000 명이므로 반드시 한개의 코드는 75000/67500 이상인 사람이 사용할 수 밖에 없기 때문에 2명 이상인 사람이 사용할 수 밖에 없습니다.

2. 159개의 팀이 있다.

만약 하나의 리그에 많아야 8팀이 포함될 수 있다면, 최소한 얼마나 많은 리그를 만들어야 하는가?

만약 10팀,또는 12팀이 포함될 수 있다면 최소한 얼마나 많은 리그를 만들어야 하는가?

(단, 여기서 리그전이란 스포츠 경기에서 각 팀이 다른 팀과 모두 최소 한번씩 경기를 치르는 경기 방식이다.)

문제풀이)

더보기

n개의 별개의 사물을 m개의 용기에 나누어 담으면 적어도 한개의 용기는 n/m 이상의 사물을 담고 있어야 한다.

이 원리를 이용하면

159/8 이상이므로 20개의 리그

10팀인 경우는 159/10 이상이므로 16개의 리그

12팀인 경우는 159/12 이상이므로 14개의 리그 라는 것을 확인할 수 있습니다.

3. 1~20의 20개의 자연수 중에서 임의로 몇개의 수를 뽑아야 그 중에 차가 12인 두 수가 반드시 존재하겠습니까?

(단, 뽑은 수는 다시 뽑지 않습니다.)

문제풀이)

더보기

최악의 경우 처음 1을 뽑았을때 2~12까지를 뽑는 동안은 12의 차이가 안납니다. 이렇게 12개를 뽑은 후에는 반드시 두 수의 차이가 12인 수가 존재 할 수 밖에 없기 때문에 13개를 뽑으면 반드시 존재합니다.

4. 2,4,6...,30의 15개의 짝수 중에서 임의로 몇개의 수를 뽑아야 두수의 합이 34가 반드시 존재하겠습니까?

(단, 뽑은 수는 다시 뽑지 않습니다.)

문제풀이)

더보기

34가 되는 두수의 쌍을 살펴보면

2 - 없음

4 - 30

6 - 28

8 - 26

10 - 24

12 - 22

14 - 20

16 - 18

이렇게 7개의 쌍이 있습니다.

최악의 경우 처음 8개의 수를 2,4,6,8,10,12,14,16 8개의 숫자를 선택했다고 하면 9번째 선택하는 어떤 수는 반드시 34를 만들 수 있습니다.

 

역대 기출문제]

https://docs.google.com/forms/d/e/1FAIpQLSd2LmAV7xDPT-GxXdmuTiVU8mODj2MsI_b_1QJ7-I6nisW61A/viewform

 

13-1. 비둘기집의 원리를 이용한 문제

 

docs.google.com

 

사업자 정보 표시
원당컴퓨터학원 | 기희경 | 인천 서구 당하동 1028-2 장원프라자 502호 | 사업자 등록번호 : 301-96-83080 | TEL : 032-565-5497 | Mail : icon001@naver.com | 통신판매신고번호 : 호 | 사이버몰의 이용약관 바로가기