こんにちは、ウチダです。
今日は、
「ハノイの塔」
というアルゴリズムを用いたゲームで楽しく遊び、最短の攻略法を、数学B「数列」で習った漸化式の知識を用いて考えていきましょう！
ハノイの塔とは？
ハノイの塔とは、19世紀末ごろに考案されたゲームの一種です。
まずはルール説明です。図をご覧ください。
便宜上黒と赤で色分けしましたが、つまり
これを求めていくことになります。
ここでルールがあります。
- 1回の移動で動かせるのは1枚の板のみ。
- 小さな板の上に大きな板を重ねてはならない。
この2つを守った上で、最短の手数で動かしてみましょう。
(なんか、パズルみたいで面白そうですよね！！)
そして、最後に、
これについても考えていきましょう。
ハノイの塔の規則性【小さな段数で規則性を見つける】
まずは $1$ 段から考えてみましょう。
これは明らかに $1$ 回の移動でOKですね。
よって、$n$段の最短移動手順を $a_n(回)$ とすると、$$a_1=1(回)$$ですね。
では次、$2$ 段の場合はどうなるでしょうか。
その次、$3$ 段の場合は…？ $4$ 段の場合は…？
一旦 $4$ 段までで止めておきましょう。
ちょっと考えてみてください。
$$a_2=3(回)$$$$a_3=7(回)$$$$a_4=15(回)$$
こうなりましたか？
ここから規則性を考えていくと、どうやら$$a_n=2^n-1$$の形になっていそうだな…
こういう予想が立ちましたか…？
実はこれが答えになります！
なので例えば、$10$ 段のハノイの塔の最短手順は、$$a_{10}=2^{10}-1=1023(回)$$と、とんでもない回数になります。
数学太郎一見大したことなさそうですけど、こんなに手順が必要なんですね。
ただ、今はまだ予想しただけですので、本当にこれで正しいのか数学的に考える必要があります。
その考え方が「 $2$ 通り」あるので、順にみていきましょう。
ハノイの塔の攻略1【漸化式を用いた解法】
数列で「漸化式」を必ず習うかと思います。
まず漸化式とは何か、復習しましょう。
漸化式…各項がそれより前の項によって定まる数列
つまり、たとえば $n+1$ 番目の項が $n$ 番目までの項で表せるとき、その数列を漸化式と呼びます。
では、先ほど考えていただいた、$4$ 段のハノイの塔を例にとって、見ていきましょう。
まず、1番目の操作として、「上の $3$ 段を $B$ に移動させる」と考えます。
すると、これは $3$ 段を移動させる最短手順なので、$$①=a_3(回)$$が成り立ちます。
では、次の操作にまいりましょう。
①で上に乗ってた $3$ つの板は動かせたので、ここで初めて一番大きな板を動かせます。
②の移動手順は、$A→C$ と一回なので、$$②=1(回)$$
となります。
では、最後の手順です。
一番下が移動できたので、その上にまた $3$ 段乗せていきます。
この操作は①と全く同じなので、最短手順は、$$③=a_3(回)$$
となります。
これで、$4$ 段の移動が終わりましたね！
さて、今までの話を式にしてみましょう。
$4$ 段の移動にかかった手順は、①+②+③です。
よって、
先ほど具体的に考えた時、$a_3=7(回)$、$a_4=15(回)$だったので、この式は確かに成り立ってますね。
…今考えた話って、$4$ 段の時しか言えないでしょうか…？
$5$ 段であっても、$6$ 段であっても、同じことが言えそうですよね。
よって、$n+1$ 段について考えると、$$a_{n+1}=2a_n+1(回)$$
これが今考えている数列の漸化式になりますね！(ここがポイント！)
漸化式が求まったので、あとは一般項を求めていきましょう。
【解】
特性方程式 $t=2t+1$ を解くと、$$t=-1$$なので、$$a_{n+1}+1=2(a_n+1)$$と式変形できる。
ここで、$a_n+1=b_n$と新たな数列 {$b_n$} を定義すると、$$b_{n+1}=2b_n$$よって、初項が$b_1=a_1+1=2$、公比が $2$ の等比数列になる。
よって、$$b_n=2・2^n-1=2^n$$
したがって、$$a_n=b_n-1=2^n-1$$
(証明終了)
数学花子結構簡単に求めることができましたね！
では、もう一つの方法を見ていきましょうか。
(これも実は数列の分野で習う知識です。)
ハノイの塔の攻略2【数学的帰納法を用いた解法】
数列の値を具体的に予想できるときは、その予想が正しいことを証明する方法として「数学的帰納法」が代表的です。
軽くおさらいしておきましょう。
数学的帰納法…$n=1$で成り立ち、$n=k$のとき成り立つと仮定した下で$n=k+1$のときに成り立てば、$n$がどんな自然数でも成り立つことを利用した証明方法。
よく「ドミノ倒し」が例に上がるのですが、ようは
- スタート地点
- 一個前がOKなら次もOK
が成り立てば全部ドミノは倒れる、つまり数列は成り立つ、
ということですね。
では、$$a_n=2^n-1$$になることを数学的帰納法により証明していきましょう。
【証明】
ⅰ) $n=1$のとき、$a_1=2^1-1=1$より成り立つ。
ⅱ) $n=k$のとき、成り立つと仮定する。
よって、$$a_k=2^k-1$$が成り立つ。
このとき、$n=k+1$について考える。
①$k$枚の板すべてを移動させるのは、$a_k=2^k-1$回かかる。
②一番大きな板を移動させるのは、1回かかる。
③$k$枚の板すべてを一番大きな板に乗せるのは、$a_k=2^k-1$回かかる。
したがって、
ⅰ)、ⅱ)より、数学的帰納法を用いて証明された。
(証明終了)
いかがでしょうか。
考え方は漸化式を用いる解法とさほど変わらないですが、使ってる道具が若干異なりますね。
100段のハノイの塔は何手かかるか！？
では初めに皆さんに投げかけた疑問
「100段のハノイの塔は最短何手かかるか」
文字だけ見る限りでは、「ゆーて大したことなさそう」ですよね。
ですが、規則性に気づいた今の皆さんなら、これがとんでもない数になることは予想できるはず！
だって…$$2^{100}-1$$ですもんね…(^_^;)。
こういう莫大な数の大体の値を出すテクニックを今からお教えします！
これ、結構使えるのでおススメです。
【解】
$2^{10}=1024≒10^3$を利用して、(ここがポイント！)
(終了)
つまり、大体「 $31$ 桁の数」ということになります！！
13桁でちょうど「1兆」なので、天文学的な数値ですね…。。
地球の歴史が約46億年ですので、1秒に約$10^{20}$回のスピードで移動させることができれば、地球が生まれたときからそれを行っていれば、今頃完成してますね。
自分で書いていて、「1秒に約$10^{20}$回のスピードってなんだよっ！」とツッコんでしまいました(笑)。
ハノイの塔に関するまとめ
いかがだったでしょうか。
今日は数列の知識を用いた、非常に面白いゲームをご紹介しました。
そして、100段のハノイの塔は現実的に不可能であることも示しました。
(補足)
図で板が赤と黒に色分けされてましたね。
実は、最短で動かすにあたって、「色の同じ板は絶対に重ならない」という性質があります。
これも数学的帰納法で示せますので、皆さんぜひトライしてみてください。
(ヒントは、杭「A,B,C」を色分けすることです。杭にも色がついてたのは、このヒントのためだったりします。)
アプリやアマゾンの商品では、ちょうどいい難易度のハノイの塔がありますので、ぜひ頭を鍛えながら楽しんじゃってください！
おわりです。
コメントを残す