귀여운 촌아의 작은상자

먼저 7분짜리, 11분짜리 모래시계를 동시에 뒤집고 7분짜리가 다 내려가면 11분짜리 모래시계에는 4분의 모래만 남아있으므로

이 모래가 다 떨어진 후에 바로 11분짜리 모래시계를 다시 뒤집으면 15분을 측정할 수 있습니다.

4분짜리와 7분짜리를 동시에 뒤집고 4분짜리가 다 떨어졌을 때 7분짜리는 3분이 남게 됩니다.

이 때 4분짜리를 뒤집고 7분짜리의 3분이 다 떨어졌을 때 4분짜리에는 1분만 남게 됩니다.

이 때 7분짜리를 다시 뒤집고 4분짜리의 1분이 다 떨어진 후에는 7분짜리에 6분만 남게 됩니다.

이 때 4분짜리를 뒤집고 4분짜리가 다 떨어지면 7분짜리에는 2분이 남게 됩니다.

이때부터 시간을 측정하며 7분짜리의 2분이 다 떨어진 후에 한 쪽으로 모두 떨어진 7분짜리 모래시계를 뒤집어서 7분을 모두 측정하면 9분을 잴 수 있습니다.

5분짜리와 7분짜리를 동시에 뒤집고 5분짜리가 모두 떨어진 후에 7분짜리에는 2분만 남게 됩니다.

이때 모두 떨어진 5분짜리를 뒤집고 2분만 남은 7분짜리가 모두 떨어지면 5분짜리에는 3분만 남게 됩니다.

이 때 7분짜리를 다시 뒤집고 3분만 남은 5분짜리가 모두 떨어진 후에 7분짜리에는 4분만 남게 됩니다.

이제 모두 떨어진 5분짜리 뒤집어서 4분만 남은 7분짜리가 모두 떨어졌을 때 5분짜리에는 1분만 남게 됩니다.

이제부터 시간을 측정하며 1분만 남은 5분짜리를 뒤집어서 남은 1분이 모두 떨어지면 한 쪽으로 모두 떨어진 5분짜리 모래시계를 뒤집습니다.

5분짜리가 모두 떨어지면 6분을 잴 수 있게 됩니다.

(이 문제는 처음부터 시간을 측정합니다.)

5분짜리와 7분짜리를 동시에 뒤집고 5분짜리가 모두 떨어진 후에 7분짜리에는 2분만 남게 되고, 다 떨어진 5분짜리는 바로 다시 뒤집습니다.

(5분짜리는 중간에 뒤집기 않고 한 쪽으로 모두 떨어졌으므로 지금까지 총 5분이 지났습니다.)

2분만 남은 7분짜리가 모두 떨어지면 5분짜리는 3분만 남게 되며 다 떨어진 7분짜리는 다 떨어지자마자 다시 뒤집습니다.

(7분짜리는 중간에 뒤집지 않고 한 쪽으로 모두 떨어졌으므로 지금까지 총 7분이 지났습니다.)

3분만 남은 5분짜리가 다 떨어지면 7분짜리는 4분만 남게 되며 5분짜리는 다 떨어지자마자 다시 뒤집습니다.

(7분짜리가 모두 떨어진 후 3분만 남은 5분짜리를 뒤집어서 다 떨어졌으므로 지금까지 총 10분 지났습니다.)

4분만 남은 7분짜리가 다 떨어지면 5분짜리는 1분만 남게 됩니다.

(4분만 남은 7분짜리가 모두 떨어졌으므로 지금까지 총 14분이 지났습니다.)

이때 한쪽으로 모두 떨어진 7분짜리를 뒤집고

1분 후에 5분짜리가 모두 떨어지면 7분짜리는 1분만 떨어졌으므로 7분짜리를 다시 뒤집어서 1분을 측정하면 16분을 측정할 수 있습니다.

9L짜리의 물통에 물을 가득 채운 후 4L에 가득 붓습니다. 9L짜리에는 5L만 남아있게 되고, 4L짜리의 물통을 모두 비운 후 5L만 들어있는 9L짜리의 물을 4L짜리의 물통에 가득 붓습니다. 이제 9L짜리의 물통에는 1L만 남게 되고, 4L짜리의 물통을 비운 후 1L만 들어있는 9L짜리의 물을 4L에 붓습니다. 따라서 4L짜리의 물통에는 3L가 비어있고 마지막으로 9L짜리의 물통에 물을 가득 채운 후 3L만 비어있는 4L짜리 물통에 3L를 부으면 6L를 측정할 수 있습니다.

먼저 6L짜리에 물을 가득 담은 후 11L에 붓습니다. 이 때 11L짜리에는 6L만큼 물이 차있고 5L만큼 비어있게 됩니다. 6L짜리에 다시 물을 가득 채운 후 5L만큼 비어있는 11L에 가득 붓습니다. 이 때 6L짜리에는 1L만 남아 있게 되고 11L에 가득 차 있는 물은 모두 비웁니다. 1L만 들어있는 6L짜리의 물을 11L짜리에 붓습니다. 따라서 11L짜리에는 1L만 들어있고 10L가 남아 있게 됩니다. 다시 6L에 물을 가득 채운 후 1L만 들어있는 11L에 모두 붓습니다. 이 때 11L에는 7L만 들어있고 4L가 남아있게 됩니다. 마지막으로 이 4L만 들어있는 11L의 물을 비어진 6L에 붓고 11L에 물을 가득 채운 후 2L만 남은 6L짜리 물통에 부으면 11L에는 9L만 남게 됩니다.

