하노이의 탑 푸는 법에서 외울 것은 두 가지 순서뿐이에요. 이것을 번갈아 되풀이하면 원판이 몇 개든 가장 적은 수로 탑을 옮길 수 있어요. 이 기사에서는 왼쪽 기둥의 탑을 오른쪽 기둥으로 옮기는 경우로 설명해요(규칙은 하노이의 탑이란?을 보세요). 원판은 작은 것부터 차례로 1, 2, 3…번이라고 불러요.
푸는 법은 두 가지 순서의 되풀이
- 홀수 번째 수(1번째·3번째·5번째…): 가장 작은 원판(1)을 정해진 방향으로 옆 기둥으로 하나 움직인다.
- 짝수 번째 수(2번째·4번째·6번째…): 1이 아닌 원판 중에서 움직일 수 있는 수를 둔다. 움직일 수 있는 수는 언제나 하나뿐이에요.
이게 전부예요. 1은 한 수 걸러 움직이고, 그 사이에 1이 아닌 원판이 한 번씩 움직여요.
작은 원판을 돌리는 방향 정하기
1을 움직이는 방향은 원판 개수로 정해져요. 기둥 3개를 고리처럼 이어져 있다고 생각하고, 끝까지 오면 반대쪽 끝으로 돌아요. 왼쪽 탑을 오른쪽으로 옮길 때는 다음 순서예요.
| 원판 개수 | 1을 움직이는 순서 |
|---|---|
| 홀수 개(3·5·7…) | 왼쪽→오른쪽→가운데→왼쪽… |
| 짝수 개(4·6·8…) | 왼쪽→가운데→오른쪽→왼쪽… |
외우는 법은 “홀수 개라면 첫 수에서 1을 옮기려는 기둥에 곧바로 놓는다”예요. 짝수 개라면 첫 수는 옮기려는 기둥이 아닌 쪽(가운데)에 놓아요. 방향을 정했으면 끝까지 바꾸지 않아요.
가운데 기둥으로 옮기고 싶을 때는 표의 “오른쪽”과 “가운데”를 바꿔서 생각해요.
원판 3개로 확인하기
3개(홀수)이니 1은 “왼쪽 → 오른쪽 → 가운데 → 왼쪽” 순서로 돌아요. 금색 원판이 그 수에서 움직인 원판이에요.
- 처음
- 1번째 수 1번을 오른쪽으로
- 2번째 수 2번을 가운데로
- 3번째 수 1번을 가운데로
- 4번째 수 3번을 오른쪽으로
- 5번째 수 1번을 왼쪽으로
- 6번째 수 2번을 오른쪽으로
- 7번째 수 1번을 오른쪽으로
1번째·3번째·5번째·7번째 수는 1이 돌고 있을 뿐이고, 2번째·4번째·6번째 수는 “1이 아닌 것 중 움직일 수 있는 단 하나의 수”가 되는 것을 알 수 있어요.
짝수 번째 수가 하나로 정해지는 이유
짝수 번째 수에서는 1이 놓여 있지 않은 두 기둥의 맨 위 원판끼리 비교해요. 작은 쪽을 큰 쪽 위(또는 빈 기둥)로 움직일 수밖에 없어요.
- 1 위에는 어떤 원판도 놓을 수 없어요(1보다 작은 원판이 없기 때문).
- 남은 두 기둥에서는 큰 원판을 작은 원판 위에 놓을 수 없어요.
그래서 움직일 수 있는 수는 언제나 하나뿐이에요. 헷갈리는 것은 홀수 번째의 1의 방향뿐이고, 그것도 처음에 정해 버리면 나머지는 생각하지 않아도 손이 나아가요.
“위를 치우고, 큰 것을 옮긴다”는 생각
순서를 외우는 것과는 별도로, 왜 이렇게 풀리는지 생각하는 방법도 있어요. 원판 n개의 탑을 왼쪽에서 오른쪽으로 옮기려면,
- 위의 n−1개를 가운데로 치운다.
- 가장 큰 원판을 오른쪽으로 옮긴다.
- 가운데의 n−1개를 오른쪽으로 옮긴다.
의 세 가지로 나누면 된다는 생각이에요. 1과 3은 “1개 적은 탑을 옮기는” 문제이니 같은 생각을 한 번 더 쓸 수 있어요. 원판 4개라면 “3개를 치운다 → 4를 옮긴다 → 3개를 되돌린다”, 3개를 치우려면 “2개를 치운다 → 3을 옮긴다 → 2개를 되돌린다”… 이렇게 작은 문제로 나눠 갈 수 있어요. 이 생각에서 수가 2ⁿ−1번이 되는 것도 알 수 있어요(최소 수 공식).
도중에 헷갈렸을 때 다시 세우는 법
순서를 잊어서 흩어진 배치가 되어 버려도 괜찮아요. 다음 생각으로 어디서든 다시 세울 수 있어요.
- 아직 오른쪽 기둥에 올바르게 쌓지 못한 원판 중 가장 큰 것을 찾아요. 이것이 다음에 옮길 원판이에요.
- 그 원판을 오른쪽으로 옮기려면 그보다 작은 원판을 모두 지금 있는 기둥도 오른쪽 기둥도 아닌 남은 한 기둥에 모아 둬야 해요.
- 작은 원판을 모으는 것도 같은 생각의 되풀이예요. 모을 곳을 “목표 기둥”이라고 생각하고 처음부터 다시 해요.
큰 원판부터 차례로 목적지를 정해 가는 것이 요령이에요. 앱의 “문제” 모드(흩어진 원판을 본보기 모양으로 맞추는 놀이 방식)도 이 생각으로 풀 수 있어요.
공략 요령
- 수를 세요: 홀수 번째에는 반드시 1을 움직이니, 몇 번째 수인지 알면 다음에 움직일 원판을 헷갈리지 않아요.
- 큰 원판일수록 움직이지 않아요: 1은 전체의 절반의 수에서 움직이지만, 가장 큰 원판은 1번만 움직여요. 큰 원판을 여러 번 움직이고 있다면 멀리 돌아가고 있는 거예요.
- 처음에는 원판 3개나 4개로: 두 가지 순서가 몸에 익을 때까지는 적은 개수로 여러 번 되풀이하는 것을 추천해요. 익숙해지면 5개, 7개로 늘려요.
원판 개수별 순서
원판 개수별 순서와 도중 모양의 표지는 다음 기사에 정리해 두었어요.
놀면서 해 보기
아래 판에서 두 가지 순서를 해 보세요. 기둥을 누르면 맨 위 원판을 들어 올리고, 다른 기둥을 누르면 거기에 놓아요. 처음에는 원판 4개(짝수)이니 첫 수는 1을 가운데로 움직여요.
