brunch

매거진 그냥 수학 문제가 풀고 싶어서

라이킷 4 댓글 1

You can make anything
by writing

C.S.Lewis

계정을 잊어버리셨나요?

by 박종하 Jan 11. 2019

15. [수학 논리] 비둘기 집의 원리

수학적인 논리 기술을 활용하여 현상을 증명한다

이런 증명은 정말 쉽지 않은 일일 것 같습니다. 이 증명은 ‘비둘기 집의 원리’를 적용하면 쉽게 생각할 수 있습니다. 흥미로운 비둘기 집의 원리를 한번 살펴볼까요?

먼저 사람의 머리카락 수는 머리숱이 아무리 많은 사람이라도 10만 개를 넘지는 않는다고 합니다. 이렇게 생각해보죠. 20만 명의 사람들에게 자신의 머리카락과 같은 수의 번호표를 준다고 생각해보세요. 그럼, 사람들은 모두 1부터 10만 사이에 있는 번호표를 받았을 겁니다. 대머리인 사람은 특별하게 고려할 필요는 없을 것 같네요. 이번에는 1부터 10만까지의 번호가 붙은 방을 상상해볼까요? 10만 개의 방이 있는데, 방문에는 1부터 10만까지의 번호가 각각 붙어 있는 겁니다. 이제 사람들에게 자신의 번호표에 해당하는 방을 찾아가게 하는 겁니다. 사람 수는 20만 명입니다. 방은 10만 개이고요. 10만 개의 방에 한 명씩 골고루 들어갔다고 하더라도 10만 명의 회원이 남습니다. 따라서 2명 이상의 사람이 동시에 들어가 있는 방은 반드시 있다고 말할 수 있고, 적어도 10만 명의 사람들은 2명 이상이 있는 방에 들어가게 됩니다. 같은 방에 있는 사람들은 머리카락 수가 같은 사람들이므로, 결론적으로 머리카락이 같은 사람이 적어도 10만 명은 된다는 것을 알 수 있습니다.

지금 소개한 증명의 방법을 ‘비둘기 집의 원리’라고 합니다. 직접적으로 증명하기 어려운 문제를 간접적으로 증명할 때 매우 유용하게 쓰이는 방법이죠. 비둘기 집의 원리를 설명하면 다음과 같습니다.

1. 100마리의 비둘기가 100개의 비둘기 집에 들어갔다. 그때 빈집이 하나도 없었다면 모든 비둘기 집에는 한 마리의 비둘기가 들어간 것이다. 반대로 모든 비둘기 집에 한 마리의 비둘기만 들어갔다면, 빈집은 없다.

2. 100마리의 비둘기가 99개의 비둘기 집에 모두 들어갔다면, 적어도 하나 이상의 비둘기 집에는 2마리 이상의 비둘기가 들어가 있다.

비둘기 집의 원리를 처음 들으면 매우 유치하고, “뭐 이런 게 다 있나? 당연한 걸 가지고, 무슨 원리라니”하는 생각이 듭니다. 하지만, 앞에서 소개한 ‘머리카락 수가 같은 사람이 반드시 있다’는 것과 같은 결론을 내거나 증명을 할 때에는 비둘기 집의 원리를 사용하지 않으면 거의 불가능합니다. 단순하면서도 수학적으로는 매우 강력한 증명의 도구인 겁니다. 몇 가지 질문을 더 해볼까요?

어려운 질문이 아닌데, 많은 사람들이 11짝을 꺼내봐야 한다고 답하곤 합니다. 처음 꺼낸 양말이 흰색이고 다음에 꺼낸 양말이 검은색이고, 그다음 꺼낸 양말이 검은색이고, 최악의 경우 계속 검은색이 나오면 11개의 양말을 꺼내봐야 한다고 생각하는 것이죠. 하지만, 사실은 그렇지 않습니다. 꼭 처음에 꺼낸 색의 양말만을 맞춰야 하는 것이 아니기 때문에 3짝만 꺼내면, 같은 색의 양말 1켤레를 신을 수 있습니다. 이것도 비둘기 집의 원리로 생각해보면, 먼저 마음속에 흰색 방과 검은색 방을 만들어보는 겁니다. 그리고 임의로 꺼낸 양말을 같은 색의 방에 넣는 것이죠. 이렇게 생각하면 운이 나쁘게 처음에 꺼낸 두 양말의 색깔이 달라 각각 다른 방에 들어가더라고 세 번째 꺼낸 양말이 둘 중 하나의 방으로 가기 때문에 어느 한쪽에는 같은 색의 양말 두 짝이 있다는 것을 알 수 있습니다.

비둘기 집의 원리를 적용할 때, 우리는 방을 상상했습니다. 이렇게 생각의 기술에는 상상이 들어갑니다. 수학 문제라고 하면 그냥 계산만 하면 될 것 같지만, 사실은 그렇지 않습니다. ‘머리카락 수가 같은 사람이 반드시 있다’는 증명에서 경험한 것처럼 조금 어렵고 복잡한 문제를 풀 때에는 상상을 해야 합니다. 상상이란 존재하지 않는 것을 생각하는 것이죠. 상상을 활용하는 방법으로는 종이에 기호나 도식으로 표현하며 생각하는 것이 좋은 방법입니다. 다음과 같은 문제를 풀어볼까요?

사과만 들어있는 상자, 오렌지만 들어있는 상자, 그리고 사과와 오렌지가 함께 들어있는 상자, 이렇게 3개의 상자가 있다. 그런데, 상자에 붙은 라벨이 모두 틀리게 붙어있다. 하나의 상자를 선택하여 과일 하나만을 꺼내보고, 모든 라벨을 정확하게 수정할 수 있다.

하나의 상자에서 하나의 과일을 꺼내보는 것으로는 문제가 해결되지 않을 것같이 보입니다. 하지만, 이 문제는 ‘상자에 붙은 라벨이 모두 틀리게 붙어있다’는 조건을 이용하여 해결할 수 있습니다. 이 문제를 풀기 위해서는 먼저 다음과 같은 표를 그려보시죠.

이렇게 생각해볼까요? 먼저 오렌지와 사과가 같이 들어있다고 표시된 상자에서 과일 하나를 꺼내는 겁니다. 사과와 오렌지가 같이 들어있다고 라벨이 붙은 상자에는 사과나 오렌지 둘 중 하나만 들어있을 겁니다. 라벨이 모두 잘못 붙어있다는 조건이 있었으니까요. 만약, 꺼낸 과일이 사과라면, 그 상자는 사과 상자입니다. 오렌지 라벨이 붙어있던 상자에는 사과가 있을 수 없기 때문에 그 상자는 사과/오렌지 상자이고, 사과 라벨이 붙어있는 상자는 오렌지 상자입니다.

비둘기 집의 원리에서 경험한 것처럼, 어려운 문제를 해결하는 생각의 기술에는 상상하는 부분이 있습니다. 보이지 않는 것을 상상하고 존재하지 않는 것을 상상하는 것이죠. 종이에 간단한 도형이나 도식을 이용하면 상상하는데 훨씬 도움이 될 것입니다. 사실 상상하는 것의 핵심은 능동적으로 생각한다는 것입니다. 주어진 상황으로만 생각하는 것이 아니라, 능동적으로 이런저런 상황을 설정하며 생각하는 것이 필요합니다. 비둘기 집의 원리를 적용해서 풀어야 하는 수학 문제를 하나 더 소개합니다.