[脳細胞を働かせてちょう題 07]ハノイの塔の問題

ハノイの塔の問題5リングバージョン

上の問題を解いてみてください。

知育玩具としても商品として販売されている有名な【ハノイの塔】と呼ばれる問題です。
別名【ブラフマーの塔】

数年前、テレビドラマの『探偵ガリレオ』で【フィボナッチ数列】とともに一躍有名になった【リュカ数列】の産みの親【エドゥアール・リュカ】が考案・販売したとされています。

本ページは当サイトの中でもとても人気のあるページです。

ですから、追記しておこうと考えたのですが、この問題だけでいいですから、また、何日かけてもいいですから、自分で納得いくまで、そのルールをとことん暴き出そうとしてください。

それを試みることだけでも、あなたは「脳を働かせる感覚」を体で覚えることになると思います。

ところが、何ごとでも中途半端に「何となく」で済ませてしまうことは、すべてのことに通じてしまうものですから、考える力が生まれる時も場合も失くしてしまいます。

ぶっちゃけた話、下のように道理や理屈を悩みながらでも、レポートにしてやろうというぐらいの気楽な気持ちでやり切れば、もうそこで、あなたが賢いと思っている人と同じレベルになっていると思いますよ。

普通に賢い人との差なんて、実はこういった些細なところで決まってしまっているのです。

入試で必ず1問では問われる「洩れなく整理する能力」

僕も、「勉強へのきっかけ作りとして【ハノイの塔】もいいですね!」と書いたままでそのままにしていましたので、このあたりで少し追求してみようかと思います。

中学入試にしろ大学入試にしろ、算数・数学の問題で必ず出題者が見たい能力の一つが、整理して洩れなく可能性を書き出せるかどうかの能力です。

この力を見る問題は必ず1問は入っていると言っても過言ではありませんが、その能力をゲーム感覚で育む素材として「ハノイの塔の問題」は適していますので、知育玩具になっていることも頷けます。

さて、この問題の内容は画像に示した通りです。

積み替えるリングの数によって難易度が変わってきそうなことは容易に想像できますよね。
最初にトライするには、5個バージョンが最も手頃ではないでしょうか?

残念ながら、僕はゲームソフトを作る知識は全くありませんのでビジュアルなゲームとしては、この場でご提供できませんが、下記のサイトで、クリック&ドロップで簡単に楽しめます。
何手で(何回の操作で)完成したかのカウントも出てきます。

僕なんか始めてトライしたときは、恥ずかしながら44~5手かかっていたように記憶しています。
最初は何も考えずにやるもんで致し方ありませんが、久しぶりにやってみたら34手。・・・情けないことです!
どっかで論理がいい加減になってしまったんですね。

最小で済ませる手数は後のお楽しみに取っておいて、あまり難しく考えずにどんどん手を動かして試行錯誤しながら挑戦してみてください。
気が付けばできてるって感じで完成すると思いますよ。

↓現在ページは存在も、スクリプトが機能していません。↓

5個のリングはレベル1で楽しめます。
何回かトライして、手数(操作回数)が減ってくれば、コツを修得しようと脳を働かせているって証拠になりますね。

クリアーできれば、6個のリング(レベル2)、7個のリング(レベル3)でも楽しんでみて下さいね。

その前に、5個リングへのトライが一段落したところで「どういう規則で動かしていけばいいんだろう」ってことを整理しておくと、リングの数が多くなったときに、サラサラと最短の手数で完成させるようになれるでしょう。

それに、頭の体操としても、やりっ放しじゃなくて、きちんと理屈を整理しておくことが大切ですからね。

さて、何手動かせば課題を遂行できるか?
興味が湧いてきましたか?

今や、ネットでも【ハノイの塔の問題】は詳しく解説したサイトも多いのに驚きました。
でも、最小の手数は”2n-1(nはリングの数)”とどれもが書いていますが、何故”2n“が出てくるのか、よく説明されていないコンテンツも多いように見受けられました。

数学パズル ハノイの塔 (木のおもちゃ 知育玩具)

数学パズル ハノイの塔 (木のおもちゃ 知育玩具)

木のおもちゃ製作所・銀河工房

ブラフマーの塔
インドのガンジス河の畔のベナレス(ヴァラナシ)に世界の中心を表すという聖堂がある。
そこには3本の大理石の柱(ダイヤモンドの針との説もあり)が立てられており、そのうちの1本には、当初64枚の黄金の円盤が大きい円盤から順に重ねられていたという。

バラモン僧たちはそこで、一日中円盤を別の柱に移し替える作業を行っている。
そして、全ての円盤の移し替えが終わったときに、この世は崩壊し終焉を迎えると言われている。

もちろんこれはリュカの作り話であるが、64枚の円盤を移動させるには、最低でも18,446,744,073,709,551,615回かかり、1枚移動させるのに1秒かかったとして、約5,845億年かかる(なお、ビッグバンは今から約137億年前の発生とされている)。

小さい数でバカみたいに幼稚にプロセスを追う!

さて、数の問題を考えるには、「やっぱり数が小さいものから考えることで、何かが見えてくるよ」ということは、本編でも【過去入試問題の着眼点】などでも口をすっぱくして言ってましたね。

では、その通り、リング数が少ない場合に置き換えてみて、バカみたいに幼稚にプロセスを追ってみましょう。
何もカッコ悪いことではありません。

とは言っても、リング数が1個の場合は、ただ左端から右端に移すだけの1手で済みますから、割愛しますね。
まさか、一旦中央の棒に刺して、次に左端の棒に刺すという2手で完成させる子も居ないでしょう。
それもアリですが、どう褒めてあげようか悩みどころです…。(笑)

では、リング2個バージョンの操作を下に表してみますね。

