기둥 세 개에 원판을 옮기는 하노이 퍼즐에 규칙 하나를 더해요. 기둥은 시계 방향으로 A, B, C라 이름 붙이고, 이동은 A→B, B→C, C→A만 허용해요. 한 번에 맨 위 원판 하나만 옮기며, 큰 원판을 작은 원판 위에 놓을 수 없어요. 처음에는 크기가 서로 다른 원판 n개가 모두 A에 있어요.
A에서 C로 가려면 원판은 B를 거쳐야 해요. 그렇다면 A의 탑 전체를 B로 옮기는 최소 횟수를 두 배 하면, C로 옮기는 최소 횟수도 얻을까요? 원판 하나라면 맞아요. A→B는 한 번, A→B→C는 두 번이에요. 원판이 늘었을 때도 같은 판단을 유지할 수 있는지 물어요.
원판 n개를 한 칸 뒤 기둥으로 완전히 옮기는 최소 횟수를 S_n, 두 칸 뒤로 옮기는 최소 횟수를 L_n이라 해요. 기둥 이름을 함께 순환시켜 바꿔도 규칙은 같으므로 어느 기둥에서 출발했는지는 이 두 값에 영향을 주지 않아요. 원판이 없으면 이동도 없어 S_0=L_0=0입니다.
가장 큰 원판을 처음 A에서 B로 옮기는 순간을 볼까요? 그 위의 작은 원판 n−1개는 A에 남을 수 없고, 큰 원판이 들어갈 B에도 있을 수 없어요. 따라서 모두 C에 쌓여 있어야 해요. 이 준비에는 적어도 L_(n−1)번이 필요해요.
큰 원판이 다음으로 B에서 C로 이동하려면 작은 탑을 C에서 A로 옮겨야 해요. 이때는 시계 방향 한 칸이므로 적어도 S_(n−1)번이 필요해요. 가장 큰 원판이 계속 이동할 때마다, 두 이동 사이에 작은 탑이 한 칸씩 옮겨져야 해요. 큰 원판은 작은 원판들의 아래에만 놓이므로 작은 탑의 이동 규칙을 바꾸지 않아요.
마지막 큰 원판 이동 뒤에도 마무리가 남아요. 큰 원판이 목적지 B에 도착했다면 작은 탑은 C에, 목적지 C에 도착했다면 작은 탑은 A에 있어요. 어느 경우든 작은 탑을 목적지로 옮기는 것은 시계 방향 두 칸이에요. 적어도 L_(n−1)번을 더 써야 해요.
n≥1에서 가장 큰 원판의 이동 횟수를 k, 전체 이동 횟수를 T라 하면, 모든 해결 과정은 다음 하한을 가져요.
목적지가 B이면 k는 1, 4, 7, … 중 하나이고, C이면 2, 5, 8, … 중 하나예요. 가장 큰 원판을 한 바퀴 더 돌리면 하한이 3(S_(n−1)+1)만큼 늘어나요. 더 많이 돌려 작은 원판의 일을 줄이는 방법도 이 하한을 피하지 못해요.
B로 가는 경우는 작은 탑 A→C, 큰 원판 A→B, 작은 탑 C→B의 세 단계로 하한을 실제 달성해요. C로 가는 경우는 작은 탑 A→C, 큰 원판 A→B, 작은 탑 C→A, 큰 원판 B→C, 작은 탑 A→C의 다섯 단계예요. 더 작은 탑의 최소 이동을 차례로 사용하면 모두 합법적이에요. 원판이 없는 경우부터 이 구성을 반복할 수 있어요.
원판 두 개에서는 S_2=5, L_2=7입니다. 탑 전체를 A에서 B로 완성한 뒤 B에서 C로 다시 옮기면 10번이에요. 하지만 작은 원판 A→B→C, 큰 원판 A→B, 작은 원판 C→A, 큰 원판 B→C, 작은 원판 A→B→C의 순서로 하면 7번이에요. 작은 탑과 큰 원판의 이동을 중간에 섞어 B에서 전체 탑을 완성하는 조건을 피했어요.
이 차이는 두 원판만의 우연일까요? 두 식을 빼면 L_n−S_n=S_(n−1)+1이라 L_n>S_n입니다. 또 n≥2이면
오른쪽은 L_(n−1)>S_(n−1)≥0 때문에 양수예요. 따라서 원판이 두 개 이상일 때는 항상 S_n<L_n<2S_n입니다. 원판 하나에서는 L_1=2S_1이고, 원판이 없으면 두 값 모두 0입니다. 세 개의 값은 15와 21이어서, 탑 전체를 한 칸씩 두 번 옮기는 30번보다 짧아요.
교사는 실제 이동 순서를 찾은 답과 그보다 짧을 수 없다는 증명을 따로 확인해요. 제공 교재의 수열의 귀납적 정의는 이전 값으로 다음 값을 정하는 기초예요. 이번 점화식이 최소 횟수라는 결론에는 가장 큰 원판이 강제하는 준비·중간·마무리 단계의 하한이 더 필요해요.
착안: Paul K. Stockmeyer, The Average Distance between Nodes in the Cyclic Tower of Hanoi Digraph. 고전의 한 방향 규칙과 두 점화식에서 착안해, 중간 기둥에 탑 전체를 완성하는 추가 조건의 불이득을 자체 문항과 하한·달성 증명으로 구성했어요. 원문 코드나 도판의 번역이 아니에요.