하노이의 탑에서 원판이 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개를 옮기는 순서는 다음 세 부분으로 나눌 수 있어요.

  1. 위의 n−1개를 왼쪽에서 가운데로 옮긴다.
  2. 가장 큰 원판을 왼쪽에서 오른쪽으로 한 번에 움직인다.
  3. 가운데의 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수로 완성돼요.