하노이의 탑을 가장 적은 수로 풀면 그 순서에는 놀랄 만큼 아름다운 규칙성이 있어요. 여기서는 원판 n개의 탑을 왼쪽에서 오른쪽으로 옮기는 최소 순서(2ⁿ−1수)에서 찾을 수 있는 규칙을 차례로 소개해요. 원판에는 작은 것부터 차례로 1, 2, 3…번을 붙여요.
원판별로 움직이는 횟수는 2의 거듭제곱
최소 순서 속에서 각 원판이 움직이는 횟수는 정해져 있어요. 원판이 n개일 때 k번 원판은 2ⁿ⁻ᵏ번 움직여요.
| 원판(4개일 때) | 움직이는 횟수 |
|---|---|
| 1 | 8번 |
| 2 | 4번 |
| 3 | 2번 |
| 4 | 1번 |
| 합계 | 15번 |
가장 큰 원판은 1번, 그다음은 2번, 그다음은 4번… 이렇게 작아질수록 2배가 돼요. 합하면 1 + 2 + 4 + … + 2ⁿ⁻¹ = 2ⁿ−1로 최소 수와 딱 일치해요.
이유는 최소 수 공식과 같은 생각으로 알 수 있어요. 원판 n개를 옮기려면 원판 n−1개의 탑을 2번 옮겨요. 그래서 n번보다 작은 원판은 n−1개를 옮길 때의 2배씩 움직이게 되는 거예요.
몇 번째 수에 어느 원판이 움직일까
원판 4개의 최소 순서에서 첫 수부터 차례로 움직이는 원판의 번호를 늘어놓으면 다음과 같아요.
1 2 1 3 1 2 1 4 1 2 1 3 1 2 1
1이 한 수 걸러 나오고, 그 사이에 2가 하나 걸러, 또 그 사이에 3이… 이렇게 들어 있어요. 자의 눈금 길이의 나열(짧다·중간·짧다·길다…)과 같은 모양이에요.
이 나열은 몇 번째 수인지를 이진수로 쓰면 바로 구할 수 있어요.
| 몇 번째 수 | 이진수 | 끝의 0의 개수 | 움직이는 원판 |
|---|---|---|---|
| 1 | 1 | 0개 | 1 |
| 2 | 10 | 1개 | 2 |
| 3 | 11 | 0개 | 1 |
| 4 | 100 | 2개 | 3 |
| 5 | 101 | 0개 | 1 |
| 6 | 110 | 1개 | 2 |
| 7 | 111 | 0개 | 1 |
| 8 | 1000 | 3개 | 4 |
m번째 수에 움직이는 것은 m을 이진수로 썼을 때 “끝에 이어지는 0의 개수+1”번 원판이에요. 홀수 번째 수는 이진수의 끝이 1이니 언제나 1이 움직여요. 이것이 푸는 법 기사의 “홀수 번째는 1을 움직인다”의 이유예요.
더 나아가 움직일 출발 기둥과 도착 기둥도 이진수 계산만으로 구할 수 있어요(알고리즘 기사).
그레이 코드와의 연결
이진수를 0부터 차례로 셀 때 1씩 늘 때마다 바뀌는 자리의 수는 제각각이에요(0111에서 1000으로 가면 4자리가 바뀌어요). 그래서 한 단계 나아갈 때마다 한 자리만 바뀌도록 늘어놓은 수의 표현 방식을 “그레이 코드”라고 해요.
| 순서 | 그레이 코드 | 바뀌는 자리(오른쪽부터) |
|---|---|---|
| 0 | 000 | ― |
| 1 | 001 | 1 |
| 2 | 011 | 2 |
| 3 | 010 | 1 |
| 4 | 110 | 3 |
| 5 | 111 | 1 |
| 6 | 101 | 2 |
| 7 | 100 | 1 |
바뀌는 자리의 나열 “1 2 1 3 1 2 1”은 하노이의 탑에서 움직이는 원판의 나열과 똑같아요. 원판 1개를 이진수의 한 자리로 보고 “그 자리가 바뀐다=그 원판이 움직인다”고 생각하면, 하노이의 탑의 최소 순서는 그레이 코드를 차례로 따라가는 것과 같아져요.
원판이 도는 방향
푸는 법 기사에서 1은 항상 같은 방향으로 돈다고 소개했어요. 사실 다른 원판에도 같은 규칙이 있어요.
- 홀수 번 원판(1·3·5…)은 모두 1과 같은 방향으로 돈다.
- 짝수 번 원판(2·4·6…)은 모두 1과 반대 방향으로 돈다.
왼쪽 탑을 오른쪽으로 옮길 때 원판이 홀수 개면 1은 “왼쪽 → 오른쪽 → 가운데” 방향, 짝수 개면 “왼쪽 → 가운데 → 오른쪽” 방향이에요. 어느 원판이든 끝까지 한 번도 방향을 바꾸지 않아요.
또 하나, 원판 10개 푸는 법에서 소개한 규칙도 있어요. 최소 순서에서는 홀수 번 원판 위에 홀수 번을, 짝수 번 위에 짝수 번을 바로 놓는 일이 없어요.
배치는 모두 3ⁿ가지
규칙을 지킨 원판의 배치는 모두 몇 가지일까요? 어느 원판이든 3개의 기둥 중 어디에나 놓을 수 있고, 같은 기둥에 올라간 원판의 순서는 큰 순서로 정해져 버리니 배치는 3ⁿ가지예요.
| 원판 개수 | 배치 |
|---|---|
| 3개 | 27가지 |
| 5개 | 243가지 |
| 7개 | 2,187가지 |
| 9개 | 19,683가지 |
게다가 어떤 배치에서 어떤 배치로든 규칙을 지키며 반드시 옮길 수 있어요. 모든 배치를 점으로 나타내고 한 수로 옮길 수 있는 점끼리 선으로 이으면, 큰 삼각형 안에 작은 삼각형이 겹겹이 들어 있는 “시에르핀스키 삼각형”과 아주 닮은 도형이 된다는 것도 알려져 있어요.
앱 “하노이의 탑”의 “문제” 모드는 이 모든 배치 중에서 본보기 모양으로 맞추는 문제를 만들어요. 원판 9개의 ★5에서도 19,683가지 배치 모두에 대해 최단 수를 알아본 뒤에 출제해요.
