今回はハノイの塔という数学の問題ですが、論理クイズとして楽しむ問題になります。
どんな問題なのか。さっそく問題にいってみましょう！それでは
レッツゴー
問題
上図のように5段に積まれた円盤があります。
これを一番右の棒に移し替えることを考えます。
移し替えるための条件が3つあります。
- 移動は常に3本の棒を使って移動させる。（床などにいったん置くなどはなし）
- 1回につき1枚の円盤しか移動させてはいけない。
- 円盤を重ねる際に、円盤の上にその円盤より大きい円盤を重ねてはいけない。
ここで問題です。
5枚の円盤を考えるとき、最短で何手かかるでしょうか？
今回はヒントを出すので、それを含めて考えてみてください。
自力で考えたい人は、ここでいったん止めて考えてみてください。
ヒント1
1枚の場合から考える
最小の場合から考えるという定石が使えます。
今回だと1枚の場合ですね。
円盤が1枚の場合はもちろん1手が最短になります。
ラストヒント
2枚、3枚の場合を考える
2枚の場合は下図のようになり、3手が最短です。
円盤が2枚の場合
3枚の場合は、2枚の場合の結果を使って簡単に求められます。
円盤が3枚の場合
②までが2枚の円盤を違う棒に移し替えるための最短手数が3手であることが分かっているので、②までで3手になります。
そして、③は赤の円盤を移しただけなので、1手。
そして、最後にもう一度2枚の円盤を右に移し替えるので、これも3手になり、合わせて7手が3枚の円盤の場合の最短手数になります。
ここから先に答えがあります。
答え
31手
さっそく解説パートにいってみましょう。
よく分かる解説
皆さんは法則に気付けたでしょうか？
1枚の場合、最短手数：1・・・①
2枚の場合、最短手数：①+1+①＝1+1+1＝3・・・②
3枚の場合、最短手数：②+1+②＝3+1+3+＝7・・・③
という法則があるんです。
なぜかと言うと、3枚の場合を例に考えると、3枚の円盤があるということは、一番下の1枚の円盤を右に移すために、上の2枚を移動させる必要があります。（②の移動）
なので、2枚の場合の最短手数+1、そして、もう一度2枚の円盤を右に移す（③の移動）ので、3枚の円盤の場合は、
2枚の場合の最短手数+1+2枚の場合の最短手数
となるのです。
同様に考えていくと、
4枚の場合：③+1+③＝7+1+7＝15・・・④
5枚の場合：④+1+④＝15+1+15＝31
となります。
よって、円盤が5枚の場合は31手が最短の手数になります。
まとめ
どうでしたか？
この問題について面白い話があります。
それは、64枚の円盤でこの操作が実際に行われており、これが完成された時に世界が消滅すると言われているんです。
こんな途方もないことが実際に行われているんですよ。
どれくらい途方もないかというと、1枚の円盤を1秒で動かせるとして何年かかると思いますか？
それがじつに
約5800億年！！！
えっぐいでしょ。
そら世界も消滅してますよ。
というか完成しないんじゃないですかとすら思ってしまいます。
今日はどちらかというとこれが伝えたかったんです笑
というわけで今回は以上です。それでは
ザ・エンドってね
関連記事
【論理クイズ】「大中小の瓶の重さは？」 あなたは論理的に解ける？
【論理クイズ】「5人の海賊と100枚の金貨NEO」 海賊たちは金貨を分けるようです
コメント