d라이브러리

중·고교 교과 과정의 수학을 넘어서지 않는 수준에서 해결할 수 있는 재미있는 수학 연구 주제들을 소개하고 있습니다. 양팔 저울(천칭)을 사용해서 가짜 금화를 찾는 것은 매우 전통적인 수학 퀴즈입니다. 가짜가 진짜보다 더 가벼운지 혹은 더 무거운지를 모르는 상황에서는 문제 해결이 좀 어려운데, 이번 호에서는 이에 대해 차근차근 탐구하는 과제를 소개합니다.


가짜 금화가 진짜 금화보다 가볍다는 것을 알 때에는 문제 해결이 비교적 간단하다. 연습 삼아 그 문제를 먼저 정리해두고 진행하자.

물음

(1) 9개의 금화가 있는데 그중에 하나는 가짜이다. 가짜 금화는 진짜 금화보다 조금 가볍지만, 손으로 들어봐서는 잘 알 수 없는 정도이고 겉모습이 똑같아서 양팔 저울을 이용해야 한다. 양팔 저울을 2번 사용하여 가짜 금화를 찾아내어라.

(2) 금화가 9개가 아니라 10개였다면 양팔 저울을 2번만 사용해서 항상 가짜를 찾을 수 있는 방법은 없음을 보여라.


풀이

(1) 처음에 양쪽 접시에 금화를 3개씩 두고 잰다. 만일 기울어지면 가벼운 쪽의 3개 중에 가짜가 있고, 평형이면 저울질에 사용하지 않았던 3개 중에 가짜가 있다. 이제 저울질 1번으로 3개 중에서 가짜를 찾아내면 된다. 양쪽 접시에 1개씩 두고 재자. 만일 기울어지면 가벼운 쪽이 가짜이고, 평형이면 이 저울질에 사용하지 않고 남겨둔 것이 가짜이다.

(2) 금화를 어떻게 올려놓고 재도, 처음의 저울질에서 얻을 수 있는 상황은 ‘왼쪽이 무겁다(L)’,‘오른쪽이 무겁다(R)’,‘평형이다(E)’이 세 가지뿐이다. 이것을 저울의‘대답’이라고 부르자. 두번째 저울질에서도 마찬가지로 세 가지 대답을 얻는다. 그럼 두 번의 저울질로 얻을 수 있는 대답 열의종류는 LL, LE, LR, EL, EE, ER, RL, RE, RR의 3×3=9가지이다. 우리는 우리가 얻은 대답 열만을 바탕으로 어느 금화가 가짜였는지를 결정해야 하므로, 우리가 밝혀낼 수 있는 경우의 수는 대답 열의 종류의 수 9가지를 넘을 수 없다. 10개의 금화가 있다면 그중에 어느 것이 가짜이냐에 따라 10가지 경우가 존재하므로, 9가지의 대답 열로 이들을 모두 분별해낼 수는 없다.


위의 (2)와 같이,‘가려내야 할 경우의 수는 얻을 수 있는 대답 열의 수 이하가 되어야 한다’는 것을 이 과제 안에서는 스무고개 제한 원리라고 부르기로 하겠다. 이제부터는 가짜 금화가 진짜 금화보다 가벼운지 무거운지 모르는 상황에 대해 생각해보기로 하자. 진짜 금화는 한 가지 종류뿐이라서 모두 무게가 같은 것으로 하고, 저울질은 양팔 저울을 사용하는 것을 뜻하는 것으로 생각하자.


문제 1

4개의 금화가 있다. 그중 하나는 가짜로 나머지 금화들과 무게가 다르다. 두 번의 저울질로 가짜 금화를 찾아라.


이 문제를 풀어낸 사람들은 아마도 모두, 가짜 금화를 찾는 것까지는 성공했지만 그 가짜가 진짜보다가벼운지 무거운지까지 항상 밝혀낼 수 있는 방법을 찾은 것은 아닐 것이다. 이쯤에서 불가능성에 관한 다음의 질문들이 떠오를 만하다.


(A) 위의 문제에서, 두 번의 저울질로는 가짜가 진짜보다 가벼운지 무거운지까지 알아낼 수 있는 방법이 없을까?

(B) 5개의 금화가 있을 때에는 두 번의 저울질로 가짜 하나를 항상 찾아내는 것이 불가능할까?


이 질문들은 당장은 꽤 어려운 문제가 된다. 2번의 저울질로는 9가지 대답 열이 나오는데, 5개의 금화가 있다면 그중에 어느 것이 가짜냐에 따라 5가지 경우가 있을 뿐이므로, 스무고개 제한 원리로 불가능성을 말하기에는 한참 부족한 상황이다. 다음의 문제가 이 질문들에 대한 힌트가 되므로, 이것을먼저 이해하고 풀어보기 바란다.


