d라이브러리

Q

수백 개의 금화가 가득 든 11개의 자루가 있다. 이 가운데 2자루에는 11g짜리 진짜 금화가, 나머지 9자루에는 진짜 금화를 복제한 10g짜리 가짜 금화가 들어있다. 접시저울을 단 한 번만 써서 진짜 금화가 든 자루를 찾으려면 어떻게 해야 할까?

A

이 문제는 너무나 유명해서 퍼즐을 좋아하는 사람이라면 누구나 한 번쯤은 들어본 적이 있을 것이다. 1960년대에 나온 것으로 추정되는 원작은 보통 10개의 주머니 가운데 하나만 가짜인 형태로 알려져 있는데, 줄기세포 논문 조작 사건을 계기로 필자가 문제를 약간 바꿨다.

원래 문제는 1970년대의 유명한 외화인 ‘형사 콜롬보’를 통해 널리 알려졌다. ‘차이코프스키 교향곡’(원제는 ‘The Bye-Bye Sky High IQ Murder Case’)이라는 에피소드에서 범인은 자신을 귀찮게 쫓아다니는 콜롬보에게 다음과 같은 문제를 풀어보라고 한다. “똑같은 모양의 10g짜리 보석들이 들어있는 10개의 주머니 가운데 단 하나만 9g짜리 가짜들로 채워져 있다. 접시저울을 한 번만 써서 가짜 보석이 든 주머니를 찾아라.”

에피소드의 원제에서 알 수 있듯이 사건은 천재들의 모임에서 일어났고, 범인 역시 천재로 설정돼 있다. 이런 천재에게 콜롬보는 무척 어수룩하게 보였을 듯. 그렇지만 결국 우여곡절 끝에 범인은 콜롬보에게 체포되고 마는데, 현장을 떠나던 콜롬보가 깜빡 잊었다며 범인에게 한 마디 던진다.

“그때 말씀하셨던 문제 말입니다. 정말 어렵더군요. 이런 문제를 만드는 분에게 두 손 두 발 다 들었습니다. 제 아내와 함께 풀어봤는데, 이러면 어떨까요? 주머니에 차례대로 번호를 붙입니다. 그러고 나서 1번 주머니에서 보석 1개를 꺼내고, 2번 주머니에서 보석 2개를 꺼내고, 이런 식으로 모든 주머니에서 번호만큼 보석을 꺼내서 한꺼번에 저울에 달아봅니다. 모두 진짜일 때와 비교해서 얼마나 가벼운지를 알면, 가짜 보석이 든 주머니를 알 수 있지 않을까요?”

모두가 진짜일 때의 무게는 450g이어야 하는데, 만약 446g이 나왔다면 4개가 가짜니까 4번 주머니가 가짜라는 것을 알 수 있다.

필자가 초등학생일 때 방학 과제인 탐구생활에 이 문제가 실린 적이 있다. 초등학생 주제에(?) 형사 콜롬보의 열렬한 시청자이다 보니 문제를 보자마자 답을 알았는데, 방학이 끝나고 보니 나 혼자 정답을 적었다.

원래 문제처럼 2개 이상의 대상을 찾아야 하는 경우에는 이진법을 쓰는 것이 간단하다. 우선 번호 순서대로 0, 1, 2, 4, 8, 16, …, 512개를 꺼낸다. 모두가 가짜라면 10240g이 나와야 한다. 만약 10243g이 나왔다면 모두가 가짜일 때에 비해 3g이 남는 것이고, 3=1+2이므로 2번과 3번 자루가 ‘가짜’라는 것을 알 수 있다. 요즘 상황을 보면 이 2개마저 의심스러워지기는 하지만 말이다.