가짜 동전 찾기
저울질 두 번으로 가짜를 잡습니다
모양과 크기가 똑같은 동전 9개 중에 가짜 동전이 하나 섞여 있습니다. 가짜는 진짜보다 약간 가볍습니다.
양팔저울을 단 두 번만 써서 가짜 동전을 확실하게 찾아낼 수 있을까요? 반으로 나누지 않고 세 무더기로 나누는 순간 어떤 놀라운 일이 벌어질까요?
이야기
1945년 케임브리지의 학생 잡지 『유레카』에 열두 개짜리 판이 실리면서 이 문제가 퍼졌습니다. 전쟁 중이었습니다. 사람들이 하도 여기에 매달리는 것을 보고 「이걸 독일에 뿌려서 저쪽 연구를 멈추게 하자」는 농담이 돌았다고 전해집니다.
그런데 이 문제가 사람을 사로잡는 까닭은 답이 어려워서가 아닙니다. 누구나 반으로 나누는 것부터 떠올리는데, 그것이 함정이기 때문입니다. 반으로 나누면 아홉 개를 찾는 데 네 번이 걸립니다.
양팔저울은 기운다·기운다·같다 세 가지를 말해 줍니다. 두 가지가 아니라 세 가지입니다. 그러니 나눌 때도 셋으로 나눠야 저울이 가진 말을 다 쓰는 것입니다.
그래서 한 번에 아홉이 셋으로, 두 번에 셋이 하나로 줄어듭니다. 3의 거듭제곱만큼씩 줄기 때문에, 두 번이면 아홉까지, 세 번이면 스물일곱까지 찾을 수 있습니다.
가장 적게 물어 답을 찾는 법입니다. 한 번 재면 셋 중 하나로 갈리니, n번이면 3의 n제곱까지 가릅니다.
불량품 검사, 병 감염자 찾기(여럿을 섞어 한 번에 검사), 데이터에서 원인을 좁혀 가는 방법이 모두 같은 셈입니다.
계단 넷 — 같은 사실을 네 깊이로
동전 아홉 개로 두 번 만에 찾기
바둑돌 9개를 3개, 3개, 3개 세 무더기로 나눕니다. 첫 번째 저울질에서 3개씩을 양쪽에 올립니다.
저울이 기울면 가벼운 쪽에, 수평을 이루면 저울에 안 올린 나머지 3개 속에 가짜가 있습니다. 남은 3개 중 1개씩을 올려 두 번째 저울질을 하면 단 두 번 만에 가짜가 바로 밝혀집니다.
몇 번 재면 찾을까요
그래서 3의 거듭제곱만큼 줄어듭니다 — 9 개면 두 번.
세 갈래로 나누는 생각
보통 절반으로 나누는 이진 탐색을 떠올리기 쉽지만, 양팔저울은 왼쪽이 무겁다, 오른쪽이 무겁다, 수평이다의 세 가지 결과(3진법)를 제공합니다.
따라서 대상을 3등분할 때 저울질 1번으로 후보의 수를 로 줄일 수 있습니다. 저울질 번으로 판별할 수 있는 최대 동전의 개수는 개이므로, 9개는 에서 정확히 2번으로 충분합니다.
세 갈래의 힘
「같다」도 정보입니다 — 저울에 안 올린 동전이 답일 수 있으니까요.
정보량으로 최소 횟수 구하기
정보 이론의 관점에서 개의 동전 중 하나를 특정하는 데 필요한 정보량(엔트로피)은 비트입니다. 3가지 결과를 내는 저울질 1회가 줄 수 있는 최대 정보량은 비트입니다.
따라서 최소 저울질 횟수 는 을 만족해야 합니다. 일 때 가 되어 2회가 수학적 절대 최소치임이 증명됩니다.
무거운지 가벼운지도 모른다면
12 개는 딱 세 번 — 3³ = 27 > 24 이기 때문입니다.
정보 이론
가짜 동전 문제는 정보 이론(Information Theory)의 최적 부호화(Huffman Coding) 및 결함 진단(Group Testing) 이론으로 발전했습니다.
가짜 동전이 무거운지 가벼운지 모르는 일반화된 문제, 가짜 동전이 여러 개 섞여 있는 다중 결함 검출 문제는 제2차 세계대전 당시 군인 혈액 검사 최적화(Dorfman Pooling)에 쓰였으며, 오늘날 대규모 감염병 PCR 취합 검사 및 데이터 압축 알고리즘의 뼈대가 됩니다.
정보로 재 보세요
「몇 번 재야 하나」는 곧 「정보가 얼마나 필요한가」 입니다.
풀어 보기
양팔저울과 가짜 동전 찾기. 겉모양이 같은 동전들 중 가벼운 가짜 동전 1개가 섞여 있다.
(1) 동전 9개에서 양팔저울을 2번 사용하여 가짜 동전을 찾는 구체적 알고리즘을 설명하시오.
(2) 양팔저울을 번 사용하여 가짜 동전 1개를 항상 찾아낼 수 있는 동전의 최대 개수를 에 대한 거듭제곱 식으로 나타내시오.
(3) 동전 27개와 81개가 있을 때, 가짜 동전 1개를 찾는 데 필요한 최소 저울질 횟수를 각각 구하시오.
(3) 27 = 3³ 이므로 3회, 81 = 3⁴ 이므로 4회가 됩니다.
답과 풀이 보기
(1) 아홉 개를 세 개씩 세 무더기로 나눕니다.
① 두 무더기를 저울에 올립니다. 기울면 가벼운 쪽에, 평형이면 안 올린 무더기에 가짜가 있습니다. → 후보가 아홉에서 셋으로 줄었습니다.
② 그 셋 중 두 개를 올립니다. 같은 방법으로 하나가 남습니다.
→ 두 번이면 끝납니다.
(2) 저울의 결과는 왼쪽·오른쪽·평형 셋입니다. 한 번 잴 때마다 후보가 로 줄어드므로
개까지 번이면 찾습니다.
(3) → 3 회, → 4 회
하나씩 견주면 여든 번이 걸리는 일을 네 번에 끝냅니다. 저울이 세 가지를 알려 준다는 것을 알아차리는 것이 전부입니다.
더 멀리
「한 번의 물음으로 얼마나 줄일 수 있나」는 정보의 문제입니다.
- 스무고개 — 예·아니오 둘뿐이니 한 번에 절반씩 줄입니다
- 이진 탐색 — 컴퓨터가 정렬된 자료에서 값을 찾는 방식입니다
- 더 어려운 판 — 가짜가 무거운지 가벼운지 모를 때는 열두 개를 세 번에 찾을 수 있습니다
이어지는 장
양팔저울의 세 가지 상태를 이용하여 3진법 트리 탐색으로 가짜 동전을 좁혀가는 전략은, 열 개의 손가락을 펴고 접는 2진법 비트 조합으로 1023까지 빠르게 수를 세어내는 정보 표현의 원리와 상통합니다 — 제26장에서 진법 체계가 선사하는 셈의 마법을 체험해 보세요.
영감을 받은 곳
1945년 E. D. 셸이 『아메리칸 매스매티컬 먼슬리』에 게재한 수학 퍼즐 문제와, 클로드 섀넌이 1948년 정립한 정보이론의 정보 엔트로피 및 삼진 분기 탐색 원리에서 발전했습니다.