ハノイの塔:2リング
ハノイの塔:2リング最短第1操作
ハノイの塔:2リング最短第2操作
ハノイの塔:2リング最短第3操作

↑クリックで画像拡大(以下の小画像は全てクリックで拡大できます。)↑

リング2個なら、全然問題なくできたのではないでしょうか?
たった3手で目的は達成されます。

でもね、ここで、最初のリングを一番右端の棒に刺してしまったらどうでしょう?
そのことも可能性としてあるわけですから、この可能性にもきちんと落とし前をつけておかねばなりません。
可能性のあることを放置しておいては、「論理的に考えた」などという資格はとてもあるとは言えません。

この場合は、下のようになり、5手を要してしまいます。
よく眺めてみると、もし右端の棒にではなく中央の棒に積み替えることが目的だったとすれば、第3手目で右端のリングを中央に移せば、それで終了ということになりますね。

もし右端の棒にではなく中央の棒に積み替えることが目的だったとすれば、3手で済んだというわけです。

ハノイの塔:2リング第1操作
ハノイの塔:2リング第2操作
ハノイの塔:2リング第3操作
ハノイの塔:2リング第4操作
ハノイの塔:2リング第5操作

何かルールがあるのではないだろうか?

どうやら、どの棒にそのままの順序で積み替えるかによって、各操作でリングをどの棒に刺せば無駄が生じないのかを決める規則がありそうですよね!

そんな風な予感がしませんか?

2リングの場合で右端の棒が目的地の場合は、最初のリング(小さい方)は目的地の棒とは違う棒(中央)に刺し、次のリング(大きい方)は目的地の棒(右端)に刺せば、無駄なく最小の手数で目的を達成できる。

もし3リングであれば、これとは逆のことが言えそうだな。
リングが奇数か偶数かで論理が逆転するのではないかと予想されるな。

この段階で、僕はこの程度の推論を何となく持ちました。

よし、もう1個リングを増やしてみれば、何か掴めるかもしれない!

それでは、リング3個バージョンの操作も紐解いておきましょう。
もっと鮮やかに見えてくるのではないかと期待しつつ・・・。

結果、下のような操作の流れとなりました。

ハノイの塔:3リング
ハノイの塔:3リング第1操作
ハノイの塔:3リング第2操作
ハノイの塔:3リング第3操作
ハノイの塔:3リング第4操作
ハノイの塔:3リング第5操作
ハノイの塔:3リング第6操作
ハノイの塔:3リング第7操作

少し複雑になりましたが、7手で目的は達成されるようです。
無駄な手数に関しては、やはり予想通り、今回は2リングの際とは逆に、最初に移動させるリングを目的の棒に次に移動させるリングを目的とは別の棒に移すことで無駄が発生しないことが分かりますね。

ここで、ついでに、4リングの場合に思いを馳せてみると、最大のリングの上に載っている3リングに関して、この流れと同じ操作をしたとすれば、真ん中の棒に入れねばなりませんね。
そうなると、再び右端に移すための手数を打たなければなりません。

それならば、同じ手数でできるのですから、最初から上3リングを真ん中の棒に積み替えておけば、最大リングはダイレクトに右端の棒に刺せてしまい、無駄が生じないと考えられます。

ハッハーン!
どうやら、

  • 奇数のリング数のときは、最初は目的地の棒に移し変えるスタート
  • 偶数のリング数のときは、最初は目的地とは別の棒に移し変えるスタート

を切れば無駄が生じないのだなという一般化に辿り着きます。

さて、7手という数字で、ピーンと来ました~!

2リングは3手、3リングは7手が最小の手数。
そう来れば、ここで想起されるのは、”2n
これは、ある程度数学のトレーニングを積んできた子であれば、比較的自然に出てくる予測ですね。

でも確証があるわけではありませんから、今はただ頭の隅に置いておくだけでスルーしておき、次に、操作の流れから何か言えることはないかを探してみましょう。

  1. 僕が注目したのは、第3ステップを終えた段階です。
    最初に左端の底にあった最も大きなリングが右端の棒に刺せる準備ができています。
    絶対にこの状態を経ることなしに目的は達成できないということが言えますね。
  2. そして、第3ステップまでの操作の流れはどうでしょう?
    よく見ると、左端にあった上2つのリングを隣の棒に積み替える作業ではありませんか!
    ちょうど3手で積み替えることができていますね。
  3. 最後に、第4ステップで最も大きなリングを右端の棒に刺した後はどうでしょうか?
    次の課題は、中央の棒にある2つのリングを右端の棒に積み替える作業ではありませんか!
    そうなると、ここもちょうど3手で積み替えることができるということになりますね。

何となくゴールが見えて来たら逆手流でゴールから眺めてみる!

7手=3手+1手+3手と分解して考えることで、操作の流れの有り様、意味合いが少し浮かび上がってきましたね。
即ち、【2リングを積み替える手数+最大リングを目的地に移す1手+2リングを積み替える手数】なる構図が見えて来ました。



このコンテンツを閲覧するにはログインが必要です。お願い . あなたは会員ですか ? 会員について
発刊10周年記念

発刊10周年記念 / お申し込みはこちら

  • 受付時間:24時間年中無休

「帝都大学へのビジョン」は「バイブル」と頼られて10年。

受験合格に留まらない一生モノの栄養素が自分の未知の力を引き出す!

教材では、英数と算数の興味の引き金となり、且つ本質に目を向かせてしまうコアな問題を精選し、不器用レベルの脳細胞の働かせ方目線で解説。

京都大学工学部OB2名と大阪大学大学院工学科OBの3名、しかも全員ハードエンジニア出身(教師転身2名)で執筆していますから、商売人や学生上がりのような根拠のない、いい加減な甘言は書いていません。

発刊10周年記念 / お申し込みはこちら