하노이탑 원반이 한 장 늘면 이동이 두 배가 됩니다 — 64장이면 5,845억 년
핵심 요약 — 하노이탑의 최소 이동은 원반이 n장일 때 2ⁿ−1입니다. 3장 7번, 6장 63번, 10장이면 벌써 1,023번입니다. 원반이 한 장 늘 때마다 두 배가 조금 넘게 늡니다. 전설에 나오는 64장을 1초에 한 번씩 옮기면 5,845억 년이 걸립니다.
하노이탑은 규칙이 두 줄뿐입니다. 한 번에 한 장만 옮기고, 큰 원반을 작은 원반 위에 놓을 수 없습니다.
규칙이 짧은 것에 비해 이동 횟수는 가파르게 늡니다.
왜 2ⁿ−1인가
맨 아래 원반을 옮기는 순간을 생각해 보세요. 그 원반이 움직이려면 그 위에 있는 n−1장이 통째로 다른 기둥에 비켜 있어야 합니다. 아래 원반을 옮긴 다음에는 비켜 둔 n−1장을 다시 그 위에 얹어야 합니다.
n−1장을 통째로 옮기는 일이 두 번 필요합니다.
T(n) = 2 × T(n−1) + 1
T(1) = 1
이 식을 풀면 T(n) = 2ⁿ−1입니다. 한 장 늘 때마다 직전의 두 배에 한 번이 붙습니다.
표로 보면
| 원반 | 최소 이동 |
|---|---|
| 3장 | 7번 |
| 4장 | 15번 |
| 5장 | 31번 |
| 6장 | 63번 |
| 10장 | 1,023번 |
| 20장 | 1,048,575번 |
| 64장 | 18,446,744,073,709,551,615번 |
슬롯플레이는 6장까지 둡니다. 63번이면 손으로 둘 만하고, 7장이면 127번이라 같은 동작을 되풀이하는 시간이 더 길어집니다.
전설의 64장
인도 사원의 승려들이 64장짜리 하노이탑을 옮기고 있고, 다 옮기면 세상이 끝난다는 이야기가 있습니다. 실제로 계산해 보면 이렇습니다.
1초에 한 번씩 쉬지 않고 옮긴다고 하면 1,844경 6,744조 번이니 약 5,845억 년입니다. 우주 나이가 138억 년이니 그 42배입니다.
세상이 끝날 걱정은 하지 않아도 되겠습니다.
외우지 않고 최소로 두는 법
재귀를 머릿속으로 풀 필요가 없습니다. 규칙 하나만 지키면 저절로 최소가 됩니다.
- 가장 작은 원반을 한 번 걸러 한 번씩 옮깁니다. 늘 같은 방향으로만 돌립니다.
- 작은 원반을 옮기지 않는 차례에는 둘 수 있는 수가 하나뿐입니다. 그것을 둡니다.
도는 방향은 원반 수가 홀수면 첫 기둥에서 마지막 기둥 쪽으로, 짝수면 반대쪽으로 돕니다.
왜 되는지는 위의 재귀와 같은 이야기입니다. 작은 원반이 규칙적으로 돌면서 큰 원반이 옮겨질 자리를 차례로 비워 주기 때문입니다.
최소를 미리 알려 주는 이유
슬롯플레이는 판을 열 때 최소 이동을 화면에 적어 줍니다.
이 게임에는 숨길 것이 없습니다. 시작 배치가 언제나 같고 최소 이동은 공식으로 나옵니다. 숨겨 봐야 사람이 검색해서 알아낼 뿐이고, 목표를 모르면 몇 번에 끝냈다는 것이 뜻을 갖지 못합니다.
라이츠 아웃에서도 같은 이유로 최소 해를 적어 줍니다.
되돌리기는 세지 않습니다
방금 옮긴 것을 곧바로 되돌리면 그 수는 기록에서 빠집니다. 잘못 짚었다고 처음부터 다시 하게 만들 이유가 없기 때문입니다.
기록으로 남는 것은 이동 횟수이고, 서버가 처음 배치에서 그대로 다시 옮겨 봅니다. 완주만 보는 것이 아니라 가는 길에 규칙을 어긴 수가 없었는지까지 확인합니다.
자주 묻는 질문
하노이탑 최소 이동은 몇 번인가요?
원반이 n장이면 2ⁿ−1번입니다. 3장 7번, 4장 15번, 5장 31번, 6장 63번입니다.
재귀를 몰라도 최소로 풀 수 있나요?
네. 가장 작은 원반을 한 번 걸러 한 번씩 같은 방향으로만 돌리고, 나머지 차례에는 둘 수 있는 수가 하나뿐이므로 그것을 두면 저절로 최소가 됩니다.
가운데 기둥에 다 모으면 끝나나요?
아니요. 마지막 기둥에 전부 모여야 끝납니다.
코인이 드나요?
아니요. 하노이탑은 코인 차감이 없고 연령 제한 없이 즐길 수 있습니다.