보통의 하노이의 탑은 기둥이 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개의 탑을 옮길 때,
- 위의 k개를 기둥 4개를 모두 써서 옮기려는 기둥이 아닌 기둥으로 옮긴다.
- 남은 n−k개를 위의 k개가 있는 기둥을 쓰지 않고 기둥 3개만으로 옮기려는 기둥으로 옮긴다(2ⁿ⁻ᵏ−1수).
- 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개일 때와의 차이를 몸으로 느낄 수 있어요.
