보통의 하노이의 탑은 기둥이 3개예요. 그렇다면 기둥을 1개 늘려 4개로 하면 어떻게 될까요? 규칙은 같아요. 한 번에 1개씩, 작은 원판 위에 큰 원판을 놓지 않고 탑을 다른 기둥으로 옮겨요.

1개 늘 뿐인데 수가 크게 줄어요

쓸 수 있는 놓을 자리가 1곳 늘어서 원판을 치우기가 훨씬 쉬워져요. 최소 수를 비교하면 그 차이는 원판이 늘수록 커져요.

원판 개수기둥이 3개기둥이 4개
3개7수5수
4개15수9수
5개31수13수
6개63수17수
7개127수25수
8개255수33수
10개1,023수49수
64개약 1845경 수18,433수

기둥 3개에서는 원판 64개를 옮기는 데 1초에 1수씩이라도 약 5845억 년이 걸려요(원판 64개를 옮기면 몇 년이 걸릴까?). 그런데 4개라면 18,433수, 1초에 1수씩이면 약 5시간이에요. 전설 속 승려들이 기둥을 1개 늘렸다면 세상은 그날 안에 끝났을 거예요.

듀드니의 “치즈 퍼즐”

기둥 4개의 하노이의 탑을 널리 알린 것은 영국의 퍼즐 작가 헨리 듀드니예요. 1907년의 책 『캔터베리 퍼즐』 속에서 “리브의 퍼즐”로 출제했어요. 리브는 장원의 관리인을 뜻해요.

듀드니의 문제에서는 원판 대신 크기가 다른 치즈 8개를 걸상 4개 사이에서 옮겨요. 작은 치즈 위에 큰 치즈를 올리면 안 돼요. 답은 33수로, 위 표의 원판 8개와 같아요.

프레임-스튜어트 풀이

기둥 4개에서 적은 수로 옮기는 방법은 1941년에 J. S. 프레임과 B. M. 스튜어트가 각각 같은 생각을 발표했어요. 원판 n개의 탑을 옮길 때,

  1. 위의 k개를 기둥 4개를 모두 써서 옮기려는 기둥이 아닌 기둥으로 옮긴다.
  2. 남은 n−k개를 위의 k개가 있는 기둥을 쓰지 않고 기둥 3개만으로 옮기려는 기둥으로 옮긴다(2ⁿ⁻ᵏ−1수).
  3. 1에서 치운 k개를 기둥 4개를 모두 써서 옮기려는 기둥으로 옮긴다.

이렇게 세 부분으로 나눠요. 1과 3은 같은 문제의 작은 판이라서 재귀의 생각을 쓸 수 있어요(알고리즘 기사). 나머지는 위에 몇 개(k개)를 남기면 가장 적어지는지 고르기만 하면 돼요. 원판 8개라면 위의 4개나 5개를 먼저 치우는 것이 가장 적고 33수가 돼요.

100년 가까이 증명되지 않았던 “가장 적은 수”

프레임-스튜어트의 방법으로 적은 수로 옮길 수 있다는 것은 알았어요. 그런데 이보다 적은 방법이 정말 없는지는 오랫동안 아무도 증명하지 못했어요.

기둥 3개라면 “가장 큰 원판을 움직이는 순간 다른 원판은 모두 1개 기둥에 모여 있어야 한다”는 한 가지 사실에서 최소 수를 바로 증명할 수 있어요(최소 수 공식). 4개가 되면 큰 원판을 움직이는 순간 다른 원판이 남은 2개 기둥에 어떻게 나뉘어 있어도 되기 때문에 생각할 수 있는 순서가 단번에 늘어나 버려요.

컴퓨터로 모든 배치를 조사해서 원판 30개쯤까지는 이 방법이 최소임이 확인되어 있었어요. 그리고 듀드니의 출제에서 약 100년 뒤인 2014년, 프랑스의 수학자 티에리 부슈가 원판이 몇 개든 프레임-스튜어트의 방법이 최소임을 증명했어요. 기둥이 5개 이상인 경우는 지금도 증명되지 않았다고 해요.

직접 해 볼 수도 있어요

기둥 4개의 하노이의 탑은 만드는 법 기사의 두꺼운 종이 만드는 법에서 놓을 자리의 동그라미를 4개로 하면 만들 수 있어요. 원판 3개를 5수, 4개를 9수로 옮길 수 있는지 해 보세요. 기둥 3개일 때와의 차이를 몸으로 느낄 수 있어요.