何か解決が困難な問題に直面したとき
「もし、こうだったら解決できるのに」
と思うことがありますよね。
問題を手探りで解決してゆく上で、解決するために十分な条件を考える姿勢は、数学という学問のみならず、生きてゆく上でも大切なことです。
今回は、そのような姿勢を意識して読み進めていただきたいと思います。
ハノイの塔とは
みなさんは、“ゲームが終了するときに世界が崩壊し終焉を迎える” という伝説のある「ハノイの塔」をご存知でしょうか。
私の手元に10段のハノイの塔がありますので、何はともあれご覧ください。
3本の杭と何枚かの円盤を用いて行うパズルゲームで、1883年にフランスで発売されました。
ルーカスタワーなどとも呼ばれており、映画「猿の惑星：創世記」では、知能が発達した猿へのテストとして用いられることで登場しています。
このハノイの塔を「解く」とは何か、ルールと共に説明します。
- ピラミッド状に積まれた円盤を、他の杭に同じ形に積み直していく
- 円盤は1枚ずつ動かす
- 円盤の上には、より小さな円盤しか乗せることができない
実際に、3段の場合を解いてみましょう。
初期状態
1手終了
2手終了
3手終了
4手終了（一番下の円盤が動きましたね！）
5手終了
6手終了
7手終了
お疲れ様でした。これで、3段のハノイの塔が無事に解けました。
ハノイの塔っていつも解けるの？
先ほどは、ハノイの塔とは何か、また、その解き方を説明しました。
そこで、次のような疑問を抱いた方がいらっしゃるかもしれません。
「ハノイの塔っていつも解けるの？」
さて、この疑問をどのように解決しましょうか。
ハノイの塔を紹介した際に、「ゲームが終了するときに世界が崩壊し終焉を迎える」という伝説があると紹介しましたから、
「ハノイの塔は常に解けるであろう」
という予想のもと、これの証明を試みましょう。
これが、今回の “問題” です。（記事冒頭で述べた姿勢を思い出してくださいね。）
証明してみよう
目標を明確にしておきましょう。
「任意の正の整数 \(n\) に対して、\(n\) 段のハノイの塔は解くことができる」
これを数学的に証明することを目指します。
まずは実験
\(n=1\) のとき、円盤は1段だけですので、1手動かせば終了ですね。（1手）
\(n=2\) のとき、円盤は2段です。手を動かしてみましょう。
小さい円盤を他の杭に動かし、大きい円盤を残りの杭に動かします。
最後に、小さい円盤を大きい円盤の上に動かせば終了ですね。（3手）
\(n=3\) のとき、円盤は3段ですが、ルール説明のときに写真で示した通り、解くことができますね。（7手）
次に考察
3段のハノイの塔を例にとります。
これを解くには、最も大きい円盤である、１番下の円盤を動かす必要があります。（ルール説明のときに写真でも強調しました。）
そのためには、１番下の円盤の上に円盤が乗っておらず、かつ、１番下の円盤を動かすための他の杭に空きがなくてはなりません。
つまり、１番下の円盤を除く上部2段のハノイの塔を解く必要があります。
逆に言えば、2段のハノイの塔を解くことができれば…
上部2段の塔を他の杭に動かすことができ
１番下の円盤を残りの杭に動かせて
その上に上部2段の塔を動かすことができる
つまり、3段のハノイの塔が解くことができます。
同じことは、4段のハノイの塔でも言えますね。
3段のハノイの塔を解くことができれば、
上部3段の塔を他の杭に動かすことができ
１番下の円盤を残りの杭に動かせて
その上に上部3段の塔を動かすことができる
つまり、4段のハノイの塔が解くことができます。
この議論を繰り返しすることで
\begin{align*}
1段が解ける\ &\Longrightarrow\ 2段が解ける\\
2段が解ける\ &\Longrightarrow\ 3段が解ける\\
3段が解ける\ &\Longrightarrow\ 4段が解ける\\
&\quad\!\!\vdots\\
n-1段が解ける\ &\Longrightarrow\ n段が解ける
\end{align*}
となり、なんと、\(n\) 段のハノイの塔が解けることが言えてしまうのです！
ここまでの考察を、整理しておきます。
- ある \(k\) 段のハノイの塔が解けたときに、\(k+1\) 段のハノイの塔も解けることを示す。
これだけでは証明が完了しません。
これだけでは、
\(n\) 段が解けるためには \(n-1\) 段が解ければよくて、
そのためには \(n-2\) 段が解ければよくて、
…、
そのためには2段が解ければよくて、
そのためには1段が解ければよい。
ここまでしか言えません。
イメージとしては、ドミノをせっせと並べただけで、最初の１つのドミノ（1段の場合の可解性）を倒していない状態です。
逆に言えば、あとは最初の１つさえ倒せば、直ちに全てのドミノが倒れて、証明完了となります。
つまり、証明にはもう１つの要素
- 1段のハノイの塔が解けることを示す。
ことが必要です。
いざ証明
上記の２点を再度まとめておきます。
- \(k\) 段のハノイの塔が解けるならば \(k+1\) 段が解ける。（ドミノを並べる）
- 1段のハノイの塔が解ける。（最初のドミノを倒す）
この２点を証明していきましょう。（実際のところは、ほとんど考察で話した通りですが…。）
– – – – – 証明 – – – – –
1について。
正の整数 \(k\) に対して、\(k\) 段のハノイの塔が解けると仮定する。
\(k+1\) 段のハノイの塔において、仮定より上部 \(k\) 段の塔を他の杭に動かすことができる。
このとき、１番下の円盤を残りの杭に動かすことができ、その上に上部 \(k\) 段の塔を再び動かせる。
これにより、\(k+1\) 段のハノイの塔は解ける。
2について。
1段のハノイの塔は、1手動かせば解ける。
– – – – – 証明終 – – – – –
見事、目標であった「任意の正の整数 \(n\) に対して、\(n\) 段のハノイの塔は解くことができる」ことが示されました。
これが数学的帰納法
さて、ここまではハノイの塔の可解性についてのみ考えてきました。
その証明のポイントを３度目になりますが確認します。
ここで、正の整数 \(n\) に対して「\(n\) 段のハノイの塔が解ける」という命題を \(P(n)\) と書くことにします。
ポイントは
- 正の整数 \(k\) に対して、\(P(k)\) が真ならば \(P(k+1)\) も真である。
- \(P(1)\) は真である。
これらが示されれば
「任意の正の整数 \(n\) に対して、\(P(n)\) は真である」
ことが示されます。
ドミノを並べて倒すような、この証明法を「数学的帰納法」（すうがくてききのうほう）といい、任意の正の整数（つまり、自然数）などに対する命題の証明に役に立ちます。
実際に証明するときは、2\(\to\)1の順で証明することが多いようです。（勿論、今回のように1\(\to\)2の順で示しても問題ありません。）
練習してみよう
伝説について
はじめに紹介した伝説を詳しく紹介します。
64段のハノイの塔を用意します。先ほど示したように、64段のハノイの塔も解けますね。（\(P(64)\) は真でした。）
これを最小の手数で解いたとします。
このとき、1手動かすのに1秒を要するとして、解けるにはどれくらいの時間が必要かというと
…約5845億年です！
驚愕ですね。（宇宙が生まれたのは約137億年前と言われています。）
最後に、この「最小手数」の証明をみなさんにしてもらおうと思います。勿論、数学的帰納法で。
最小手数の計算
証明の実験の際に見たように、1段のときは1手、2段のときは3手、3段のときは7手で解くことができました。
これらの規則は見出だせますか？（ヒント、それぞれの手数に1を足してみましょう。）
これらは
\begin{align*}
1段&\ \colon 1=2-1=2^1-1,\\
2段&\ \colon 3=4-1=2^2-1,\\
3段&\ \colon 7=8-1=2^3-1
\end{align*}となるので「\(n\) 段のハノイの塔を解く最小手数は \(2^n-1\) 手である」という推測から、この命題を \(P(n)\) として、数学的帰納法を適用してやりましょう。
（できる方は、紙とペンを手に取って、手を動かしてから読み進めてくださいね。）
\(n\) 段の最小手数を \(a_n\) とし、証明します。
– – – – – 証明 – – – – –
1について。
正の整数 \(k\) について、\(a_k=2^k-1\) と仮定する。
\(k+1\) 段のハノイの塔を解くには上部 \(k\) 段を他の1本の杭に動かす必要があるので、\(a_k\) 手だけ必要である。
その後、１番下の円盤を動かすのに1手必要。
最後に、再び上部 \(k\) 段を動かす必要があるので、さらに \(a_k\) 手だけ必要である。
以上より、
\begin{align*}
a_{k+1}
&=a_k+1+a_k\\
&=(2^k-1)+1+(2^k-1)\\
&=2×2^k-1\\
&=2^{k+1}-1
\end{align*}となる。
2について。
1段のハノイの塔の最小手数は1手であるが、\(n=1\) とすると \(a_1=2^1-1=1\) となり一致する。
– – – – – 証明終 – – – – –
以上より
「\(n\) 段のハノイの塔を解く最小手数は \(2^n-1\) 手である」
ことが証明されました。
伝説にある64段の場合は、
\begin{align*}
a_{64}=2^{64}-1=18446744073709551615
\end{align*}ですので、1844京6744兆737億955万1615秒、すなわち、約5845億年かかるというわけです。
ちなみに、ご紹介した私の持っている10段のハノイの塔の場合は
\begin{align*}
a_{10}=2^{10}-1=1023
\end{align*}ですので、1023秒、すなわち、17分3秒かかるというわけです。
（私は解くのに26分かかりました。笑）
ノーカット版です（時間のある方はご覧ください）
20倍速版です（時間のない方はご覧ください）
最後に
今回は、「ハノイの塔を解こう！」というモチベーションから、数学的帰納法について説明しました。
また、最後にはその練習として、ハノイの塔の最小手数を求めました。
最後の最後に、驚きの事実をお伝えしたいと思います。
ハノイの塔の杭を “4本に増やします” 。
そのとき、5845億年という所要時間により世界を崩壊させ、終焉を迎えさせた64段のハノイの塔を解くにはどれくらいの時間があればよいと思いますか？（もちろん、1手を1秒で。）
なんと、「6時間15分29秒」なんです！
5845億年が、杭を1本増やすだけで、6時間になりました。
（興味のある方は、Frame-Stewart（フレーム・スチュワート）アルゴリズムなどを調べてみてください。）
数学って面白いですね。
コメント