원반 3개를 옮기는 건 몇 번만 시도하면 금방 성공해요. 그런데 원반이 5개, 7개로 늘어나면 갑자기 훨씬 오래 걸리고, 10개쯤 되면 손으로 다 세기도 힘들 만큼 많은 이동이 필요해져요. 왜 원반 하나 늘었을 뿐인데 이렇게 급격히 어려워질까요? 그 답은 하노이의 탑이 "지수적으로 증가하는" 문제이기 때문이에요.
규칙은 간단해요. 세 개의 기둥이 있고, 첫 번째 기둥에 크기 순서대로 쌓인 원반들을 세 번째 기둥으로 전부 옮기면 돼요. 조건은 딱 두 가지 — 한 번에 원반 하나만 옮길 수 있고, 큰 원반을 작은 원반 위에 올릴 수 없어요. 원반이 n개일 때 필요한 최소 이동 횟수는 정확히 2ⁿ − 1번이에요. 원반이 1개면 1번, 2개면 3번, 3개면 7번, 4개면 15번… 이런 식으로 원반이 하나 늘어날 때마다 필요한 횟수가 거의 두 배로 뛰어요.
왜 하필 2ⁿ−1일까요? n개의 원반을 옮기려면, 먼저 맨 아래 큰 원반을 뺀 위쪽 n−1개를 보조 기둥으로 옮기고(이때 이미 2ⁿ⁻¹−1번이 필요해요), 맨 아래 원반을 목표 기둥으로 옮기고(1번), 마지막으로 보조 기둥에 있던 n−1개를 다시 목표 기둥으로 옮기면(또 2ⁿ⁻¹−1번) 끝나요. 이걸 식으로 쓰면 (2ⁿ⁻¹−1) + 1 + (2ⁿ⁻¹−1) = 2ⁿ−1이 되는데, 이렇게 "큰 문제를 같은 모양의 작은 문제로 쪼개서 해결하는" 방식을 재귀라고 불러요. 하노이의 탑은 재귀적 사고를 배우는 데 가장 유명한 예제로, 컴퓨터공학과에서도 프로그래밍을 처음 배울 때 단골로 등장해요.
이 퍼즐에는 인도의 사원에 관한 유명한 전설도 얽혀 있어요. 승려들이 64개의 금 원반을 이 규칙에 따라 옮기고 있으며, 다 옮기고 나면 세상이 끝난다는 이야기예요. 64개 원반의 최소 이동 횟수는 2⁶⁴−1번인데, 1초에 하나씩 쉬지 않고 옮겨도 약 5,850억 년이 걸려요. 우주의 나이(약 138억 년)보다도 훨씬 긴 시간이에요. 이 전설 덕분에 하노이의 탑은 "지수적으로 증가하는 양이 얼마나 무서운 속도로 커지는지"를 보여주는 대표적인 예시로 자주 인용돼요.
이런 지수적 증가는 하노이의 탑 밖에서도 중요하게 다뤄져요. 세균이 일정 시간마다 두 배로 늘어나는 것, 종이를 반으로 계속 접었을 때 두께가 순식간에 엄청나게 두꺼워지는 것도 같은 원리예요. "작아 보이는 규칙이 반복되면 상상 이상으로 커진다"는 감각을 익히는 데, 하노이의 탑만큼 직관적인 예제도 드물어요.
아이들과 풀어볼 때는 원반 3개부터 시작해서 최소 횟수(7번)로 풀어보게 하고, 그다음 원반 4개(15번), 5개(31번)로 늘려가며 "몇 번 만에 풀었는지" 기록해보게 하세요. 원반이 늘어날 때마다 필요한 횟수가 정확히 두 배 조금 넘게 늘어난다는 걸 직접 확인하면, 지수 증가라는 추상적인 개념이 훨씬 생생하게 다가올 거예요.
저희 체험 페이지에서는 원반 3개부터 6개까지 난이도를 골라 도전할 수 있고, 이론상 최소 이동 횟수와 지금까지 옮긴 횟수를 실시간으로 비교해볼 수 있어요. 최소 횟수에 정확히 맞춰서 풀어보는 것에도 도전해보세요.