3L에 물을 가득 채운 후 5L에 붓습니다. 5L에는 3L를 채웠으므로 2L만큼 비어 있고, 여기에 다시 3L에 가득 채운 물을 5L에 가득 차도록 붓습니다. 5L에는 2L만큼 비어 있으므로 3L짜리에는 1L만 남게 됩니다. 5L짜리를 모두 비운 다음 3L짜리의 1L를 5L에 부은 다음 3L에 물을 다시 가득 채워 1L만 들어있는 5L짜리에 모두 부으면 4L만 들어있게 됩니다.

가득 채운 5L짜리 물통의 물을 4L짜리 물통에 가득 붓습니다. 5L짜리에는 1L만 남게 되고 가득 찬 4L짜리의 물통은 비운 후 1L만 남은 5L짜리의 물을 다시 4L짜리의 물통에 붓습니다. 따라서 4L짜리의 물통에는 3L만 남게 되며 5L짜리의 물통을 가득 채운 후 3L가 남은 4L짜리의 물통에 가득 부으면 5L짜리의 물통에는 2L만 남게 됩니다. 마지막으로 4L짜리의 물통을 가득 채운 후 2L만 남은 5L짜리에 부으면 2L를 측정할 수 있습니다.

4L짜리의 물통에 물을 가득 담고 비어있는 3L짜리에 부으면 4L에는 1L만 남게 됩니다. 다시 3L짜리의 물통을 비운 후 1L만 남은 4L짜리의 물통의 물을 3L짜리에 옮겨 담습니다. 따라서 3L짜리의 물통에는 1L만 옮겨 담았으므로 2L만 비어있게 된다. 마지막으로 4L짜리의 물통을 가득 채운 후 2L가 비어있는 3L짜리에 가득 부으면 2L를 측정할 수 있다.

8L짜리의 물을 5L짜리의 물통에 가득 부은 후 가득 찬 5L짜리의 물을 3L짜리의 물통에 가득 붓습니다. 즉, 8L짜리의 물통에는 3L의 물이 남아 있고 5L짜리의 물통에는 2L의 물이, 3L짜리의 물통에는 L가 가득 차 있게 됩니다. 이 때 3L짜리의 물을 8L짜리의 물통에 모두 붓고 5L짜리 물통에 있는 2L의 물을 3L짜리의 물통에 옮겨 붓습니다. 이제 8L짜리의 물통에 있는 6L의 물을 5L짜리의 물통에 가득 붓습니다. 즉, 8L짜리의 물통에는 1L의 물이, 5L짜리의 물통에는 5L의 물이, 3L짜리에는 2L의 물이 있게 되며 마지막으로 5L짜리의 물통의 물을 1L의 공간이 남아있는 3L짜리의 물통에 옮겨 부으면 4L를 측정할 수 있습니다.

7L짜리의 물통에 들어있는 물을 4L짜리의 물통에 가득 붓고, 가득 찬 4L짜리의 물은 3L짜리의 물통에 가득 붓습니다. 그러면 7L짜리의 물통에는 3L만큼의 물이 남아있고 4L짜리의 물통에는 1L의 물만, 3L짜리의 물통에는 3L만큼의 물이 차 있게 됩니다. 이제 3L짜리의 물통의 물은 7L짜리의 물통에 모두 옮겨 담고 4L짜리 물통의 1L는 3L짜리의 물통에 옮겨 담습니다. 즉, 7L짜리의 물통에는 6L의 물이 들어있고 4L짜리의 물통은 비어있으며 3L짜리의 물통에는 1L만 남아있게 됩니다. 이제 7L짜리 물통의 물을 4L짜리에 가득 붓고 가득 찬 4L짜리의 물은 2L만큼 비어 있는 3L짜리의 물통에 부으면 2L, 2L, 3L로 나눌 수 있습니다.

양팔 저울 문제에서 양팔 저울을 한 번 사용하여 무게가 무거운(또는 가벼운) 하나를 알아내는 최대의 동전 개수는 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개를 저울로 측정하면 무게가 가벼운 것을 알아낼 수 있습니다.

남아 있는 다른 한 문으로 바꿔야 한다.

가장 먼저 선택한 문을 계속 고수하고 바꾸지 않는다면 염소가 있는 문을 열든 열지 않든 차를 선택할 확률은 1/3 입니다.

그렇다면 염소가 있는 문이 공개된 후 문을 바꾸는 선택을 했을 때의 경우의 수만 따져보겠습니다.

마지막 최종 선택을 보면 다른 문이 공개된 후에 선택을 바꾸었을 때 차를 선택할 확률이 2/3으로 증가하게 된다.

즉, 염소가 공개된 후에 선택을 바꾸는 것이 유리하다.