귀여운 촌아의 작은상자

양팔 저울 문제에서 양팔 저울을 한 번 사용하여 무게가 무거운(또는 가벼운) 하나를 알아내는 최대의 동전 개수는 3개입니다. 동전 3개 중 두 개를 무작위로 선택하여 저울을 한번 사용하면 같거나 어느 한 쪽으로 기운 경우가 나오므로 동전 3개가 있을 때 저울 한 번을 사용하여 알아낼 수 있습니다. 즉, 위와 같이 9개의 동전을 3개씩 3그룹으로 묶어서 위의 설명과 같이 한 번 측정하여 무거운 동전이 있는 그룹을 알아냅니다. 무거운 동전이 포함된 그룹을 알아냈으므로 그 그룹의 3개 동전을 두 번째 측정을 통해 알아낼 수 있습니다.

따라서 위와 같이 동전의 무게가 다른 하나가 무거운지 또는 가벼운지 알고 있고, 주어진 저울질의 횟수 n일 때 알아낼 수 있는 동전의 최대 개수는 3의 n제곱이 됩니다.

이 저울 문제의 어려운 버전으로 무게가 다른 구슬(또는 동전, 공 등)이 하나 있고, 이 구슬의 무게가 무거운지 가벼운지 모르는 문제입니다. 이 문제의 쉬운 버전은 구슬이 3개이고 저울을 사용할 수 있는 횟수는 2번이고 이 문제의 어려운 버전은 구슬의 개수는 39개이고 저울의 사용 횟수는 4번입니다.

이 문제의 해법은 한 가지 이상인데 먼저 영문 위키에 있는 풀이와 다른 것을 올리겠습니다.

먼저 구슬을 4개씩 3개의 그룹으로 묶고 이 중 두 그룹을 측정합니다.

이 때 나올 수 있는 결과는 측정한 두 그룹이 같거나 한 쪽으로 기울어 진 경우가 있습니다.

구슬 4개짜리 그룹이 같을 때 측정하지 않은 나머지 그룹에 무게가 다른 구슬이 있게 되고, 측정한 두 그룹은 모두 무게가 같은 8개의 구슬입니다. 그 다음 무게가 다른 구슬이 포함된 4개의 구슬을 2개씩 2그룹으로 나눕니다. 그 다음 무게가 모두 같은 구슬 8개 중 2개를 그룹지어 무게가 다른 구슬이 포함된 구슬 2개짜리 그룹과 무게를 측정합니다.

2번 째 무게 측정 후 나올 수 있는 경우는 구슬 2개짜리 그룹의 무게가 같거나 한 쪽이 더 무겁거나 가벼운 경우인데, 어떠한 경우가 나오든 무게가 다른 구슬 2개짜리 그룹 하나를 선별할 수 있습니다. 이제 무게가 모두 같은 구슬 하나를 이용하여 남은 구슬 2개 중 1개를 골라 측정하여 무게가 다른 하나를 알아낼 수 있습니다.

만약 처음의 측정에서 한 쪽으로 기울어진 경우 측정한 구슬 4개짜리 그룹 2개 중 하나의 그룹에 더 무거운 구슬이 포함되어 있거나 같이 측정한 다른 그룹에 가벼운 구슬이 포함된 경우입니다. 이렇게 한 쪽으로 기울어졌을 때 무겁게 측정된 구슬 4개짜리 그룹에서 구슬 2개와 가볍게 측정된 구슬 4개짜리 그룹의 구슬 1개를 묶어 구슬 3개짜리 그룹 하나를 만들고, 무겁게 측정된 구슬 1개와 가볍게 측정된 구슬 1개, 무게가 같은 구슬 1개를 묶어 하나의 그룹을 만듭니다. 정리하면 (무겁게 측정된 구슬 2개 + 가볍게 측정된 구슬 1개)와 (무겁게 측정된 구슬 1개 + 가볍게 측정된 구슬 1개 + 무게가 같은 구슬 1개) 그리고 (무겁게 측정된 구슬 1개 + 가볍게 측정된 구슬 2개 + 무게가 같은 구슬 3개)로 그룹을 만들어 줍니다. 그 다음 (무겁게 측정된 구슬 2개 + 가볍게 측정된 구슬 1개)와 (무겁게 측정된 구슬 1개 + 가볍게 측정된 구슬 1개 + 무게가 같은 구슬 1개)를 저울로 무게를 비교 합니다.

