하노이 탑 (Tower of Hanoi) 퍼즐에 얽힌 놀라운 이야기

하노이 탑 (Tower of Hanoi) 퍼즐은 아래와 같이 생겼습니다.
아주 심플한 퍼즐입니다.

위 사진에서 알 수 있듯이 일정한 판 위에 3개의 막대가 고정되어 있습니다. 지름이 약간씩 다른 원반이 여러개 있고 그 중심에 구멍이 뚫려 있어 작은 지름의 원반이 위에 오도록 하여 맨 왼쪽의 막대에 원반들이 꽂혀 있습니다.
이 퍼즐의 미션은 모든 원반을 다른 막대로 옮기는 것입니다.
여러 사람이 할 경우에는 최소의 이동 횟수를 기록한 사람이 이기는 것이겠죠.
단 규칙이 있습니다.

① 1회에 한 개의 원반밖에 이동할 수 없다.
② 이동은 막대에서 막대로 이루어진다.
③ 작은 원반 위에 큰 원반을 올려놓을 수 없다.

그런데 이 퍼즐에는 다음과 같은 전설이 있다고 합니다.
옛날옛적 인도 카시 비슈와나스 (Kashi Vihswanath)에 있는 브라만교 대사원에 하노이 탑이 있었습니다.
이 하노이 탑은 세 개의 다이아몬드 기둥이 있는데,
신(Brahma) 이 이 세상을 창조할 때 64개의 순금 원판을 이 기둥 중 하나에 쌓아 놓았다고 합니다.
이 원판들은 크기가 큰 것이 아래에 놓이고 작은 것이 위에 놓이도록 차례로 쌓여 있는데
신은 브라만 승려들에게 두가지 원칙을 제시하며 승려들에게 원판을 옮기라고 합니다.
첫째, 원판은 한번에 한개씩만 옮겨야 한다.
둘째, 작은 원판 위에 큰 원판을 올려놓을 수 없다.
이렇게 해서 64개의 원판이 모두 다른 기둥으로 옮겨졌을 때, 이 세상의 종말이 오게 된다고 했다고 합니다.
전설속의 승려는 지금 이순간에도 원판을 룰에 의해 하나씩 하나씩 옮기고 있는 중이구요.

이 전설에 의하면 지구의 종말은 언제쯤 가능할까요?
왠지 모르게 가까운 시일 내에 원판을 다 옮겨서 세상이 멸망할 것 같은 불길한 느낌이 엄습합니다.

그러나 이 전설이 설사 맞다 할 지라도 걱정 붙들어 매도 됩니다.
왜냐하면 64개의 원판을 다른 다이아몬드 기둥으로 옮기기 위해서는 엄청난 세월이 소요되기 때문입니다.

이게 무슨 말인지에 대해서 좀더 자세히 살펴보겠습니다.

이 하노이의 탑 퍼즐의 해법 관련해서는 이미 수학적으로 증명이 되어 있습니다.
예전에 'http://puzzlemuseum.tistory.com/206' 코너에서 간단히 언급했던 누진 이진법 원리입니다.
쉽게 말해서 거듭제곱의 위력입니다. 

원반 수	최소 이동 횟수	최소 이동 횟수 산식
1	1	21−1
2	3	22−1
3	7	23−1
4	15	24−1
5	31	25−1
6	63	26−1
7	127	27−1
8	255	28−1
...	...	2원반수−1

위 표의 맨 아래 행에 표시했지만 하노이 탑 퍼즐의 최소 이동 횟수는 (2^원반수−1) 입니다. 
굳이 이 산식이 아니더라도 원반의 수가 하나씩 늘어남에 따라 거의 두배씩 최소이동횟수가 증가함을 알 수 있습니다. 즉, 원반 수가 증가함에 따라 최소 이동 횟수는 기하급수적으로 급격히 증가한다는 것입니다.

