아주 먼 옛날 인도의 갠지스 강 기슭에 브라만교의 대사원이 있었다. 그곳에는 세계의 중심임을 나타내는 큰 탑이 있는데 그 아래에는 구리로 만든 판자 위에 높이가 약 50cm정도인 다이어
몬드 기둥이 세 개 세워져 있고 그 중 한 기둥에는 위로 올라갈수록 작아지는 원뿔대 모양으로 64개의 원판이 끼워져 있다.
여기에는 다음과 같은 신의 지시가 옛날부터 전해 내려오고 있다.
"이 세 개의 기둥을 적당히 써서 한 개의 기둥에 끼워진 원판을 다른 기둥으로 옮겨라. 다만 원판은 한 번에 1개씩 옮기되 큰 것을 작은 것 위에 얹으면 안 된다. 이제부터 내 말을 충실히 시행하고 한 순간도 게을리 하지 말아라. 만일 게을리 하는 일이 있으면 그 때는 이 사원의 탑도 무너지고 세계는 종말을 고하게 되리라."
브라만교의 스님들은 어떻게 했을까? 사원이 무너지지 않게 하기 위하여 부지런히 원판을 옮기기 시작했을 것이다. 그러면 이 64개의 원판을 옮기려면 원판을 몇 번이나 이동시켜야 할까?
문제를 간단히 풀기 위하여 우선 원판의 개수를 줄여보자.
만약 원판이 1개라면 이것을 옮기는 데는 1번의 이동으로 충분하다. 만약 원판이 2개라면 3번 이동시키면 된다. 그러면 원판이 3개라면 몇 번 이동시켜야 할까?
위 그림에서 기둥의 이름을 A, B, C라 하자. 작은 원판 2개를 B로 이동시키려면 원판이 2개인 경우와 같이 3번 이동시키면 된다. 그 다음에 가장 큰 원판을 C로 옮기고(1번) 다시 B에 있는 원판 2개를 3번 이동하면 C로 옮길 수 있다. 곧 3+1+3 = 7(번) 옮기면 된다.
이것을 정리하면 n개의 원판을 옮기려면 n-1개의 원판을 옮기는 횟수의 2배의 1을 더한 횟수만큼 이동시키면 된다는 것을 알 수 있다.
이제 원판이 4개, 5개 있을 때의 이동 횟수를 계산한 후, 그 횟수의 규칙을 찾아보자. 과연 브라만의 스님들은 언제쯤 이것을 완성할 수 있을까….
.