하노이탑

하노이탑의 원판을 옮기는 최소 횟수에는 어떤 규칙성이 있을까? 여기에는 메르센 수가 숨어있다고 한다. 메르센 수(Mersenne number)는 2의 거듭제곱에서 1이 모자란 숫자를 말한다. 원판의 개수를 n이라고 할 때, 원판을 옮기는 최소 횟수는 지수가 n인 메르센 수이다.

고대 인도 베나레스에 있는 한 사원의 이야기에는 하노이탑 문제가 나온다. 이 사원에는 세상의 중심을 나타내는 큰 돔이 있고, 그 안에 세 개의 다이아몬드 기둥이 있다. 한 기둥에는 64개의 크기가 다른 황금 원반이 놓여 있는데, 가장 아래쪽에 있는 것이 가장 크고, 위로 올라갈수록 작아져 원추 모양을 이룬다. 브라흐마가 정한 규칙에 따라 승려들은 모든 원판을 다른 기둥으로 밤낮없이 옮기는데, 이 일이 끝날 때 탑은 무너지고 세상은 종말을 맞이하게 된다. 브라흐마가 정한 규칙은 다음과 같다.

1. 한 번에 하나의 원판을 다른 기둥으로 옮긴다.

2. 항상 작은 원판이 큰 원판의 위에 있다.