하노이의 탑에서 원판이 n개일 때 탑을 다른 기둥으로 옮기는 가장 적은 수는 2ⁿ−1번이에요. 2를 원판 개수만큼 곱하고 1을 뺀 수예요.
| 원판 개수 | 최소 수 |
|---|---|
| 1개 | 1번 |
| 2개 | 3번 |
| 3개 | 7번 |
| 4개 | 15번 |
| 5개 | 31번 |
| 6개 | 63번 |
| 7개 | 127번 |
| 8개 | 255번 |
| 9개 | 511번 |
원판이 1개 늘 때마다 수는 대략 2배가 돼요. 왜 그런지 차례로 살펴봐요.
가장 큰 원판에 주목하기
원판 n개의 탑을 왼쪽에서 오른쪽으로 옮기는 것을 생각해 봐요. 가장 큰 원판은 다른 원판 아래에 있어서 그대로는 움직일 수 없어요. 큰 원판을 오른쪽으로 옮기려면 그 순간에 다음 상태여야 해요.
- 큰 원판 위에 아무것도 올라가 있지 않다.
- 오른쪽 기둥이 비어 있다(큰 원판보다 작은 원판은 그 아래에 놓을 수 없기 때문).
즉 나머지 n−1개는 모두 가운데 기둥에 쌓여 있어야 해요.
수를 세 부분으로 나누기
여기서부터 원판 n개를 옮기는 순서는 다음 세 부분으로 나눌 수 있어요.
- 위의 n−1개를 왼쪽에서 가운데로 옮긴다.
- 가장 큰 원판을 왼쪽에서 오른쪽으로 한 번에 움직인다.
- 가운데의 n−1개를 큰 원판 위로 옮긴다.
1과 3은 둘 다 “원판 n−1개의 탑을 옮기는” 문제 그 자체예요. 원판 n개의 최소 수를 T(n)이라고 쓰면,
T(n) = T(n−1) + 1 + T(n−1) = 2 × T(n−1) + 1
이라는 관계가 돼요. 원판 1개일 때는 1번이니 T(1) = 1. 여기서부터 차례로 3, 7, 15, 31…을 구할 수 있어요.
식이 2ⁿ−1이 되는 이유
이 관계의 양변에 1을 더하면,
T(n) + 1 = 2 × (T(n−1) + 1)
이 돼요. “수에 1을 더한 수”는 원판이 1개 늘 때마다 정확히 2배가 된다는 거예요. 원판 1개일 때는 T(1) + 1 = 2이니, n개에서는 2를 n번 곱한 2ⁿ. 거기서 1을 빼면 T(n) = 2ⁿ−1이 돼요.
이보다 줄일 수 없는 이유
위의 순서로 2ⁿ−1번에 옮길 수 있다는 것은 알았어요. 그렇다면 더 적은 수로 옮기는 방법은 없을까요?
앞에서 말했듯이 큰 원판을 처음 움직이는 순간에는 나머지 n−1개가 모두 다른 한 기둥에 쌓여 있어야 해요. 거기까지 적어도 원판 n−1개의 탑을 옮기는 수가 들어요. 마찬가지로 큰 원판을 마지막에 오른쪽에 놓은 뒤 나머지 n−1개를 그 위로 다시 쌓는 데도 적어도 원판 n−1개의 탑을 옮기는 수가 들어요. 큰 원판 자체도 적어도 1번은 움직여요.
어떤 순서든 이 세 가지 수는 반드시 들어요. 그래서 2 × T(n−1) + 1번보다 적게는 할 수 없어요. 가장 적은 수의 순서는 사실 이 한 가지뿐이라는 것도 알려져 있어요.
앱의 “기본”은 127수
앱 “하노이의 탑”의 기본은 원판 7개이니 최소 수는 2⁷−1 = 127수예요. 수가 127이 되면 가장 적은 수로 푼 거예요. 노는 법 기사에서 소개한 “작은 원판을 같은 방향으로 돌리는” 움직임을 하면 딱 127수로 완성돼요.
