하노이의 탑 원반 64개를 옮기려면 · 수학적 귀납법

하노이의 탑은 기둥 세 개와 크기가 다른 원반 몇 개로 하는 퍼즐이다. 한 기둥에 큰 원반부터 쌓인 탑을 다른 기둥으로 옮기는데, 한 번에 원반 하나만 옮길 수 있고 작은 원반 위에 큰 원반을 놓을 수 없다. 원반이 1개면 1번, 2개면 3번, 3개면 7번이 가장 적은 이동 횟수다.

첫 도미노가 넘어지고, 하나가 넘어지면 다음이 넘어진다. 그 둘이면 끝없는 줄이 모두 넘어진다.

1, 3, 7을 보면 2ⁿ − 1이 떠오른다. 이것이 모든 n에서 맞는지는 수학적 귀납법으로 확인한다. 먼저 n = 1일 때 2¹ − 1 = 1로 맞다. 다음으로 원반 k개를 2ᵏ − 1번에 옮길 수 있다고 하자. 원반이 k + 1개면, 위의 k개를 가운데 기둥으로 옮기고(2ᵏ − 1번), 맨 아래 큰 원반을 옮기고(1번), k개를 다시 그 위로 옮긴다(2ᵏ − 1번). 합하면 2 × (2ᵏ − 1) + 1 = 2ᵏ⁺¹ − 1번이다.

첫 번째가 맞고, 어떤 경우가 맞으면 다음 경우도 맞으니, 도미노가 차례로 넘어지듯 모든 자연수 n에서 맞다. 이것이 수학적 귀납법이다. 원반 몇 개까지 직접 해 보는 것으로는 「모든 n」을 확인할 수 없지만, 이 두 단계면 끝이 없는 경우를 한 번에 확인한다.

전설에 따르면 어느 사원의 승려들이 원반 64개짜리 탑을 옮기고 있고, 다 옮기면 세상이 끝난다고 한다. 2⁶⁴ − 1은 약 1.8 × 10¹⁹번이다. 1초에 하나씩 쉬지 않고 옮겨도 약 5,800억 년이 걸린다. 지금 우주의 나이가 약 138억 년이니 걱정하지 않아도 된다.

이어서 학습하기