백과

하노이탑의 전설^각주1)

전설에 의하면 인도의 베라네스라는 곳에 아주 큰 사원이 있습니다. 이 사원에는 구리로 된 판 위에 길이가 50cm 정도 되는 막대가 3개 세워져 있고, 그중 한 막대에는 위로 올라갈수록 크기가 작아지는 원판이 64개 끼워져 있습니다. 어느 날 브라만 신이 나타나 이 사원의 승려들에게 쉬지 않고 원판을 다른 막대에 옮기도록 명령하였습니다.

“원판을 한 번에 한 개씩 옮겨야 한며, 작은 원판 위에 큰 원판을 절대로 올려놓을 수 없다. 너희들이 이 일을 게을리 하면 곧바로 세상의 종말이 올 것이고, 게으름을 피우지 않고 이 일을 열심히 한다면 그때까지 세상은 평온할 것이다. 64개의 원판을 모두 옮겨 놓으면, 그 탑과 사원, 너희들은 모두 먼지가 되어 사라지고 세상은 종말이 올 것이다.”

브라만 신은 이 말은 남기고 연기와 함께 사라졌다고 합니다.

지구의 종말은 언제일까?

겨우 원판 64개를 다른 기둥으로 옮기면 지구의 종말이 온다니 걱정이 됩니다. 이 문제를 해결하기 위해 하노이탑의 규칙을 다시 한 번 정리해 봅시다.

규칙 1 : 한 번에 하나의 원판만 옮길 수 있다.
규칙 2 : 작은 원판 위에 큰 원판을 올려놓을 수 없다.

이제 규칙1과 규칙2에 따라 원판을 하나씩 옮겨 보고 실제 얼마나 시간이 걸리는지 알아보아야 합니다. 원판 64개는 너무 많이 보이는 원판의 개수를 1개일 때부터 따져 보기로 합니다.

원판이 1개인 경우

원판이 한 개이면 다른 기둥으로 옮기는 데 한 번만 움직이면 됩니다. 아주 간단한 문제군요.

원판이 2개인 경우

원판이 2개이면, 한 번 움직일 때마다 다른 원판을 움직이는 것도 함께 고려해야 합니다. 이렇게 되면 약간 복잡해지겠군요. 이처럼 원판의 개수를 하나씩 추가해 가면서 규칙을 찾아보면 다음과 같습니다.

원판이 3개이면 움직인 횟수는 2³－1이고, 원판이 4개이면 움직인 횟수는 2⁴－1입니다. 따라서 원판이 64개이면 움직인 횟수는 모두 2⁶⁴－1이 됩니다. 그런데 2⁶⁴－1은 얼마나 큰 수일까요? 2⁶⁴－1은 2를 64번 곱한 값에 1을 뺀 수입니다.

이것을 계산기를 이용하여 계산하면

2⁶⁴－1＝18446744073709551615

으로 약 1800경입니다.

만약 사원의 승려들이 1초에 원판을 1개 움직인다면

18446744073709551615 초 ＝ 약 583334858456 년
＝ 약 5833억년

입니다. 5833억년이 지나야 세상의 종말이 오므로 걱정하지 않아도 됩니다. 현재 우주의 나이가 과학자에 따라서 다르기도 하지만 길어야 겨우 200억년이라고 하니까 말이지요.