하노이의 탑: 유래와 역사

큰 원반이 작은 원반 위에 올라가지 않도록 움직이면서 막대에 끼워진 원반을 다른 막대로 옮기는 하노이의 탑(Tower of Hanoi) 퍼즐은 고안된지 120년이 지난 지금까지도 퍼즐 애호가, 수학자, 전산과학자들에게 많은 관심거리가 되고 있다. 이 퍼즐을 처음 만든 것은 1883년 '클라우스 교수'(Professor Claus)라는 이름의 인물이다. 이것은 받침대에 나무 막대 3개가 박혀 있고, 이 중 하나에 반지름이 다른 원반 8개가 크기 순서대로 쌓여 있는 것이었다. 이 퍼즐의 목표는 큰 원반을 작은 원반 위에 놓을 수 없다는 제약 아래 한 번에 맨 위에 있는 원반 1개씩만 움직여서 탑 전체를 다른 막대로 이동하는 것이다. 1884년, 드 파빌(H. de Parville)이 '클라우스'(Claus)가 '뤼카'(Lucas)―수학 게임이나 퍼즐에 관심이 많았던 정수론학자 에두아르 뤼카(Edouard Lucas, 1842-1891)―의 철자를 바꿔쓴 것임을 밝혔다. 하노이의 탑 퍼즐이 유명해진 것은 분명 신화상의 브라만의 탑(Tower of Brahma)에 대한 드 파빌의 글 덕분인데 여기서는 하노이의 탑이 브라만의 탑을 본뜬 것으로 나온다.(주 1) 드 파빌의 글에서는, 3개의 다이아몬드 막대와 64개의 황금 원반 탑이 있고, 일단의 브라만 승려들이 앞서 설명한 규칙에 따라 탑을 옮기려고 하며, 승려들이 탑을 완전히 옮기면 세계는 종말을 맞게 될 거라고 나온다. 이 종말론적인 이야기는 라우즈 볼(W. W. Rouse Ball)과 가드너(Martin Gardner)가 좀더 상세한 형태로 썼다. ※주 1: 물론 브라만의 탑은 화려한 전설일 뿐이지만, 하노이의 탑은 실제로 존재한다. 비록 파리에서 퍼즐 형태로 소개되었으나, '하노이의 탑'이라는 이름으로 알려진 고대 유물이 하노이의 한 사원 터에 존재한다. 이 건조물과 뤼카가 고안한 퍼즐 사이의 연관성에 대해서는 그저 추측만 할 수 있을 따름이다. (원주) 하노이의 탑 퍼즐의 풀이는 1884년 앨러디스(R. E. Allardice)와 프레이저(A. Y. Fraser)가 처음 수학 논문으로 발표했다. 사실, 원반 n개가 쌓인 탑을 수학적으로 추상화하면, 탑을 한 막대에서 다른 막대로 옮기는 데 필요한 이동 횟수를 구하는 것은 그렇게 어렵지 않다. 이 문제는 이산수학 기초 과정 연습 문제로 자주 나온다. 먼저 위쪽의 원반 n - 1개짜리 탑을 다른 막대로 옮겨놓은 다음 탑을 옮기려는 막대로 가장 큰 원반을 옮기고 나머지 원반 n - 1개를 가장 큰 원반 위로 옮겨놓으면 되므로 원반 n개짜리 탑을 옮기는 데 필요한 이동 횟수를 hn으로 표기하면 다음과 같은 점화식을 얻는다. hn = 2hn-1 + 1 여기서 h1 = 1(또는 h0 = 0)이다. 위 점화식을 풀거나 수학적 귀납법을 이용하면 잘 알려진 풀이 hn = 2n - 1 이 나온다(따라서, 브라만 승려들이 원반 1장을 1초에 옮긴다고 해도, h64는 5천 8백억년이 넘으니까, 한 동안 세계는 안전할 것이다!). 문제에서는 암묵적으로 hn이 최소 횟수여야 한다고 가정하고 있지만, 위 풀이에서는 정말로 2n - 1이 최적해인가는 보여주지 못하고 있다. 이와 관련된 증명은 1981년에야 발표되었다―아마 그때까지는 아무도 그런 증명이 필요하다고 생각지 않았을 것이다. 최근 여러 해 동안, 하노이의 탑 문제에 대한 여러 가지 별해나 새로운 관찰 결과가 발견되었다. 크로우(D. W. Crowe)는 하노이의 탑 문제를 푸는 것이 n차원 초입방체의 해밀턴 경로(Hamiltonian path)(주 2)를 구하는 것과 동등함을 보였고 원반의 이동을 나타내는 열(sequence)을 오늘날 이진 그레이 코드(binary Gray code)(주 3)라 부르는 도구를 써서 나타낼 수 있다는 것은 뤼카 자신도 알고 있었을 것으로 추측된다. 하노이의 탑의 역사나 풀이 기법에 대해서 더 자세히 알고 싶으면 다음 문헌들을 참고하기 바란다. Martin Gardner, The Scientific American Book of Mathematical Puzzles and Diversions, Simon and Schuster, New York, 1959; revised edition, Hexaflexagons and Other Mathematical Diversions, Univ. of chicago Press, Chicago, 1988. A. K. Dewdney, The Armchair Universe, W. H. Freeman, New York, 1986. A. M. Hinz, "The Tower of Hanoi," Enseign. Math. 35 (1989), 289-321.