【論理クイズ】「ハノイの塔」 最短何手で移し替えられるか

論理クイズ

皆さんアッシェンテ!

今回はハノイの塔という数学の問題ですが、論理クイズとして楽しむ問題になります。

どんな問題なのか。さっそく問題にいってみましょう!それでは

レッツゴー

問題

上図のように5段に積まれた円盤があります。

これを一番右の棒に移し替えることを考えます。

移し替えるための条件が3つあります。

  1. 移動は常に3本の棒を使って移動させる。(床などにいったん置くなどはなし)
  2. 1回につき1枚の円盤しか移動させてはいけない。
  3. 円盤を重ねる際に、円盤の上にその円盤より大きい円盤を重ねてはいけない。

ここで問題です。

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億年!!!

えっぐいでしょ。

そら世界も消滅してますよ。

というか完成しないんじゃないですかとすら思ってしまいます。

今日はどちらかというとこれが伝えたかったんです笑

というわけで今回は以上です。それでは

ザ・エンドってね

関連記事

【論理クイズ】「大中小の瓶の重さは?」 あなたは論理的に解ける?

【論理クイズ】「2回戦目に誰と戦った?」 優勝はA

【論理クイズ】「5人の海賊と100枚の金貨NEO」 海賊たちは金貨を分けるようです

【論理クイズ】「つり橋を最も早く渡るには」 グーグル入社試験の有名問題に挑戦!

【論理クイズ】「絶対に誕生日を知りたい友達✕絶対に誕生日を教えない友達」 ほこたて対決

コメント

タイトルとURLをコピーしました