ホームへ

　入り口近く部屋の真中、塩で遊ぼうコーナーの隣にハノイの塔のコーナーがあります。これは、とりあえずやってみるお客さんが多かったようです。しかし、その数学的な中身についてはちゃんと読んでもらえなかったようなきがします。普通のハノイの塔が３本の柱なのに対して、もうひとつ４本柱のあるものと並んでおいてあります。遊んでみてその違いに気が付いてくれれば、パンフレットに載っている生徒の発見についてもっと評価してもらえるのに・・・

ハノイの塔

　ベトナムのハノイにある寺院には、１００枚の石板と３本の柱があって、僧侶たちが石版を１枚ずつ移動しているのだそうです。石板は大きい順に下から積み上げられていて、移動する途中で大きい石板が小さい石板の上になってはいけません。僧侶たちは毎日この石板を動かしつづけているのだそうです。そして、この１００枚の石板が移動したときに、この世が終わるという言い伝えがあるのだそうです。

　この話を、しばらく信じていましたが、これは作り話なんだそうです。・・・

　トップへ 　もどる 　次へ 　最後へ 　

３本柱のハノイの塔

　１枚のときには、１回で移動できることは、明らかです。

　２枚のときには、左図のようにして３回で移動できます。これが最小回数であることも、おそらく文句の無いところだと思います。

　トップへ 　もどる 　次へ 　最後へ 　

　３枚のときには、回数が多くなりますが、左のようにして７回で移動できます。

　このハノイの塔に向かって黙々と動かしつづけていると、やり方がつかめてきます。どう動かせばよいか分かってきますが、これを最後までやるのはかなり大変です。何しろ、このハノイの塔は１０枚ですから、後で述べるように、１０２３回かかるのです。こ二日間で、二人の生徒がやり遂げましたが、途中で8止める生徒が多かったようです。

　トップへ 　もどる 　次へ 　最後へ 　

　これは４枚の場合です。

　全部移動するためには、一番底にある一番大きな円盤を移動しなければなりません。動かすための場所を作るためには、その上にある３枚の円盤を、１本の柱に移動していなければなりません。

　左の図は、まず、上から３枚を真中の柱に移動しています。次に、一番大きな円盤を残りの柱に移動し、その後また３枚を移動した大きな円盤の上に重ねています。

　これは、一般にｎ枚のときにもいえることです。ｎ枚の円盤を移動する最小回数をａ_nとしましょう。上から(ｎ−１)枚をａ_n-1回で別の柱に移動させて、一番下の最大の円盤を空いている柱に移動させた後、また、ａ_n-1回で残る(ｎ−１)枚を移動させればいいのですから、
　　　ａ_n＝２ａ_n-1＋１
という漸化式がなりたちます。

　ａ₁＝１、ａ_n＝２ａ_n-1＋１　から、
　　　ａ_n＝２ⁿ−１
ということになります。

　トップへ 　もどる 　次へ 　最後へ 　

４本ハノイ

　柱が２本しかないとすると、このゲームはできません。これができるのは、最低でも柱が３本必要です。この柱が４本になるとどうなるでしょう？

　柱が４本になると、自由度が高まる分、移動回数は少なくてすみます。左の図は３枚のときの４本ハノイの移動を示しています。一つの柱に一枚ずつ置いても、まだ１本柱があります。３本ハノイの時には７回かかった移動が４本ハノイでは５回で終わってしまいます。

　トップへ 　もどる 　次へ 　最後へ 　

　４枚の４本ハノイです。

　まず、３回で上の２枚を移動しています。次に、残り２枚を移動してから、その上に小さい２枚を移動しています。

　５枚の４本ハノイです。

　同じく、下の２枚を残して上３枚を移動しています。上３枚の移動に要する回数は、３枚の４本ハノイの回数だる５回です。次に、下の大きな２枚を移動するときには、上の３枚が置いてある柱以外の３本を使っての移動ですから、２枚の３本ハノイの回数である３回で移動しています。その後、小さい３枚の移動は、また３枚４本ハノイの回数である５回で移動し、合計１３回ということになります。

　トップへ 　もどる 　次へ 　最後へ 　

　６枚の４本ハノイです。

　左の図の移動では、まず上の３枚を５回で移動してから、下の３枚を移動しています。上の３枚が置いてある柱は使えませんから、ここからは３本ハノイの移動の仕方になってしまいます。３枚の３本ハノイで最低でも７回必要となります。そして、その後３枚を移動しますが、これには４本ハノイの５回が必要です。６枚の場合は、このようにして見てみると、１７回かかりそうです。

　トップへ 　もどる 　次へ 　最後へ 　

　上で見たように、大きいほうの何枚かを残して上の小さい円盤を一つの柱に重ねるまでは、４本ハノイの移動となり、その後、残した大きな円盤の移動は３本ハノイになります。そこで、一枚残した場合、二枚残した場合、三枚残した場合・・・と調べていって下の表のようにまとめてみました。枚数が大きくなるにつれて、残した枚数が多くなったほうが全体の回数が少なくなります。しかし、残した枚数が大きすぎるとまた回数が増えてしまいます。円盤の枚数により、残す円盤の枚数に最適値があることがわかります。このように、何枚残すかで回数を調べていき、それらの中で最小のものを取っていけば、それが４本ハノイの移動の最小回数が分かります。

　トップへ 　もどる 　次へ 　最後へ 　

　ｎ枚の４本ハノイの移動回数を ｂ_n　とします。上の表から数列 ｂ_n　の階差数列を調べてみたら、
　　２,２,４,４,４,８,８,８,８,１６,１６,１６,１６,１６,３２,３２,・・・

　この階差数列の数字が変わるところが、何枚残すかによって回数の最小値が移動したところだということまで分かりました。

　トップへ 　2000文化祭へ 　ホームへ

SEO		[PR] 爆速!無料ブログ 無料ホームページ開設 無料ライブ放送