하노이 탑의 일반항을 구하기

하노이 탑의 일반항을 구하기

 

옛날 베트남의 수도 하노이에 있는 한 불교 사원이 있었는데, 사람들이 이 사원이 세계의 중심이라고 믿었다. 그 곳에는 높이가 50cm 정도 되는 다이아몬드 막대기가 3개 있었고, 그 중 한 막대기에는 순금으로 된 원판 64개가 큰 것부터 작은 것이 크기의 순서에 따라 가장 큰 것이 맨 아래, 가장 작은 것이 맨 위에 쌓여 있었다.

이 사원에는 대대로, 다이아몬드 막대기에 쌓여 있는 64개의 원판을 빈 막대기 중 하나에 옮기면 지구는 연기와 같이 우주 공간으로 사라진다는 말이 전해지고 있었다. 단, 원판을 옮기는 데는 몇 가지 지켜야할 규칙이 있는데 첫째, 원판은 한 번에 1개씩 옮겨야 하며, 둘째 큰 원판이 작은 원판 위로 올 수는 없다.

 

그럼 과연 이러한 규칙에 의해서 64개의 원판을 빈 막대기 중 하나에 옮길 수 있는 방법의 수는 과연 몇 가지가 될 것이지를 생각해 보자.

첫 번째로 원판의 개수에 따른 최소 시행횟수를 찾도록 하고, 두 번째로 최소 시행 횟수를 기초로 문제에 내제된 수학적 법칙을 추정하여 일반항을 구한다.

* 주의 : 반드시 원판 중 큰 것이 아래에 놓이도록 해야 한다.

 

■ 해법

(1) 원판의 개수에 따른 시행 횟수 구하고 추정하기 (실험을 통해 구하기)

원판의 수	1	2	3	4	5	6	7	…	n
최소 이동횟수	1	3	7	15	31	63	127
추정하기	2-1

(2) 원리 찾기

   : (n-1)개의 원판이 옮겨지는 횟수라 하자

   : n 개의 원판이 옮겨지는 횟수라고 하자.

 

<원리를 찾아보자>

n 개의 원판을 옮기는 횟수 은 (n-1)개의 원판을 B 막대기에 옮기는 횟수 , 가장 밑에 있는 원판 1개를 C 막대기에 옮기는 횟수 1 , 그리고 다시 B 막대기에 있는 (n-1)개의 막대기를 C 막대기에 옮기는 횟수  의 합으로 나타낼 수 있다.

총이동 횟수 :

{A→B로 (n-1) 개 이동} + { A→C 1개 이동} + { B→C 로 (n-1)개 이동}

 

(3) 일반항 구하기

여러 가지 수열의 일반항을 구하는 요령으로 일반항을 구할 수 있다.

을  로 변형

( )

 

(4) 하노이 탑을 통해 여러 가지 수열에 대한 문제를 일상생활과 연관시켜 생각할 수 있고 스스로 직접 해결할 수 있는 능력을 기른다. 위의 하노이 탑의 일반항이 이므로 64개의 원판을 옮기는 경우의 횟수가 =18,446,744,073,709,551,615 라는 아주 큰 수가됨을 알 수 있다.

예를 들어 원판 1개를 옮기는데 1초가 걸린다고 가정하면 1년은 365×24×60×60=31,536,000회를 시행할 수 있다. 이런 식으로 64개의 원판을 옮기는데 소요되는 시간을 계산하면 약 5,833억년이 걸린다.