하노이의 탑을 가장 적은 수로 풀면 그 순서에는 놀랄 만큼 아름다운 규칙성이 있어요. 여기서는 원판 n개의 탑을 왼쪽에서 오른쪽으로 옮기는 최소 순서(2ⁿ−1수)에서 찾을 수 있는 규칙을 차례로 소개해요. 원판에는 작은 것부터 차례로 1, 2, 3…번을 붙여요.

원판별로 움직이는 횟수는 2의 거듭제곱

최소 순서 속에서 각 원판이 움직이는 횟수는 정해져 있어요. 원판이 n개일 때 k번 원판은 2ⁿ⁻ᵏ번 움직여요.

원판(4개일 때)움직이는 횟수
18번
24번
32번
41번
합계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의 개수움직이는 원판
110개1
2101개2
3110개1
41002개3
51010개1
61101개2
71110개1
810003개4

m번째 수에 움직이는 것은 m을 이진수로 썼을 때 “끝에 이어지는 0의 개수+1”번 원판이에요. 홀수 번째 수는 이진수의 끝이 1이니 언제나 1이 움직여요. 이것이 푸는 법 기사의 “홀수 번째는 1을 움직인다”의 이유예요.

더 나아가 움직일 출발 기둥과 도착 기둥도 이진수 계산만으로 구할 수 있어요(알고리즘 기사).

그레이 코드와의 연결

이진수를 0부터 차례로 셀 때 1씩 늘 때마다 바뀌는 자리의 수는 제각각이에요(0111에서 1000으로 가면 4자리가 바뀌어요). 그래서 한 단계 나아갈 때마다 한 자리만 바뀌도록 늘어놓은 수의 표현 방식을 “그레이 코드”라고 해요.

순서그레이 코드바뀌는 자리(오른쪽부터)
0000―
10011
20112
30101
41103
51111
61012
71001

바뀌는 자리의 나열 “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가지 배치 모두에 대해 최단 수를 알아본 뒤에 출제해요.