하노이의 탑

2 minute read

하노이의 탑

너무 유명한 문제라 링크로 대체한다.

문제 해결의 순서

일단 답이 존재하는지 판별해야하지만 이 문제에서는 당연히 답이 존재하므로 패스.

최적의 답을 구하는데 가장 좋은 방법은 문제를 일반화 하는 것.
- 그러므로 원반의 개수가 $n$이라고 하자.
- 이런 접근의 장점은 문제의 규모를 훨씬 줄인다는 것.
다음 단계는 명명정복 (name and conquer)
- 원반 $n$개를 옮기는데 필요한 최소의 이동 횟수를 $T_n$이라고 하자.
- $T_1=1$, $T_2=3$이 된다.
- 가장 간단한 경우, 원반이 없는 $T_0=0$임은 쉽게 알 수 있다.
위에 까지는 작게 생각하는 것이고, 이 다음은 크게 생각하는 단계
- 원반이 3개인 경우를 보면, 맨 아래의 원반을 옮기려면 어떻게 해야 하는가?
- 그 원반 위의 2개가 다른 두 기둥을 점유하고 있다면, 가장 큰 원반인 맨 아래의 원반을 어디로든 옮기지 못할 것이다.
- 그러므로 2개의 원반이 하나의 기둥에 모여 있고, 나머지 기둥이 비어있어야 옮길 수 있음을 알 수 있다.
- 그런데, 게임의 목표가 왼쪽 기둥의 모든 원반을 가장 오른쪽 기둥으로 이동시키는 것이므로, 2개의 원반이 모이는 기둥은 가운데여야 하는 것을 알 수 있다.
- 그 다음은 간단하게 될 것이다. 마지막 원반을 오른쪽 기둥으로 옮기고, 가운데 기둥의 2개의 원반을 오른쪽 기둥으로 옮기면 끝이다.
- 그러면 최소로 필요한 이동 횟수는 $T_3 = T_2+T_1+T_2=7$이다.
- 이를 일반화하면, 가장 작은 원반 $n-1$개를 다른 기둥으로 옮기고(필요한 이동 횟수 $T_{n-1}$), 가장 큰 원반을 또 다른 기둥으로 옮기고(필요한 이동 횟수 1), 마지막으로 가장 작은 원반 $n-1$개를 가장 큰 원반 위로 옮기는 것이다 (필요한 이동 횟수 $T_{n-1}$).
이를 식으로 나타내면,
$\begin{align} T_0 = 0: \\ T_n = 2T_{n-1}+1,\ n>0에\ 대해 \end{align}$
위와 같은 식이 점화식(recunence formula)으로, 경계값(boundary value)과 등식으로 구성됨.
- 등식은 일반항의 값을 이전 값으로 서술

점화식의 문제점

$T_n$을 구하려면 그 이전 값을 구해야한다.
만약 $n$이 엄청 크다면? 그래도 묵묵히 0부터 $n$이 될 때까지 계산해야하는 번거로움이 있다.
이런 과정을 건너뛰고 단번에 $T_n$을 구할 수 있는 닫힌 형식 (closed form)의 공식을 점화식의 해(solution) 라고 한다.

점화식의 해 구하기

작은 사례의 답을 살피고 큰 사례에서도 정확함을 증명하는 것이다. 하노이 탑의 점화식의 작은 사례를 보면 다음과 같을 것이다.
$\begin{align}T_0 = 0\\ T_1 = 2\cdot0+1 = 1\\ T_2 = 2\cdot1+1 = 3\\ T_3 = 2\cdot3+1 = 7\\ T_4 = 2\cdot7+1 = 15\\ T_5 = 2\cdot15+1 = 31\\ T_6 = 2\cdot31+1 = 63 \end{align}$
이를 봐서는 해는 다음과 같을 것이다.
$\begin{align}T_n = 2^n-1,\ n>0에\ 대해\end{align}$

수학적 귀납법(Mathmatical Induction)

정수 $n$에 관한 어떤 명제가 모든 $n\geq n_0$에 대해 참임을 증명하는 일반적인 방법으로 다음과 같은 단계로 나뉜다.

기초(basis) 단계: $n$의 가장 작은 값 $n_0$에 대해 증명
귀납(induction) 단계: $n_0$에서 $n-1$까지 증명되었다는 가정하에 $n>n_0$에 대해 명제를 증명

수학적 귀납법은 점화식을 푸는 데 이상적이다. 점화식의 해 구하기에서 구한 해에 적용해보면 다음과 같다.

기초(basis) 단계: $T_0=2^0-1=0$
귀납(induction) 단계: $n>0$인 $n-1$에 대해 성립한다고 가정하고 점화식의 등식 $T_n = 2T_{n-1}+1$과 해 공식 $T_n = 2^n-1$ 사용하면 다음과 같은 등식을 얻을 수 있다.
$\begin{align}T_n = 2T_{n-1}+1=2(2^{n-1}-1)+1=2^n-1\end{align}$

정리하면, 위와 같은 특정한 수량의 닫힌 형식 공식을 찾을 때는 세 단계를 거치면 된다.

작은 사례 검증
특정 수량에 대한 수학 공식을 구하고 증명을 만든다.
닫힌 형식의 수학 공식을 구하고 증명

책의 목표

구체 수학 책의 초첨은 3단계, “닫힌 형식의 수학 공식을 구하고 증명”하는 것으로, 그 앞은 생략하는 경우가 많다(고 한다^^;). 점화식의 해 구하기에서 하노이의 탑의 해를 구하긴 했는데, 이는 운이 좋게 ‘추측’한 것이 맞았다고 한다. 사례를 나열해 놓고 각 단계의 숫자들 간의 관계를 ‘추측’한 것인데, 이를 ‘귀납적 비약(inductive leap)’라고 한다. 근데, 이 책의 목표는 그런식으로 해를 ‘추측’하는 것이 아니고 ‘구하는 방법’을 설명한다고 한다.