비둘기집 문제

[질문]

1) 13명 중에 적어도 두 사람은 같은 달에 생일이 있음을 설명하라.

2) 색깔이 다름 10컬레의 장갑이 어둠 속에 뒤섞여 있다. 이중에서 장갑을 적어도 몇 짝을 집어야 색깔이 맞는 한 컬레가 포함되는가?

3) 가로, 세로 길이가 2m인 방안에 5개의 인형을 놓을 때 임의의 두 인형은 반드시 √2m이내에 있게 됨을 보여라.

4) 어느 파티에 30명이 있다. 같은 수의 친구를 가진 두 명이 있음을 설명하라.

5) 한 변의 길이가 1인 정삼각형 안에 5개의 점을 잡으면 거리가 1/2 이하인 두 점이 존재함을 밝혀라.

6) 사과 10개, 바나나, 15개 수박 5개, 참외 7개, 자두 20개가 있다. 이  중 몇 개를 골라야 같은 종류의 과일 9개가 반드시 포함되는가? (예를 들면, 사과 8개+바나나2개+수박2개+자두9개)

7) 한 고등학교에 30개의 반이 있다.한 반에서 5명을 뽑아 봉사활동을 가고자 한다. 학생들이 공부를 하느라 바쁘다는 이유로 참여를 잘 하지 않는다는 것을 알고 있다. 그래서 그 30개의 반에서 신청서를 받고자 한다. 신청서를 적어도 몇 장을 받아야 신청자 중에 같은 반 학생 5명이 클림없이 포함된다고 할 수 있는가?

[답변]

문제가 너무 많네요.  비둘기집 원리는 무엇인지 알죠?  이런 문제들은 "비둘기집 원리에 의해서"로 증명이 되는 문제입니다.

1) 13명 중에 적어도 두 사람은 같은 달에 생일이 있음을 설명하라.

-> 모든 사람은 12달중 1달에 생일이 있으므로, 비둘기집 원리에 의해서 적어도 한달에 두명 이상의 생일을 가진 경우가 존재한다.

2) 색깔이 다름 10컬레의 장갑이 어둠 속에 뒤섞여 있다. 이중에서 장갑을 적어도 몇 짝을 집어야 색깔이 맞는 한 컬레가 포함되는가?

-> 11컬레.  10개의 색깔이 있으므로 11개의 장갑을 집으면 적어도 두개의 장갑은 같은 색이 된다.

3) 가로, 세로 길이가 2m인 방안에 5개의 인형을 놓을 때 임의의 두 인형은 반드시 √2m이내에 있게 됨을 보여라.

-> 이 문제는 비둘기집 원리로 풀기 좀 갑갑하네요.  1m x 1m 공간에 두개의 인형이 들어갈 수 없다.  왜냐하면 1m x 1m 에서 가장 먼 거리가 √2m이므로.  이 공간은 4개.. 인형은 5개이므로 비둘기집 원리에 의해서 적어도 두개의 인형은 같은 공간에 들어간다.

4) 어느 파티에 30명이 있다. 같은 수의 친구를 가진 두 명이 있음을 설명하라.

-> 이 문제는 좀 다른 식으로 풀어야겠네요.  물론 비둘기집 원리가 이 풀이에 들어갑니다.  A가 B의 친구라면 B도 A의 친구라고 가정해야 문제를 풀 수 있겠죠.  친구의 수가 같은 경우가 없다면 1부터 30까지 각각 친구들을 가져야 하는데, 이 경우 친구의 수의 합은 홀수가 되어 서로 친구라는 가정에 위배된다.

5) 한 변의 길이가 1인 정삼각형 안에 5개의 점을 잡으면 거리가 1/2 이하인 두 점이 존재함을 밝혀라.

-> 가로세로 2m의 방과 마찬가지로 1/2 길이의 정삼각형 4개를 잡으면 됩니다.

6) 사과 10개, 바나나, 15개 수박 5개, 참외 7개, 자두 20개가 있다. 이  중 몇 개를 골라야 같은 종류의 과일 9개가 반드시 포함되는가? (예를 들면, 사과 8개+바나나2개+수박2개+자두9개)

-> 수박 5 + 참외 7 + 사과 8 + 바다나 8 + 자두 8 + 1 = 37..  답 37개

7) 한 고등학교에 30개의 반이 있다.한 반에서 5명을 뽑아 봉사활동을 가고자 한다. 학생들이 공부를 하느라 바쁘다는 이유로 참여를 잘 하지 않는다는 것을 알고 있다. 그래서 그 30개의 반에서 신청서를 받고자 한다. 신청서를 적어도 몇 장을 받아야 신청자 중에 같은 반 학생 5명이 클림없이 포함된다고 할 수 있는가?

-> 30 x 4 + 1 = 121  답 121장