만일 원반의 수가 64개라고 하면 최소 이동 횟수는 2⁶⁴−1 회이며,
1회의 이동에 1초가 걸린다고 가정하면 최소 이동 횟수는 2⁶⁴−1 초로서,
이것을 아라비아 숫자로 표현해 보면 18,446,744,073,709,551,615 초에 해당하며,
이를 연으로 환산하면 5,850억년에 해당하는 수치입니다.
이 수치는 현재 과학적으로 추정하고 있는 태양의 잔여 수명보다도 더 긴 기간이라고 합니다.
실제로 원반을 다 옮기는 때가 오면 이미 이 세상은 종말이 온 것이겠죠.

결과적으로 위의 인도 전설에 나오는 세상의 종말 이야기에 대해서 전혀 걱정할 필요가 없습니다.

이와 유사한 이야기가 하나 더 있습니다.
옛날 인도에 어떤 왕이 있었는데 전쟁을 너무 좋아해서 백성들이 항상 불안에 떨고 있었습니다.
이런 현상을 본 세타라는 승려가 전쟁과 비슷한 규칙을 지닌 체스 게임을 만들어 냈습니다.
서양식 장기인 체스는 가로와 세로 각각 8칸씩 총 64칸으로 이루어진 정사각형의 판 위에 여러 종류의 말을 놓고, 일정한 규칙에 따라 말을 움직이는 게임입니다.
얼마나 많은 말을 보유하고 있는가도 중요하지만,
정작 승패를 판가름하는 것은 어떻게 전략을 짜느냐 하는 것이죠.
다행히 왕은 체스 게임에 흥미를 느껴 전쟁이 아니라 체스로 관심을 돌리게 되었습니다.
왕은 체스 게임을 소개해 준 세타에게 고마움을 표시하기 위해 무엇이든 원하는 것을 말해보라고 합니다.
그러자 세타는 체스판의 첫 칸에 밀 한 알, 둘째 칸에 밀 두 알, 셋째 칸에 밀 네 알과 같이 두배씩 밀알을 늘려 채워달라고 요구합니다.
왕은 세타가 참으로 소박한 승려라고 생각했습니다.
그....러....나,
실제로 체스판을 세타가 말한 방식대로 채우기 위해서 필요한 밀알은 의외로 엄청난 양이었습니다.
즉, 1 + 2 + 4 + 8 + 16 + 32 + ...... + 2⁶² + 2⁶³ 개,
위의 숫자를 모두 더하면 결국 2⁶⁴−1 개의 밀알이 됩니다.
왕은 결국 이 숫자의 밀알을 줄 수가 없게 된 것입니다.
왕의 섣부른 오판, 그리고 세타 승려의 현명함이 돋보이는 대목입니다.

또 이와 유사한 원리로서 신문지 종이를 몇회 접어야 달까지 갈 수 있을까 하는 문제가 있습니다.
즉, 신문지 종이를 반으로 접고, 반으로 접은 것을 다시 다시 반으로 접고 해서 이런 과정을 계속 반복했을 때 과연 몇회만에 지구에서 달까지 도착할 수 있는지의 문제입니다.
상당히 큰 횟수를 생각했겠지만 실상은 42번만 접으면 지구에서 달 표면까지 도착하고도 남아서 56,805km를 더 간답니다.
그리고 43번 접으면 달 표면까지 갔다 다시 지구로 돌아오고도 (왕복하고도) 113,609km가 남게 됩니다.
(여기서의 가정은 신문 종이의 두께가 0.1mm 이고, 달까지의 거리는 383,000km라는 것입니다.) 

이러한 현상이 발생하는 것 모두 누적 이진법 즉 거듭제곱의 힘입니다.
기하급수적으로 늘어나는 숫자는 그 횟수가 커질 수록 엄청난 위력을 발휘하는 것이죠.
0.1mm * 2⁴² = 439,805km
0.1mm * 2⁴³ = 879,609km

