답변 궁금해 하는 비둘기집의 원리(pigeonhole principle)란??

[수학일일구]

수업 시간에 설명하다보니 여러분이 궁금해하는 수학의 비둘기 집 원리에 대하여 간단히 설명하고자 합니다.

더 필요한 궁금증이나 예제 문제 또는 깊이 있는 원리를 원하시면 글을
주세요 여러분 !!!!!

재미있는 수학이 됬으면 합니다.

비둘기집의 원리(pigeonhole principle)

'비둘기집의 구멍수보다 비둘기가 더 많으면 적어도 한 구멍에는 두 마리 이상이 들어 있다'라는 원리를 말한다.
좀더 일반적으로 말하면, '비둘기의 수가 구멍수의 k배보다 더 많으면 어떤 구멍에는 적어도 k+1마리가 들어있다'라고 할 수 있다.
실제로 문제풀이에 많이 쓰이는 경우는, 'n+1마리의 비둘기가 n개의 구멍에 들어가려면 적어도 한 구멍에는 두 마리 이상 들어가야 한다'는 것이다.
이 원리의 증명은, 귀류법에 의하여 명백하므로 거의 필요로 하지 않는다. 즉, 모든 구멍에 한 마리 이하가 들어간다면 그 총 비둘기의 수는 n마리 이하이므로 처음에 생각한 n+1마리가 될 수 없기 때문이다.
쉬운 예로 탁구공 3개를 양손으로 잡으려면 한 손은 2개 이상 잡아야 한다.
이 원리를 디리클레 서랍 원리, 신장 원리라고도 한다.


[예제] 사람 13명 중에 적어도 두 사람은 같은 달에 생일이 있음을 설명하여라.


(풀이) 사람을 pigeon, 달을 pigeonhole이라 생각한다. 13명을 12달에 배정하면 같은 달에 배정되는 두 명이 있다.

[예제] 색깔이 다른 5켤레의 양말이 어둠 속에 뒤섞여 있다.
양말을 적어도 몇 짝을 집어야 색깔이 맞는 한 켤레가 포함되는가?


(풀이) 양말을 pigeon, 색깔을 pigeonhole이라 생각한다. 5개의 구멍 중 어떤 구멍에서 두 마리의 비둘기를 잡고 싶다는 것이다. 그러므로 양말 6짝을 집으면 반드시 색깔이 맞는 한 켤레가 포함된다. (답:6)

[예제] n명의 여자와 그들의 남편이 있다. 이 2n명의 집단에서 몇 명을 뽑아야 반드시 한 부부가 포함되는가?


(풀이) 남녀 각자를 pigeon, 부부를 pigeonhole이라 한다. 그러면 앞 예제와 같이 해결된다.
(답:n+1)