자연계열 1번

【문제 1-1】원반을 크기순으로 ①<②<③ 이라 하자.

【문제 1-2】세가지 답안을 제시한다.

<답안1>$\displaystyle H_{100}=2H_{99}+1=2(2H_{98}+1)+1=2^2H_{98}+2+1=\cdots=2^{99}H_1+2^{98}+2^{97}+2^{96}+\cdots+2+1$이 성립한다. $\displaystyle H_1=1$ 이므로,$\displaystyle H_{100}=2^{99}+2^{98}+2^{97}+2^{96}+\cdots+2+1=\frac{2^{100}-1}{2-1}=2^{100}-1$ 이다.

【문제 1-3】$\displaystyle H_{n+1}\geq2H_n+1$을 증명하자.

$\displaystyle n+1$개의 원반을 가진 하노이 퍼즐을 해결하기 위해서는 맨 아래에 있는 가장 큰 원반을 오른쪽 기둥으로 옮겨야 한다. 이를 위해서는 그 위의 $\displaystyle n$개의 원반들이 모두 가운데 기둥에 위치해야 한다. 그러므로 적어도 $\displaystyle H_n$번의 이동이 필요하다. 그 후에 가장 큰 원반을 오른쪽으로 옮기는데 한번의 이동이 필요하다. 마지막으로 가운데 기둥에 있는 $\displaystyle n$개의 원반을 오른쪽 기둥으로 옮기는 데 또다시 적어도 $\displaystyle H_n$번의 이동이 필요하다. 모두 합하면 적어도 $\displaystyle 2H_n+1$번의 이동이 필요하다.