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