하노이 탑(Tower of Hanoi)

배한길 info.elc09@gmail.com 글쓴이의 다른 글 보기

최종수정 : 2012-08-27 07:05

오늘은 가족과 함께 같이 할수있는 수학 관련 게임 한 가지 소개 합니다.

바로 “하노이 탑(Tower of Hanoi)”라는 게임입니다. 이 게임은 퍼즐의 일종입니다. 생김새는 아래 그림과 같습니다. 이 게임은 세개의 기둥과 이 기둥에 꽂을 수 있는 다양한 크기의 디스크들로 구성되어 있습니다. 게임을 시작하기 전 한 기둥에 이 디스크들을 큰것이 바닥으로 갈수 있도록하여 가장 작은 디스크가 맨 위에 갈수 있도록 쌓아 놓습니다. 이 게임은 캐나다 고등학교 과정중 “Geometric Sequence”(등비수열:같은 비율로 계속하여 증가하거나 감소하는 규칙을 갖는 수의 나열) 와 연관이 있습니다.

게임의 룰은 아주 간단합니다. 한기둥에 꽂힌 디스크들을 그 순서 그대로 다른 기중으로 옮겨서 다시 쌓는 것입니다. 물론 충족해야 할 규칙들이 몇가지 있습니다. 첫째 한번에 하나의 디스크만을 옮길수 있다. 둘째 큰 디스크는 그 보다 작은 디스크 위에 위치 할 수 없다. 그럼 이 두 규칙을 잘 생각 하시면서 한 번 같이 해 보도록 하겠습니다.

한기둥위에 3개의 디스크가 있습니다(그림 참조). 이 디스크들을 다른 기둥으로 옮기는 방법은 그림에 자세히 설명 되어 져 있기 때문에 생략하기로 하구요. 저는 단지 몇번에 걸쳐서 이와 같은 방법이 이루어 졌는지에 촛점을 맞추도록 하겠습니다. 아마도 7번의 움직임으로 위의 조건을 만족하면서 디스크들을 다른 기둥으로 옮기셨을거라 생각합니다. 그렇다면 4개의 디스크가 있을때는 어떻까요? 또 다른 예로 디스크가 64개 가 있으면 몇번의 움직임이 있어야 할까요?

일반적으로 디스크가n개 일 때, 2ⁿ -1번의 이동으로 디스크들을 모두 옮길 수 있습니다. 수학에서 이2ⁿ − 1는 메르센 수라고 부릅니다. 다시 설명 드리면 우리가 이전에 같이 풀어본 디스크 3개의 경우 2³-1 이 되어 8-1로 7 이라는 답을 얻을수 있습니다.

참고도 디스크를 옮기는데 얼마의 시간이 걸릴까요? 디스크를 한 번 옮기는데 1초가 소요된다고 가정했을때 위와 같이 디스크가 3장이라면 대략 7초가 걸릴것입니다. 그런데 만약 디스크가 64장 이라면 어떨까요? 64개의 디스크를 옮기는데 약 1844경6744조737억955만1615번을 움직임이 필요하고, 한번 옮길 때 시간을 1초로 가정했을때 64개의 원판을 옮기는데 5849억 4241만 7355년 걸린다.