그리고 하노이 탑 (Tower of Hanoi) 퍼즐은 브라마의 탑 (Tower of Brahma) 또는 루카스 타워 (Lucas' Tower) 또는 파나마 콘 퍼즐 또는 파나마 디스크 퍼즐 (Panama Cone or Disc Puzzle) 이라고도 불린답니다.
브라마 탑이라고 불리는 이유는 힌두교 최고의 신인 브라마가 이 퍼즐을 만들었다고 해서 주어진 이름이구요.
루카스 타워라고 불리는 이유는 프랑스 수학자인 Edouard Lucas 의 책에 의해 1883년에 서양에서 처음으로 대중에 알려졌기 때문입니다. 위에서 언급한 인도의 전설 속의 세상의 종말 관련한 이야기는 루카스가 한 말입니다. 이 전설을 루카스가 지어낸 것인지, 아니면 실제로 전설이 있고 그 전설에 영향을 받아서 이야기한 것인지는 현재 불분명합니다. 
파나마 콘 퍼즐 또는 파나마 디스크 퍼즐이라고 불리는 이유는 예전에 이 이름으로 아래와 같은 퍼즐이 판매되었기 때문입니다. 

 

그런데 이 하노이 탑 퍼즐을 즐기려면 반드시 퍼즐을 구입해야만 하는 것일까요?
아닙니다.
요즘 인터넷의 발달로 인해 인터넷 상에서 하노이 탑 퍼즐을 가상 체험해 볼 수 있는 프로그램이 많이 있답니다.
http://www.dynamicdrive.com/dynamicindex12/towerhanoi.htm 사이트를 방문해 보시면 하노이 탑 퍼즐을 체험할 수 있는 프로그램을 제공하고 있습니다.
원반을 드래그 앤 드랍하면서 손쉽게 즐길 수 있습니다.
관심 있으신 분들은 한번 방문해 보시지요.

마지막으로 하노이 탑 퍼즐에 대한 각종 이미지를 보여드리겠습니다. 나름 재미있는 구석이 있더군요.

위 퍼즐은 하노이 탑 퍼즐을 나무 상자 안에 정리할 수 있도록 고안된 퍼즐입니다.
퍼즐러 갱이 가지고 있는 것도 이와 유사한 것입니다.

위 퍼즐은 일반적 하노이 탑 퍼즐과는 달리 가운데 있는 나무 기둥을 뱀 모양으로 만들었다는 것이 특징이군요.
그리고 가장 넓은 원반 끝부분을 뱀의 꼬리처럼 처리함으로써 결국,
뱀이 또아리를 틀고 있는 모습으로 만들었다는 것이 참 기발한 아이디어입니다.

 

위 퍼즐은 직사각형의 바닥 대신에 삼각형 모양의 바닥을 가지고 있는 하노이 탑 퍼즐입니다. 가운데의 것은 나름 부드러운 곡선미를 자랑하는군요.

 

위 사진은 하노이 탑이라는 퍼즐 이름에 걸맞게 단순한 원반 대신 탑 형식을 취한 것입니다.
상당히 멋드러진 하노이 탑 퍼즐인 것 같습니다.
진짜 탑 모양을 하고 있는 위의 퍼즐을 꼭 손에 쥐고 싶은 생각이 굴뚝 같습니다.

마지막으로 하노이 탑 퍼즐은 기계적 퍼즐 분류에 의하면 순차이동 퍼즐 (Sequential Movement Puzzle) 에 해당합니다~~

오늘도 해피 퍼즐링~~

- 참고 사이트:
http://cmath_club.blog.me/30138769398
- 관련 포스트:
http://puzzlemuseum.tistory.com/206
http://puzzlemuseum.tistory.com/141
http://puzzlemuseum.tistory.com/180

 

 *아래 화면은 퍼즐러갱이 개설한 유튜브 '퍼즐러갱TV'의 초기화면입니다. 아래 그림을 클릭/터치하여 퍼즐러갱TV를 감상해 보시지요(구독과 좋아요는 저에게 큰 힘을 줍니다)!!