하노이 탑
원반을 다른 기둥으로 옮겨 보세요
크기가 다른 원반 세 장을 기둥에 꽂고, 큰 원반이 작은 원반 위에 올라가지 않도록 한 번에 한 장씩 세 번째 기둥으로 옮겨 보세요.
세 장은 7번, 네 장은 15번 만에 옮겨집니다. 왜 원반이 하나 늘어날 때마다 옮기는 횟수가 정확히 2배보다 1번 더 많아질까요?
이야기
1883년 파리, 수학자 에두아르 뤼카가 이 장난감을 만들어 팔았습니다. 그런데 그는 자기 이름을 쓰지 않고 「시암의 클라우스 교수」라는 이름을 달았습니다. 이 가짜 이름은 「아미앵의 뤼카」의 글자를 뒤섞은 것이었습니다.
포장에는 이야기가 하나 붙어 있었습니다. 인도의 어느 사원에 예순네 장짜리 탑이 있고, 승려들이 그것을 다 옮기면 세상이 끝난다는 것이었습니다.
그런데 겁먹을 것 없습니다. 예순네 장이면 옮기는 횟수가 1844경 6744조 번입니다. 일 초에 한 장씩 쉬지 않고 옮겨도 5850억 년이 걸립니다. 우주의 나이가 138억 년이니, 그 마흔 배가 넘습니다.
왜 한 장 늘 때마다 갑절이 되고 하나가 더 붙을까요. n장을 옮기려면 먼저 위의 n−1장을 통째로 비켜 두어야 합니다. 맨 아래 큰 것을 한 번 옮기고, 비켜 둔 n−1장을 다시 그 위로 옮겨야 합니다.
그러니 「n−1장 옮기기」를 두 번 하고 여기에 한 번을 더한 것입니다. 그래서 횟수가 2배 더하기 1로 늘고, 그 결과가 2의 n제곱에서 1을 뺀 수가 됩니다.
자료를 백업하는 방식에 쓰입니다. 「하노이 탑 백업」은 테이프를 바꿔 쓰는 순서를 이 규칙으로 정해, 적은 테이프로 여러 시점의 자료를 보관합니다.
프로그래밍을 배울 때 재귀를 익히는 첫 문제이기도 합니다.
계단 넷 — 같은 사실을 네 깊이로
원반 3~4장으로 직접 옮긴다
동전이나 컵 받침 세 개를 크기순으로 쌓고 규칙에 맞춰 옆자리로 옮겨 봅니다. 작은 원반 위에 큰 원반을 올릴 수 없습니다.
원반 1개는 1번, 2개는 3번, 3개는 7번, 4개는 15번이 걸립니다. 숫자를 적어 보면 1, 3, 7, 15, 31로 앞의 수에 2를 곱하고 1을 더한 규칙이 한눈에 드러납니다.
원반을 몇 번 옮겨야 할까요
1 · 3 · 7 · 15 · 31 — 2ⁿ − 1 입니다.
횟수가 2ⁿ−1 인 것 찾기
개의 원반을 옮기려면 맨 밑의 가장 큰 원반을 옮기기 전에 위의 개를 보조 기둥으로 먼저 치워 두어야 합니다.
그다음 맨 밑 원반을 목표 기둥에 놓고, 다시 개를 그 위로 옮겨 옵니다. 따라서 횟수 점화식은 이 되며, 풀면 번이 됩니다.
규칙을 찾아보세요
n 장을 옮기려면 「위 n−1 장 옮기고 · 큰 것 하나 옮기고 · 다시 n−1 장」 — 그래서 2·(n−1의 횟수) + 1.
점화식과 귀납법
수학적 귀납법으로 을 증명할 수 있습니다. 일 때 로 성립하고, 이면 이 성립합니다.
이 구조는 컴퓨터 과학의 재귀 알고리즘(Recursion)과 분할 정복(Divide and Conquer)의 표준 표본이며, 상태 전이 그래프를 그리면 프랙탈인 시에르핀스키 삼각형의 격자 구조와 정확히 동형이 됩니다.
예순네 장이면 얼마나 걸릴까요
1초에 한 번씩 옮겨도 5,850억 년 — 우주 나이의 마흔 배입니다.
재귀와 시에르핀스키
하노이 탑의 상태 공간은 꼭짓점 개를 가진 그래프를 이루며, 최적 해 경로는 이 그래프 위의 해밀턴 경로가 됩니다. 기둥이 4개 이상인 프레임-스튜어트 추측(Frame-Stewart conjecture)은 최근에야 부분 증명되었습니다.
이 문제는 그레이 부호(Gray code), 베이스-3 진법 수 체계, 그리고 조합론적 게임 이론의 오토마타 모델로 깊이 연구됩니다.
이것이 「풀 수 없다」의 뜻입니다
「풀 수 있다」와 「현실에서 풀린다」는 다릅니다 — 계산복잡도 이론이 여기서 시작합니다.
풀어 보기
하노이 탑의 최소 이동 횟수. 개의 원반을 규칙에 맞게 다른 기둥으로 옮기는 최소 횟수를 이라 하자.
(1) 원반 5개를 옮길 때의 최소 이동 횟수 의 값을 구하시오.
(2) 를 만족하는 원반의 개수 을 구하시오.
(3) 원반 64개를 1초에 1번씩 밤낮없이 옮긴다면 걸리는 총시간(초)을 거듭제곱 꼴로 나타내시오.
(2) 이므로 입니다.
답과 풀이 보기
(1) 이므로 번입니다.
(2)
이므로 입니다.
(3) 초입니다. 값으로는 약 초, 곧 오천억 년이 넘습니다. 우주의 나이가 약 138억 년이니 걱정하지 않아도 됩니다.
여기 「풀어 보기」는 기본 한 벌입니다. 더 풀어 보고 싶으면 행복수학의 그 단원으로 건너가세요.
더 멀리
「자기보다 한 단계 작은 문제로 미루기」는 컴퓨터가 가장 잘하는 방식입니다.
- 재귀 호출 — 프로그램이 자기 자신을 부르며 문제를 줄여 갑니다. 하노이 탑은 그것을 가르치는 첫 예제입니다
- 자료 정리(정렬) — 반으로 쪼개고, 각각을 같은 방법으로 정리하고, 합칩니다
- 백업 돌리기 — 매체를 하노이 탑 순서로 돌려 쓰면 오래된 자료도 남길 수 있습니다
이어지는 장
원판이 하나 늘어날 때마다 이동 횟수가 두 배씩 폭발적으로 늘어나는 하노이 탑의 원리는, 접을 때마다 두께가 두 배가 되는 거듭제곱의 놀라움과 똑같습니다 — 제22장에서 지수적 증가의 위력을 체감해 보세요.
영감을 받은 곳
프랑스의 수학자 에두아르 뤼카가 1883년 'N. 클라'라는 필명으로 발표한 수학 퍼즐과 인도 바라나시 사원의 전설 이야기에서 비롯되었습니다.