[하노이탑]하노이탑의 유래 2

하노이탑, 하노이의탑, 하노이탑게임, 가베놀이, 명심보감하노이탑, 하노이, 하노이탑규칙, 하노이타워, 소마큐브, 하노이탑 C++, c언어하노이탑, 하노이탑 소스, 하노이탑 c, 하노이 탑, 하노이의 탑, 하노이의 탑 게임, 하노이탑의 유래

큰 원반이 작은 원반 위에 올라가지 않도록 움직이면서 막대에 끼워진 원반을 다른 막대로 옮기는 하노이의 탑(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개짜리 탑을 옮기는 데 필요한 이동 횟수를 h_n으로 표기하면 다음과 같은 점화식을 얻는다.

h_n = 2h_n-1 - 1

여기서 h₁ = 1(또는 h₀ = 0)이다. 위 점화식을 풀거나 수학적 귀납법을 이용하면 잘 알려진 풀이

h_n = 2ⁿ - 1

이 나온다(따라서, 브라만 승려들이 원반 1장을 1초에 옮긴다고 해도, h₆₄는 5천 8백억년이 넘으니까, 한 동안 세계는 안전할 것이다!). 문제에서는 암묵적으로 h_n이 최소 횟수여야 한다고 가정하고 있지만, 위 풀이에서는 정말로 2ⁿ - 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.

(주 2: 그래프 이론 용어. 그래프 위의 두 점을 이은 경로 중에서 모든 점을 한 번씩 지나는 경로를 해밀턴 경로라 한다. 참고로 모든 점을 다 지나고 출발점으로 돌아오는 경로를 해밀턴 순환로(Hamilton circuit)라 하며 조합론, 전산수학에서 중요하게 다루는 순회 세일즈맨 문제(Traveling Salesman's Problem)과 관계가 있다.)
(주 3: 컴퓨터에서 문자 데이터를 표현하는 코드의 한 종류로 숫자가 증가할 때 항상 1개의 비트(bit)만 변화한다. 2진 코드(BCD)를 그레이 코드로 변환하는 과정은 다음 URL에서 읽을 수 있다.)
http://ns.shingu-c.ac.kr/~nsbaek/comp/gray.htm

최근에는 전산과학 분야에서 하노이의 탑에 대한 흥미가 살아나는 경향이 있다. 이들 중 대부분은 문제 해결에서 반복적(iterative) 알고리듬과 재귀적(recursive) 알고리듬 중 어느 쪽이 상대적으로 나은가를 둘러싼 논쟁과 관련되어 있다. 전산과학 교과서에서는 하노이의 탑을 프로그래밍 연습문제로 싣는 일이 흔하다.

한편 이언 스튜어트(Ian Stewart: 영국 수학자. 한국에서는 카오스 이론 관련 서적의 저자로 알려져 있다)는 각각의 원반이 배치된 상태를 (1, 1, 1), (1, 2, 3) 등의 순서쌍으로 표시하고, 이들 순서쌍을 점에 대응시키고 각각의 상태에서 원반을 움직여서 만들 수 있는 상태끼리 선으로 연결한 하노이 그래프(Hanoi Graph)를 고안했다. 하노이 그래프는 원반의 개수에 따라 H_n으로 표시하는데 아래 그림은 H₃을 나타낸다.)

(사진 출처: http://icl.pku.edu.cn/yujs/MathWorld/math/h/h059.htm)
하노이의 탑 퍼즐은 하노이 그래프의 어느 한 꼭지점에서 다른 꼭지점으로 가는 최단 경로를 찾는 문제와 같아지며 이 방법으로 풀어도 최소 이동 횟수는 2ⁿ - 1임을 확인할 수 있다. 또한 하노이 그래프는 n이 증가함에 따라 프랙탈 기하학에서 등장하는 시에르핀스키 삼각형(Sierpinski triangle)^{(주 4)}과 비슷한 모양이 된다.
(주 4: 시에르핀스키 개스킷(Sierpinski gasket)이라고도 한다.)


【원문 출처】
1. David G. Poole, "The Towers and Triangles of Professor Claus (or, Pascal Knows Hanoi)", Mathematics Magazine, Vol. 67, No. 5 (December 1994), pp. 323-344.
2. 박부성, ≪재미있는 영재들의 수학 퍼즐≫(자모사이언스 14), 자음과 모음, 2001.


출처: http://blog.naver.com/mskim13/120004667156


[하노이탑 제품보기]