하노이탑의 원판 3개 최소 이동횟수

[안도산]

Towers of Hanoi, Towers of Brahma라고도 함.

3개의 수직기둥과 이 기둥에 꽂을 수 있도록 중앙에 구멍이 있는 다양한 크기의 원판 1벌로 구성된 퍼즐 게임.

 하노이 탑은 1883년에 프랑스의 수학자인 에두아르 뤼카가 발명한 것으로 널리 알려져 있지만, 발명에 기여한 그의 역할에 대해서는 논란이 있다. 목재나 플라스틱으로 만들어진 하노이 탑은 전세계 장난감 가게에서 볼 수 있다.

일반적인 장난감 세트는 받침대를 고정시키는 3개의 기둥과 중앙에 구멍이 있는 8개의 원판으로 구성된다. 반지름이 모두 다른 원판들은 처음에 가장 큰 원판이 맨 아래쪽에, 가장 작은 원판이 맨 위쪽에 놓이도록 1개의 기둥에 순서대로 쌓여 꽂혀 있다.

 게임의 과제는 2가지 규칙에 따라 한쪽 기둥에 꽂혀 있는 원판들을 다른 기둥으로 옮겨서 쌓는 것이다.

 첫 번째 규칙은 1번에 1개의 원판만 옮겨야 한다는 것이고,

 두 번째 규칙은 큰 원판이 더 작은 원판 위에 놓여서는 안 된다는 것이다.

  탑을 쌓기 위한 n개의 원판은 탑을 다른 기둥에 완벽하게 옮기기 위해 각 각  2^{n -}1번 이동해야 한다. 그러므로 8개의 원판을 옮기려면 2^8-1, 즉 255번을 이동해야 한다. 만약 원래의 '바늘'(기둥)이 64개의 원판으로 쌓은 탑이었다면, 이동 횟수는 2^64-1인 18,446,744,073,709,551,615번이 될 것이다. 이것은 64개의 칸으로 나뉘어진 장기판 첫째 칸에 낟알 1개, 둘째 칸에 낟알 2개, 다음 칸에 4개, 8개, 16개, 32개 등으로 밀의 낟알을 채워 넣을 때 요구되는 숫자와 정확히 같은 숫자이다.

 분명하지는 않지만, 하노이 탑의 유래에 대해 전해지는 바에 따르면 베트남 또는 인도의 사원이나 수도원에서 승려들이 수세기 동안 3개의 기둥 사이를 이리저리 오가며 순금 원판을 옮긴 데서 유래되었다고 한다. 마침내 승려들이 모든 원판을 옮기는 일에 성공했을 때 세상은 종말을 맞이하게 되었다고 한다. 전설에 대한 다양한 이야기 사이의 공통점은 하루에 1번씩만 옮길 수 있었다는 것이다. 1번 옮기는 데 1초가 걸린다고 하더라도 과제를 완성하려면 5,000억 년 이상이 걸린다.

 끝내는 것이 불가능한 승려들의 임무는 미국의 에릭 프랭크 러셀이 쓴 고전 과학 소설 〈Now Inhale〉(1959)에서 희극적인 결과로 인용되었다. 소설에서 주인공은 외계행성에서 처형되기 전에 지구로부터 게임 하나를 할 수 있도록 허락을 받는다.