こんにちは！繁田です。急に暖かくなったり寒くなったり、雨が降ったり花粉が飛んだりと、安定しない気候が続きますが風邪などひかれていませんか？[E:up][E:up]さて、先週の問題を解説します。先週の問題はコチラでした。【問題】インドのガンジス川ほとりにあるバラモン教の寺院では、３つの柱のうちの１つに下から大きい順に積み重ねられた64枚の円盤を、僧侶たちが次のルールに従って別の棒に移しかえようと動かしているという。①移動できるのは、１回につき１枚②移動した円盤はそれより大きな円盤の上に乗せる（小さい円盤の上に大きい円盤が乗ってはいけない）③移動した円盤はいずれかの柱に必ず差し込む（外によけておくことはできない）伝説では、この移し替えが終わるとき、世界が滅びるとのこと。怖い話ですね。さてその伝説はともかくとして、これと同じルールで、３つの棒のうち１つに重ねられている４枚の円盤を、別の棒に移しかえるには、最低何手かかるかを考えてみましょう。下から大きい順に４冊の本を積み重ねてやってみると、わかりやすいかもしれません。こんな問題です。これは実は「ハノイの塔」と呼ばれている、超有名な問題です。こちらの解説を動画でおこなってみました！[E:movie]…が、動画のアップロードがうまくいかず、更新が遅れてしまいました[E:despair]しかたないので、ひとまず文字で書こうと思います[E:pencil]いきなり4枚だと難しいので、まずは2枚の円盤で考えてみましょう[E:flair]①A、B、Cと3本の棒があり、Aにささっている2枚の円盤をCに動かすことを考えます。手元に大きさの違う本を重ねておいてもらえるとわかりやすいと思います。その場合は、3手でできることはお分かりいただけますか？（A→B、A→C、B→Cの3手）つまり、2枚の円盤を別の棒に移すには「3手」かかるとわかりました[E:rock]②では次に、円盤を3枚にします。そのときの考え方ですが、3枚の円盤のうち、上2枚をまずはBに動かすと考えます。それにかかる手順は、①と同じで3手ですよね。次に、Aに残っている一番大きな円盤をCに移します。これに1手。そしてそのあと、Bにある2枚の円盤をCに動かすのにかかる手数は…やはり①のように3手ですよね。というわけで、合計3+1+3＝7手で動かすことが可能です。③では今回の問題、円盤4枚だったら？まずは3枚をBに→７手（②の手数と同じになるはずですよね）次に、一番大きい円盤をCに→1手そのあと、Bの3枚をCに→７手よって、今回の問題の正解は7+1+7=15手になります。うーん、、動画や図を使って説明したい…[E:crying]ちなみに、答えの3、7、15というのは、2枚 2×2-1=3 答え3手3枚 2×2×2-1=7 答え7手4枚 2×2×2×2-1=15 答え15手という風に求めることもできます。この式は「2の枚数乗-１」と言うことができますね。（小学生的には「2を枚数の数だけかける」という言い方になりますね）ところで、2を何回もかけていくという作業は、ぱっと聞いた時のイメージ以上に実はとんでもないことになります。ハノイの塔の伝説にある64枚の円盤を移しかえるのには、何手かかるのでしょうか？？2を10回かけると…1024です。でも、まだこのあたりは序の口です。2を20回かけると…1024×1024で軽く100万オーバーです。2を40回かけると…軽く100万×100万で…1,000,000,000,000って！？？1兆オーバーです。[E:coldsweats02]ひとまず、40枚の円盤を動かすのにどれくらいの年月がかかるかを、おおよそで試しに計算してみましょう。1手うごかすのに１秒かかるとしたら、1年間は60×60×24×365＝31536000秒なのでだいたい3千万手、3年間で約1億手だとしても、えーと…30000年かかります。60枚の円盤を動かすのはさらにこの100万倍かかるので…えー[E:coldsweats01]そりゃ世界も滅びるさ…とそんなお話でした！
