구체 수학 - #1.1 하노이의 탑

첫 번째 장은 재귀적인 문제들에 대한 내용이다.

 

그중에서 첫 번째인 하노이의 탑은 알고리즘 혹은 수학 분야에서 꽤 유명한 문제 중에 하나다.

 

원반 여덟 개로 된 탑에서 시작하고

원반들은 세 개의 기둥 중 하나에 큰 것부터 크기순으로 쌓여있다. (꼭대기에 제일 작은 선반이 놓이도록)

원반을 하나씩 이동해서 탑 전체를 다른 기둥으로 옮기는 게 이 퍼즐의 목표다.

(단, 작은 원반 위에 큰 원반을 놓아서는 안됨)

 

해가 존재하는 걸 찾기보다는

해가 존재는 할 텐데, 그중 가장 최선의 해는 무엇인지, 다시 말해 충분한 이동 횟수는 얼마인지를 구하는 게 핵심이다.

 

이런 질문을 공략하는 가장 좋은 방법은 문제를 약간 더 일반화하는 것이다.

하노이의 탑은 원반이 8개인데, 이를 n개인 경우를 고찰해보자.

 

일반화의 한 가지 장점은 문제의 규모를 훨씬 줄일 수 있다는 점이다.

실제로 작은 사례(small case) 들을 살펴보는 것이 유익한 경우가 자주 나온다.

원반이 하나나 둘밖에 없는 탑을 옮기는 방법은 아주 쉽다.

그리고 약간의 실험을 거치면, 원반이 세 개인 탑을 옮기는 방법도 파악이 가능하다.

 

다음 단계는 적절한 표기법을 도입하는 것이다. name and conquer.

한 기둥에서 원반 n개를 다른 한 기둥으로 옮기는 데 필요한 최소 이동 횟수를 Tn으로 표기하자. 그러면

T1 = 1, T2 = 3은 쉽게 구할 수 있다.

또한 T0 = 0 임도 알 수 있다.

엄청 당연한 이야기 같지만 똑똑한 수학자들은 작게 생각하는(think small)을 부끄러워하지 않는다.

극단적인 사례들을 잘 이해하고 나면(자명한 사례들이라도) 일반적인 패턴을 파악하기가 쉬워진다.

 

그러나 이번에는 크게 생각하는(think big) 쪽으로 관심을 바꾸어, 높은 탑을 옮기는 방법을 고찰하자.

 

원반 세 개짜리 탑으로 실험을 하면

최상위 두 원반을 가운데 기둥으로 옮기고

마지막 원반을 셋째 기둥으로 옮기고

다른 두 원반을 셋째 기둥으로 옮기면 된다.

 

먼저 가장 작은 원반 n-1개를 다른 기둥으로 옮기고(필요한 이동 횟수는 Tn-1)

가장 큰 원반을 또 다른 기둥으로 옮기고(필요 이동 횟수 1)

마지막으로 가장 작은 원반 n-1개를 가장 큰 원반 위로 옮기는 것이다(필요 이동 횟수 Tn-1)

 

따라서 원반 n개의 이동 횟수는 2*Tn-1 + 1을 넘지 않는다.

 

이런 식으로 점화식을 구하는 방법에 대해 소개한다.

 

어떤 관심 잇는 수량의 닫힌 형식 공식을 찾을 때 아래의 세 단계를 거친다.

1. 작은 사례를 살펴봄.

2. 관심 잇는 수량에 대한 수학 공식을 구하고 증명을 만듦.

3. 그 수학 공식의 닫힌 형식을 구하고 증명

 

이 책 전반에서 가장 초점을 두는 건 3번째 단계. 사실 1,2 단계를 건너뛰는 경우도 많음.

 

책의 마지막에서 하노이 탑의 점화식을 '추측'하지 않고(귀납적 비약을 사용해서) 해를 구하는 방법을 소개한다.