쥐약 문제 - 김전일은 풀 수 있을까?

[책을 읽고] 장톈룽, <확률로 바라본 수학적 일상> (3)

김전일의 동전 문제

<소년 탐정 김전일>에는 이런 문제가 나온다.

10개의 금화 주머니가 있는데, 1개의 금화 주머니에만 11그램짜리 금화들이 들어 있고, 나머니 주머니는 모두 10그램짜리 금화들이 들어 있다. 저울을 몇 번 쓰면 11그램짜리 금화 주머니를 찾아낼 수 있을까?

정답은 한 번이다.

열 개의 금화 주머니에 일련 번호를 매긴다. 1번 주머니에서 1개, 2번 주머니에서는 2개, 이런 식으로 10개의 주머니에서 총 55개의 금화를 저울에 올린다. 모두 10그램이라면 550그램이지만, 11그램짜리 금화 때문에 오차가 생길 것이다. 그 오차 만큼 11그램짜리 금화가 저울에 올라온 것이므로, 그 오차에 해당하는 번호의 주머니에 11그램짜리 금화들이 들어 있다.

이 책에서 쥐와 독약 문제를 만났을 때, 나는 김전일의 이 문제를 떠올렸다.

쥐와 독약 문제

쥐 7마리와 약병 100개가 있다. 약병 1개에만 독약이 들어 있고, 독약을 먹은 쥐는 정확히 24시간, 즉 1일 후에 죽는다. 당신에게 24시간이 주어진다면, 어떻게 독약이 들어 있는 병을 찾아낼 수 있는가?

보통의 교육을 받은 사람이라면, 앞의 김전일 문제와 마찬가지로 여기에서도 실험군과 대조군을 대비하는 방법을 생각할 것이다. (당연한 것이지, 부끄러워 할 일이 아니다.)

7*14=98이므로, 쥐 일곱 마리는 각각 14병의 약병을 시험해 볼 수 있다. 즉, 각 쥐에게 14병의 약병을 먹이고, 죽은 쥐가 먹은 약병을 다시 남은 쥐들에게 먹이는 식으로 하면 3일만에 알아낼 수 있다. (처음에 아무 쥐도 안 죽는다면 2병 중에 하나가 되므로 이틀만에 가능하고, 독약 먹고 죽은 쥐 때문에 이틀째에는 6마리, 3일째에는 5마리로 실험을 해야 하지만 충분하다.)

그러나 시간은 딱 하루, 즉 24시간이 주어져 있고, 독약의 효능이 딱 한 번밖에 발휘될 수 없는 시간이다.

이 시점에서 나는 문제를 다시 읽어보았고, 예컨대 '죽을 수 있다'라는 표현에 주목하며 이게 혹시 넌센스 퀴즈인가 하는 생각도 했다. (만약 그랬다면 상당히 열 받았을 것이다. 나는 문제가 나온 시점에서 책을 덮고 생각을 하고 있었다.)

운동 시간이 끝났기 때문에, 나는 문제 풀기를 포기하고 해답을 읽었다. 이런 신박한 방법이 있다니!

얘가 대체 뭔 잘못을 했다고

해답

약병의 일련 번호를 2진수로 바꾼다. 2^7=128이므로, 모든 약병이 7자리 이내의 일련 번호로 표시된다.

1번 쥐에게는 첫째 자리가 1인 약병을 모두, 2번 쥐에게는 둘째 자리가 1인 약병을 모두, 이런 식으로 7개의 약병을 모든 쥐에게 먹인다.

죽은 쥐에 해당하는 자리는 1, 그렇지 않는 자리는 0인 2진수가 완성된다. 이 번호가 독약병이다.

응용 문제

앞의 문제와 마찬가지로, 약병 100개 중 1개가 독약병이다. 다만, 이번에는 이틀의 시간이 주어졌다. 즉, 두 번 실험이 가능하다. 총 몇 마리의 쥐가 필요한가?

앞 문제의 해결 방법을 알았으므로, 몇 마리의 쥐가 필요한지는 쉽게 알아낼 수 있다. 3^4=81, 3^5=243이므로, 5마리면 충분하다.

실험은 어떻게 진행해야 할까?

첫째 날에는 3진수의 해당 자리수가 2인 약병을 담당 쥐에게 먹인다. 예컨대 (십진수) 8번 병이라면 3진수로 00022이므로, 4번 쥐와 5번 쥐에게 이 약병을 먹이고, 나머지에게는 안 먹인다.

하루가 지나면 해당 자리의 3진수가 2인 자리가 확인된다. 이제 남은 쥐들에게 해당 자리수가 1인 약병을 먹인다. 이 방식으로 해당 자리수가 1인 자리가 확인된다. 나머지 자리는 물론 0이다.

이 방법이 직관적으로 보이지는 않는다. 우리는 10진수를 쓰기 때문이다.

그렇다면 10진수를 써서, 9일에 걸쳐 알아내는 방법을 생각해 보자.

100만 개의 약병이 있고, 이중 딱 한 개만 독약병이다. 100만=10^10이므로, 쥐는 열마리다.

첫째 날에는 9를 테스트한다. (다른 어떤 수라도 상관없다.) 자기 자리 수가 9인 약병을 모든 쥐가 먹는다. 하루가 지나면 어느 자리가 9인지 확인된다.

같은 방식으로, 둘째 날에는 8, 셋째 날에는 7, 이런 식으로 9일에 걸쳐 0을 제외한 모든 10진수의 자리가 확인되고, 남는 자리는 0이다.

정보 엔트로피

이 문제는 정보 엔트로피를 다루는 제5부에 나온다.

약병의 액체를 먹고 하루가 지난 쥐에게서 우리가 얻을 수 있는 정보량은 1비트다. 살았거나, 죽었거나.

쥐가 모두 7마리이므로, 얻을 수 있는 정보량은 7비트다.

두 번째 문제의 경우, 쥐 한 마리의 상태가 이틀에 걸쳐 분포하는 방식은 생생, 생사, 사생, 사사다.

그러나 사생은 실제로 가능하지 않으므로, 쥐가 제공할 수 있는 정보는 3가지 중에 하나다.

삼진법에는 비트에 해당하는 말이 없으므로, 이들 트리트(trit)라고 하자.

쥐 5마리는 5트리트, 즉 3^5=243가지 경우의 수를 나타낼 수 있다.

128이든, 243이든 100보다 크다. (훨씬 크다.)

우리가 64 또는 128개의 약병 중에 하나를 찾아야 하는 상황이라면 훨씬 깔끔했을 것이다.

이는 단지 기분 문제에 그치지 않고, 비용 문제를 불러온다.

약병이 64개라면 쥐가 6마리 필요하지만, 65개라면 쥐가 7마리 필요하다.

그래서 저자는 이 상황을 '소 잡는 칼'로 닭을 잡는 상황이라 비유한다.

그러나 이는 알고리즘에 의해 문제를 해결하려고 하는 경우 피할 수 없는 문제다.

인간이 하면 간단한 일이라도, 우리는 로봇(인공지능)에게 시키고 싶다.

그러려면 소 잡는 칼로 닭 잡을 각오를 해야 한다.

닭 잡는 칼의 예시

***계속***