만약 두 그룹의 무게가 같다면 무게를 측정하지 않은 (무겁게 측정된 구슬 1개 + 가볍게 측정된 구슬 2개 + 무게가 같은 구슬 3개) 그룹 중 (무겁게 측정된 구슬 1개 + 가볍게 측정된 구슬 2개)에 무게가 다른 구슬이 있게 됩니다. 마지막으로 가볍게 측정된 구슬 2개를 서로 무게를 측정하여 서로 같다면 무겁게 측정된 구슬 1개가 무거운 구슬이 되며 어느 한 쪽이 기운다면 가볍게 측정된 구슬 2개를 서로 측정했으므로 가벼운 구슬 1개를 알아낼 수 있습니다.

만약 두 그룹의 무게를 측정했는데 (무겁게 측정된 구슬 2개 + 가볍게 측정된 구슬 1개) 그룹이 더 무겁게 측정되었다면 무겁게 측정된 구슬 2개 중에 무게가 무거운 구슬 1개가 있거나 반대편 그룹 (무겁게 측정된 구슬 1개 + 가볍게 측정된 구슬 1개 + 무게가 같은 구슬 1개)의 가볍게 측정된 구슬 1개가 가벼운 구슬일 경우입니다. 따라서 무겁게 측정된 구슬 2개를 마지막으로 서로 측정하여 같다면 가볍게 측정된 구슬 1개가 가벼운 구슬이고, 어느 한 쪽이 기운다면 무겁게 측정된 구슬 2개를 서로 측정했으므로 무거운 구슬을 알아낼 수 있습니다.

만약 두 그룹의 무게를 측정했는데 (무겁게 측정된 구슬 1개 + 가볍게 측정된 구슬 1개 + 무게가 같은 구슬 1개) 그룹이 더 무겁게 측정되었다면 (무겁게 측정된 구슬 1개 + 가볍게 측정된 구슬 1개 + 무게가 같은 구슬 1개) 그룹의 무겁게 측정된 구슬 1개가 무거운 구슬이거나 반대편의 (무겁게 측정된 구슬 2개 + 가볍게 측정된 구슬 1개) 그룹에 가볍게 측정된 구슬 1개가 가벼운 구슬인 경우입니다. 따라서 무겁게 측정된 구슬 1개와 가볍게 측정된 구슬 1개를 무게가 같은 구슬 1개와 비교하여 무게가 다른 구슬을 알아낼 수 있습니다.

위 문제에서는 두 번째 저울 사용이 중요합니다. 영문 위키에 나와 있는 문제의 해법은 첫 번째 저울 사용까지는 위와 같고 두 번째 저울을 사용할 때 다음과 같이 그룹을 구성하는 것입니다. (가볍게 측정된 것 3개 + 무겁게 측정된 것 1개)와 (무게가 같게 측정된 것 3개 + 가볍게 측정된 것 1개) 따라서 남게 되는 것들은 (무겁게 측정된 것 3개 + 무게가 같은 1개)입니다.

이 때 (가볍게 측정된 것 3개 + 무겁게 측정된 것 1개)와 (무게가 같은 3개 + 가볍게 측정된 것 1개)을 서로 저울로 무게를 비교 합니다.

무게를 비교 했을 때 (가볍게 측정된 것 3개 + 무겁게 측정된 것 1개)와 (무게가 같은 3개 + 가볍게 측정된 것 1개)가 같게 측정된다면 남아있는 (무겁게 측정된 것 3개 + 무게가 같은 1개)의 무겁게 측정된 것 3개 중 하나에 무거운 것이 있게 되므로 이 3개를 저울질하면 됩니다.

만약 (가볍게 측정된 것 3개 + 무겁게 측정된 것 1개)가 더 무겁게 측정되었다면 무겁게 측정된 것 1개와 저울 반대편의 가볍게 측정된 것 1개 중 무게가 다른 것이 있게 되므로 무게가 같은 것 1개와 비교하면 알아낼 수 있습니다.

반대로 (가볍게 측정된 것 3개 + 무겁게 측정된 것 1개)가 더 가볍게 측정되었다면 저울 반대편에는 가볍게 측정된 것이 없으므로 가볍게 측정된 것 3개 중에 가벼운 것이 있는 것이므로 이 3개 중 2개를 저울로 측정하면 무게가 가벼운 것을 알아낼 수 있습니다.