[6월의 퍼즐 해설] 개미의 퇴근길

이 문제는 시작점이 아니라 도착점 근처부터 보면 풀기 쉽다. 집에 도착하려면 11 위에 올라가야 하는데, 문제는 10에서 출발해도 세갈래길 중 11이 가장 높고, 1에서 출발해도 세갈래길 중 11이 가장 높아서 절대 11에 올라갈 수가 없다는 점이다. 이 문제를 해결하려면 두 가지 방법이 있다. 하나는 그 세갈래길 중 하나에 12를 올려놓아 11이 선택지 중 가장 낮은 흙더미가 되도록 하는 것이고, 하나는 11 자체를 다른 수로 교체하는 것이다.

세갈래길 중 하나에 12를 올려놓아 11이 선택지 중 가장 낮은 흙더미가 되도록 한다는 것은, 다음 세 수 중 하나를 택해서 12와 위치를 바꾼다는 뜻이다. 그래야 개미가 12와 11을 비교해서 11로 가게 될 것이기 때문이다.

그렇다면 실제로 세 가지 가능성을 모두 확인해 보자.

꿀→5→2→7→3→5→2→7→3→… 무한루프에 빠진다.

꿀→5→2→7→4→8→6→5→2→7→4→8→6→… 무한루프에 빠진다.

꿀→5→2→7→4→5→2→7→4→… 무한루프에 빠진다.

12를 이용해서 개미를 11로 유도할 수는 없다는 것을 알았다. 그렇다면 11을 아예 다른 수로 교체해야만 한다. 11과 높이를 비교하게 되는 수는 3, 6, 4다. 따라서 11 자리에 오는 수가 6보다 큰 수라면 여전히 11이 세갈래길 중 가장 높아서 개미가 집을 찾아갈 수 없게 될 것이므로, 1, 2, 3, 4, 5, 6 중 하나를 가져와서 11 자리에 놓아야 한다.

11과 1을 바꾸면,

꿀→5→2→7→4→8→12→5→2→7→4→8→12→… 무한루프에 빠진다.

11과 2를 바꾸면,

꿀→5→11→7→4→8→12→5→11→7→4→8→12→… 무한루프에 빠진다.

11과 3을 바꾸면,

꿀→5→2→7→4→8→12→5→2→7→4→8→12→… 무한루프에 빠진다.

11과 4를 바꾸면,

꿀→5→2→7→6→1→3→9→2→5→12→7→2→5→12→7… 무한루프에 빠진다.

11과 6을 바꾸면,

꿀→5→2→7→4→8→12→5→2→7→4→8→12→… 무한루프에 빠진다.

마지막으로 11과 5를 바꾸면,

꿀→11→2→7→4→8→12→7→2→9→3→1→5→집. 개미가 집에 도착할 수 있게 된다!

따라서 정답은 5와 11을 바꾸는 것이다.

도착해야 하는 흙더미가 두번째로 높은 11이라 이동하기 쉽지 않아 보인다. 11을 바꾸지 않고 문제를 풀 수 있는지 따져보자. 개미가 11에 도달하려면 먼저 1이나 10으로 이동해야 한다. 인접 흙더미 세 개 중 하나는 방금 서 있던 흙더미이고, 하나는 11이므로 나머지 한 경로가 12로 막혀있어야 한다. 12를 4, 6, 혹은 3과 바꾸는 세 경우를 모두 따져보면 문제가 해결되지 않는다는 것을 확인할 수 있다.

4, 3의 경우: 더 작은 루프가 생긴다. (5 → 2 → 7 → 4 or 3 → 5)
6의 경우: 루프가 유지된다. (5 → 2 → 7 → 4 → 8 → 6 → 5)

따라서 11은 반드시 바꾸어야 한다. 흙더미 교환은 루프를 깨야하는데, 11을 네번째 열의 다른 흙더미와 바꾸는 것은 루프에 아무런 영향을 미치지 못한다. 세번째 열과 바꾸면 흙더미를 높이는 셈이라 역효과가 난다. 남은 경우는 6개이다. 정직하게 루프의 한쪽 방향을 틀어막아서 세번째 열로 탈출시키는 세 경우를 생각해보자. (예를 들어, 7과 11을 교환하면 2 → 7의 경로를 틀어막아 2 → 9로 탈출시킬 수 있다.)

7의 경우: 2 → 9로 탈출하지만 7이 6, 3보다 커 다른 루프에 갇힌다.
4의 경우: 7 → 6으로 탈출하지만 4가 3보다 커 다른 루프에 갇힌다.
8의 경우: 4 → 10으로 탈출하지만 8이 6, 3보다 커 다른 루프에 갇힌다.

이제 남은 선택지는 5, 2, 12이다. 2 혹은 12와 바꾸면 경로에 변화를 주지 못한다. 마지막으로 남은 경우의 수를 확인해보면 개미가 무사히 집으로 돌아갈 수 있음을 알 수 있다.

꿀 → 11 → 2 → 7 → 4 → 8 → 12 → 7 → 2 → 9 → 3 → 1 → 5 → 집