비둘기집 원리 :: Pigeonhole Principle

도입에 앞서, 한 예제를 볼까요?

런던의 모든 시민들은 그들의 머리카락 수가 런던 전체 시민수보다 적다고 한다. 런던 시민들 중 대머리가 없다고 가정할 때, 머리카락 수가 같은 시민이 적어도 두 사람 있음을 보여라.

와우.. 이러한 예제들은 증명하기에 어려움이 많아 보입니다. 한명한명 세보면서 비교 해보면 어떨까요? 런던 시민수가 한 두명도 아니고.. 거기에다가 머리카락수까지 셀려니 앞길이 깜깜해보입니다.. 이럴 때 증명을 도와줄 비둘기집 원리,

이렇게 어려운 예제도 간단히 풀어준다니.. 참 대단한 원리인 거 같죠? 점점 알고 싶어지는 비둘기집 원리를 살펴봅시다!

: "n+1개의 물건을 n개의 상자에 넣을 때 적어도 어느 한 상자에는 두개 이상의 물건이 들어 있다."

음? 증명할 필요없이 너무 자명해보입니다. 물건을 일대일대응으로 상자에 넣어도 한개의 물건이 남기 때문입니다.

그런데, 이 별거 아닌 것 처럼 보이는 원리가 다양한 논제에서 활용되고 있습니다.

••• 다시 처음으로 돌아와, 예제를 상기해봅시다.

런던 전체 시민수를 x라 하자. 그들의 머리카락 수는 런던 전체 시민수보다 작으므로 1,2, ... , x-1개 까지의 가짓수가

가능한데, x-1 < x 로 비둘기집의 원리에 의해 ∴ 머리카락 수가 같은 런던 주민이 적어도 두사람 존재하게 된다.

이렇게 비둘기집 원리로 아주 간단하게 복잡한 논제들을 증명할 수 있습니다! 그렇다면 비둘기집 원리를 증명해봅시다.

명제를 거짓하다고 가정하고 모순임을 증명하는 귀류법을 사용해봅시다.

: n개의 비둘기집과 n+1마리의 비둘기가 있다고 가정하자.

만약 각 비둘기집에 한마리 이하의 비둘기만 들어있다면, 전체 비둘기집에는 많아야 n마리의 비둘기가 존재한다.

그런데 비둘기는 모두 n+1마리이므로, 이것은 모순이다. ∴ 어느 비둘기집에는 두마리 이상의 비둘기가 있다.

+일반화

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

(여기서, [x]는 x보다 작지 않은 최소 정수를 의미한다.)

비둘기집의 원리는 별거 아닌거 같지만 엄청난 활용도를 갖고 있는 원리이니 참고해두시면 좋을 거 같습니다.

p.s. 여기까지 읽어주시느라 수고 하셨습니다..♡ 사실, 이 글이 이 블로그의 첫 글입니다..ㅎㅎ 앞으로 유익하고 친절한 글들 올리기 위해 노력할테니까 지켜봐주세요!! ㅎㅎ (아, 참고로 수학 관련 글들 많이 올릴거 같습니다..ㅎㅎ)

참고.

위키백과, "pigeonhole principle", https://en.wikipedia.org/wiki/Pigeonhole_principle , (2020.01.27)

'MATH♪' Related Articles