문제 2

저울질을 끝냈을 때 어느 금화가 가짜인지를 알아냈다면, 대개는 그 금화가 가벼운 가짜인지 무거운 가짜인지까지 자동적으로 파악이 됨을 보여라. 여기서,‘대개는’이라고 표현한 정확한 이유를 말하여라.


즉,‘1번 금화가 가짜’라는 경우는‘1번 금화가 가벼운 가짜’라는 경우와‘1번 금화가 무거운 가짜’라는 경우로 대개 분리되어서 취급되어야 한다는 것이다. 그럼 5개의 금화에서 어느 것이 어떤 가짜냐에 따라 10가지 경우가 생겨서, 스무고개 제한 원리로 불가능성을 말할 수 있는 상황에 근접하게된다.‘대개는’에 해당하는 상황 때문에 실은 10가지보다 조금 줄어들지만, 첫 번째 저울질에서 양쪽 접시에 같은 개수씩을 올려놓지 않으면 의미를 갖지 못함을 잘 고려하여, 다시 10가지 이상으로 경우를 늘리는 설명을 찾을 수 있다. 그 설명은 여러분이 스스로 찾아내서 앞의 문제를 해결해내기 바란다.


문제 3

위의 두 가지 질문 (A)와 (B)가 각각 불가능함을 증명하여라.


이제 저울질의 횟수를 3번으로 늘려보자.


문제 4

12개의 금화 중에서 가짜 금화 하나를 세 번의 저울질로 찾아내고자 한다. 가짜 금화는 진짜보다 가벼울 수도 있고 무거울 수도 있다. 저울질이 끝나면 찾은 그 가짜가 가벼운 가짜인지 무거운 가짜인지도 말해야 한다.


(1) 첫 번째 저울질은 반드시 4개 : 4개로 비교하는 것이어야 함을 보여라.

(2) 목표를 이루는 세 번의 저울질 방법을 찾아라.


이와 같이 12개일 때는 3번이면 해결이 된다. 그럼 13개일 때는 3번으로 해결할 수 없을까? 이에 대한 답변은 미묘한 부분이 있다.


문제 5

(1) 금화가 13개일 때 세 번의 저울질로 가짜 하나를 찾아내는 방법을 구하여라.

(2) 위의 문제에서, 가짜를 찾을 수는 있지만 그 가짜가 가벼운 가짜인지 무거운 가짜인지까지 항상 3번의 저울질로 알아내는 방법은 없음을 보여라.

(3) 금화가 14개이면 세 번의 저울질로 가짜 하나를 항상 찾아내는 방법은 없음을 보여라.


다음과 같은 문제를 생각하면 상황은 더욱 미묘해진다.


문제 6

(1) 가짜가 하나 포함된 13개의 금화를 갖고 있고, 그 밖에 진짜임이 확실한 금화를 하나 더 갖고 있다. 3번의 저울질로 가짜를 찾고, 그것이 가벼운 가짜인지 무거운 가짜인지도 밝힐 수 있음을 보여라.

(2) 14개일 때 진짜 금화가 하나 더 있으면 3번의 저울질로 가짜를 찾을 수 있지만, 가벼운 가짜인지무거운 가짜인지까지 항상 밝힐 수 있는 방법은 없음을 보여라.


이제 일반화에 도전할 때가 되었다. 먼저 다음의 문제를 풀어두자.


문제 7

a+b개의 금화 중에 가짜가 하나 섞여 있다. a개는 가벼운 가짜일 가능성만 있는 금화이고, b개는 무거운 가짜일 가능성만 있는 금화이다. 그리고, 이들 외에 진짜임이 확실한 금화를 하나 갖고 있다. a+b≤3ⁿ이면 n번의 저울질로 가짜를 항상 찾아낼 수 있음을 보여라.


가벼운지 무거운지 모르는 가짜가 하나 포함된 n개의 금화가 주어졌을 때 m번의 저울질로 그 가짜를 찾아낼 수 있는 최대의 금화의 개수 n을 U_m으로 쓰기로 하자. 즉, U₂=4이고 U₃=13이다.


문제 8

(1) U_m을 구하고 그것을 증명하여라.

(2) 진짜임이 확실한 금화가 추가로 하나 있을 때 m번의 저울질로 가짜 하나를 찾아낼 수 있는 최대 금화의 개수를 V_m이라 하면 V_m=U_m+1임을 보여라.

(3) 찾은 가짜가 가벼운 가짜인지 무거운 가짜인지까지 알아내야 한다면, U_m과 V_m 둘 다 1씩 감소함을 보여라.