前置き
世の中に数多あるパズルの中に、
ハノイの塔
というものがあります。
形状は、
- 3本の杭が(一列に)立っていて、
- 杭に大きさの異なる円盤が刺さっている
というものです。
遊び方は、
- 一方の端の杭に全ての円盤が大きさ順に刺さっていて、
- もう一方の端の杭に全ての円盤を移せれば完成
となります。
円盤を移すにあたって制約があります。
- 一番上の円盤のみ、他の2本の杭に移すことができます。
- ただし、小さい円盤の上に大きい円盤を乗せることはできません。
1手で1つの円盤を動かすものとして、何手かかるのか、見ていきましょう。
説明の都合上、杭にラベルを付けます。
- A┅初期状態で円盤が刺さっている杭
- B┅真ん中の杭
- C┅移す先の杭
円盤にもラベルを付けます。
- 上から順に1, 2,…
とします。
こんな感じです。
n段の場合
円盤が段の場合、円盤を移すのに必要な手数を
\begin{equation}
a_n
\end{equation}とします。
この書き方をすると、1段つまりで1手なので、
\begin{equation}
a_1=1
\end{equation}です。
n+1段の場合
円盤が段の場合、円盤を移すのに必要な手数は、
\begin{equation}
a_{n+1}
\end{equation}です。
ここで、を
で表せるかどうか考えてみましょう。
初期状態は図の(1)です。
- 1~n段をBに移動。これで
手。図の(2)です。
- n+1段目をCに移動。これで1手。図の(3)です。
- 1~n段をCに移動。これで
したがって、
\begin{equation}
a_{n+1}=2a_n+1
\end{equation}となります。
これで、n番目とn+1番目の関係を式で表すことができました。
こういう式を、
漸化式
といいます。
この式を解いていきましょう。
おもむろに、両辺に1を加えます。
\begin{equation}
a_{n+1}+1=2a_n+2
\end{equation}
右辺の2を括り出します。
\begin{equation}
a_{n+1}+1=2(a_n+1)
\end{equation}
式のを
に置き換えます。
\begin{equation}
a_n-1=2(a_{n-1}+1)
\end{equation}
繰り返していきます。
\begin{eqnarray}
a_{n+1}+1 &=& 2(a_n+1) \\
&=& 2^2 (a_{n-1}+1) \\
& \vdots & \\
&=& 2^n (a_1+1)
\end{eqnarray}
ここで、
\begin{equation}
a_1=1
\end{equation}なので、
\begin{equation}
a_{n+1}+1=2^{n+1}
\end{equation}となります。
ゆえに、
\begin{equation}
a_{n+1}=2^{n+1}-1
\end{equation}となります。
ふたたびn段の場合
先ほどの式で、を
に置き換えます。
\begin{equation}
a_n=2^n-1
\end{equation}
つまり、n段の円盤を移すのに必要な手数は、
\begin{equation}
2^n-1
\end{equation}手であることが分かります。
