19세기 말 프랑스 수학자 Lucas가 제안 전설 Benares(베트남 하노이 외곽)에는 세계의 중심이 있고, 그 곳에는 아주 큰 사원이 있다. 이 사원에는 높이 50cm 정도 되는 다이아몬드 막대 3 개가 있다. 그 중 한 막대에는 천지 창조 때에 신이 구멍이 뚫린 64 장의 순금으로 된 원판을 크기가 큰 것부터 아래에 놓이도록 하면서 차례로 쌓아 놓았다. 그리고 신은 승려들에게 밤낮으로 쉬지 않고 한 장씩 원판을 옮기어 빈 다이아몬드 막대 중 어느 곳으로 모두 옮겨 놓도록 명령하였다. 원판은 한 번에 한 개씩 옮겨야 하고, 절대로 작은 원판 위에 큰 원판을 올려 놓을 수 없다. 64개의 원판이 본래의 자리를 떠나 다른 한 막대로 모두 옮겨졌을 때에는 탑과 사원, 승려들은 모두 먼지가 되어 사라지면서 세상의 종말이 온다.
체험: http://www.mazeworks.com/hanoi/index.htm http://www.cut-the-knot.org/recurrence/hanoi.shtml
재귀적 해법 n 개의 원판을 옮기려면 위쪽에 있는 (n-1) 개의 원판을 모두 다른 막대로 옮긴 후에 맨 아래 원판을 빈 막대로 옮기고, 다시 그 위에 (n-1) 개의 원판을 옮겨 놓으면 된다
최소 이동(Move) 회수의 계산 직관적 방식 원판의 이동 회수를 TN 이라고 하면, 앞의 해법에 근거하여, TN = TN-1 + 1 이다. SN = TN + 1 이라고 하면, S0 = 1 이고 SN = TN + 1 = (2TN-1 + 1) + 1 = 2TN-1 + 2 = 2(TN-1 + 1) = 2SN-1. 따라서 아래와 같이 정의할 수 있다. S0 = 1 SN = 2SN-1 for N>0 이며, 따라서 SN=2N 이고, TN = 2N-1 이다.
귀납적 방식 (inductive reasoning) 원판의 이동회수를 P(n)이라고 하면, 앞의 해법에 근거하여, P(n) = 2 P(n-1) + 1 P(1) = 1 P(2) = 2 P(1)+1 = 2+1 = 3 P(3) = 2 P(2)+1 = 2x3+1 = 4+2+1 = 7 P(4) = 2 P(3)+1 = 2x7+1 = 8+4+2+1 = 15
등비수열의 합 공식을 이용하면, 일반적으로
Inductive reasoning의 추가 사례 A(1) = 2 A(2) = 2 + 2 … n개의 직선으로 분할된 평면의 영역의 개수 A(n) A(1) = 2 A(2) = 2 + 2 … 이므로, A(n) = A(n-1) + n (n은 2 이상인 자연수) 이고, A(n) = 2 + 2 + 3 + 4 + … + n = (n2 + n + 1)/2
하노이의 탑 이동 회수의 의미 원래의 하노이탑 문제의 경우는 n = 64 인 경우이므로 필요한 원판의 이동 총수 (이것은 가장 최소의 이동 회수를 의미하며, 만약 이동순서를 잘못하면 그만큼 이동회수는 늘어 난다)는 P(64) = 263 – 1=18,466,744,073,709,551,615 이며, 이는 약 1847 해 만큼의 이동이 필요하며, 만약 1번의 움직임에 1초가 걸린다고 가정하면, 대략 5000억년 이상이 걸리게 된다. 따라서 이 게임이 끝나게 되면 5000억년 이상의 시간이 경과한 이후이며, 태양은 50억년 후에 적색거성으로 부풀어 올라 태양계의 생명체가 사라지게 되므로, 지구의 운명도 끝이 난 이후일 것이다.