[김대수의 수학 어드벤처] 하노이탑 문제 푸는 데 무려 5845억 년?

오래전부터 전해 내려오는 어려운 수학 문제를 풀기 위한 수학자들의 노력은 지금까지도 계속돼 왔다. 거액의 현상금이 걸린 흥미로운 문제들도 여러 개 있는데 그중의 하나가 하노이 탑(Tower of Hanoi) 문제다.

하노이 탑 문제는 그림에서와 같이 각각 다른 크기의 원반들이 한 막대에 크기 순서대로 쌓여 있을 때, 어떻게 하면 이들을 다음 규칙을 지키면서 다른 막대로 옮길 수 있느냐는 것이다.

▶ 원반들은 다른 막대로 한 번에 하나씩만 이동할 수 있다.

▶ 맨 위에 있는 원반만 이동할 수 있다.

▶ 작은 원반 위에 큰 원반이 놓일 수 없다.

▶ 중간의 막대를 임시적으로 이용할 수 있으나 앞의 조건들을 지켜야 한다.

3개의 원반으로 이루어진 하노이 탑 문제를 해결할 수 있는 풀이 과정은 다음과 같이 7단계에 걸쳐 이루어진다.

(1) 원반 1을 A에서 C로 옮긴다.
(2) 원반 2를 A에서 B로 옮긴다.
(3) 원반 1을 C에서 B로 옮긴다.
(4) 원반 3을 A에서 C로 옮긴다.
(5) 원반 1을 B에서 A로 옮긴다.
(6) 원반 2를 B에서 C로 옮긴다.
(7) 원반 1을 A에서 C로 옮긴다.

하노이 탑 문제는 다음과 같은 전설에 그 근거를 두고 있다. 고대 인도의 베나레스(Benares)라는 지방의 아주 큰 불교사원에는 다이아몬드 막대가 3개 있었다고 한다. 그중 한 다이아몬드 막대에는 크기가 모두 다른 64장의 순금 원반이 큰 것이 아래에 놓이도록 순서대로 쌓여 있었다.

그런데 신은 승려들에게 밤낮으로 쉬지 않고 원반을 한 장씩 옮겨 빈 다이아몬드 막대 중 어느 한 곳으로 모두 옮겨놓도록 명령하였다. 그런데 원반은 한 번에 한 개씩만 옮겨야 하고, 작은 원반 위에 큰 원반을 절대로 올려놓을 수 없다는 규칙에 따라야 했다.

1883년 프랑스의 수학자 에두아르 뤼카(Edouard Lucas·1842~1891)는 이 하노이 탑의 이동 문제를 푸는 사람에게 1만 프랑의 상금을 지불하겠다고 선언했었다. 이 문제를 풀기 위해서는 시간이 얼마나 걸릴까?

1초에 1번씩 원반을 옮긴다고 가정해도 (2의 64승 - 1)초가 걸리는데, 이것을 연 단위로 환산하면 약 5845억 년이다. 실제 원반을 옮기면서 이 문제를 풀 수 있음을 보여주고 현상금을 타는 일은 아예 불가능한 일이었다.

이와 같이 복잡한 수를 첨단의 수퍼컴퓨터에서 계산한다면 1시간 내에도 가능할 것이니 과학기술의 발전이 그저 놀라울 따름이다.

[문제 1]에서는 정삼각형의 세변의 중앙을 잡아 수직으로 그은 무게중심과 연결하면 되며, 정사각형의 경우에는 가로 또는 세로로 3등분하면 된다.

[문제 2]에서는 네 개의 5와 다섯 개의 5를 사용해 창의성을 발휘할 수 있는 문제로 다양한 발상을 이용해 풀 수 있을 것이다.

[문제 3]에서는 모두 6개의 선으로 연결된 관계로부터 일정한 규칙을 발견하면 될 것이다.