A, B, C 세 개의 기둥 중 한 곳에 순서대로 놓여 있는 원판을 그대로 다른 기둥으로 옮기는 게임으로 한 번에 1개의 원판만을 옮길 수 있고, 옮기는 도중 큰 원판이 작은 원판 위로 올라갈 수는 없다.

하노이의 탑은 원래 수학 문제에서 기원해, 게임으로 만들어졌다. 시중에 판매되는 게임은 보통 10개의 원판으로 구성돼 있다. 미리 알면 흥미가 반감될 수도 있지만, 심심풀이 삼아 10개 원판을 옮기는 데는 얼마나 걸릴까? 한번도 안 틀린다 해도 (2¹⁰-1)번, 즉 1,023번을 옮겨야 한다.

즉, 한 기둥에 꽂힌 원판들을 그 순서 그대로 다른 기둥으로 옮겨서 다시 쌓는 식이다. 한 번에 하나의 원판만 옮길 수 있고 큰 원판이 작은 원판 위에 있어서는 안 된다. 하노이의 탑은 1883년 프랑스 수학자 루카(Edouard Lucas)가 고안한 것으로 인도의 전설에서 유래됐다.

태초에 인도의 갠지스강 기슭에 브라만교의 베나레스 사원이 있었다. 신은 천지를 창조하면서 세계의 중심이라 여겼던 사원에 구리로 만든 동판 바닥에 50cm정도 되는 다이아몬드로 된 3개의 막대 기둥을 세웠다.

그리고 기둥 하나에 구멍이 뚫린 크기가 다른 순금으로 만든 64개의 원판을 크기가 큰 것부터 아래에 놓이도록 차례로 쌓아놓았다. 어느 날 신이 승려들에게 밤낮으로 쉬지 말고 일해서 빈 기둥 중 어느 한곳에 64개의 원판을 원래 상태대로 모두 옮겨 놓으라고 명령한다.

“한 번에 하나씩 옮겨야 하고 큰 원판이 작은 원판 위에 놓이면 안 되며 게으름 피우는 일 없이 열심히 옮기면 이 원판을 모두 옮길 때까지 세상은 평화로울 것이다. 64개 원판이 모두 다른 기둥으로 옮겨졌을 때 비로소 사원은 연기처럼 사라지고 세상엔 종말이 올 것이다.”

신의 말처럼 승려들이 매우 빠르게 움직여 매초에 한 개씩 옮긴다면 전부 옮기는데 얼마나 걸릴까? 원판이 겨우 64개여서 쉽게 보이지만 간단한 문제가 아니다. 원판의 개수가 1개일 때는 이동횟수는 1회, 원판의 개수가 2개일 때는 이동횟수는 3회(맨 위의 한 개를 옮긴 후 밑에 것을 옮기고 다시 맨 위의 것을 옮김),

원판의 개수가 3개일 때는 이동횟수는 7회(맨 위의 두개를 옮기고 밑에 것을 옮기고 다시 맨 위의 두개를 옮김), 같은 방법으로 원판의 개수가 4개일 때는 이동횟수는 15회, 원판이 n개 일 때는 이동횟수는 ‘2의 n제곱-1’번이 된다.

따라서 하노이의 원판 64개를 옮기는 최소횟수는 ‘2의 64제곱-1’, 약 1844경6744조737억955만1615번을 움직여야 한다. 시간 상으로 약 5850억년이 걸리는 것이다. 전설대로라면 세상의 종말이 오기까지는 아직 엄청난 시간이 남아있는 셈이다.

하노이의 탑은 수학자, 퍼즐 애호가들에게 많은 관심거리가 되고 있다. 1인용 수학게임으로 영재교육 프로그램에 많이 이용되며 창의력 발달과 규칙성을 발견함으로써 수학적 문제해결 능력을 향상시킨다. 또한 어린이들에게는 손가락 반복동작을 통해 촉각 및 인지능력을 키울 수 있다.