ホームへ　少年少女数学愛好会へ　取れたての定理集へ

ハノイの塔

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

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

---

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

３本柱のハノイの塔

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

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

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

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

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

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

　これは４枚の場合です。

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

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

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

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

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

４本ハノイ

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

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

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

　４枚の４本ハノイです。

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

　５枚の４本ハノイです。

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

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

　６枚の４本ハノイです。

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

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

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

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

４本ハノイの最小手数・・・その規則性

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

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

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

５本ハノイ

　上で考えた方法で5本ハノイも考えることができる。そこで「５本ハノイ」についても考えてみよう。５本棒のハノイの塔は４本棒のハノイの塔に大きく関連していることがわかった。このことは、３本棒のハノイの塔と４本棒のハノイの塔との関係とほぼ、いや、全く同じと言えるでしょう。

　ハノイの塔は棒の数と大きな関係があります。諸知識でも述べましたが、ブロックの移動にはどうしても自由に移動が出来るような棒が必要となるのです。しかし、この関係のみでは、４，５本棒のハノイの塔は成り立ちません。と言うか、最小の回数でハノイの塔を完成させることは出来ません。では、そのほかにどんな規則性があるのでしょうか？

　我々は、はじめに「５本棒のハノイの塔は４本棒のハノイの塔に大きく関連している」と述べましたが、これは、つまり、５本棒のハノイの塔の中に４本棒のハノイの塔が存在すると言うことである。この性質が現れるのはブロック数個をある他の棒に移したときに現れます。

　例えば、ここに７個のブロックが存在するとします。このときのハノイの塔の成功回数は別表より19回となっています。これは始めに７個中の３個を他の棒に積み重ねます。このときは５本棒すべてが機能して５本棒のハノイの塔として扱うことが出来ますが、次に、残り４個のブロックを積み重ねるに当たっては一番小さいブロックがある一つの棒を使用不可能にしているため４個のブロックの移動は４本棒のハノイの塔と同じことになります。このように、５本棒のハノイの塔の中には４本棒のハノイの塔の特徴が現れてくるのです。

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

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

５本ハノイの最小手数の規則性

　そしてｎ枚の４本ハノイの最小手数の数列｛ａ_n｝と、その階差数列｛ｂ_n｝は次のようになる。
｛ａ_n｝
1,3,5,7,11,15,19,23,27,31,39,47,55,63,71,79,87,95,103,111,127,143,159,175,191,207,223,239,255,271,287,303,319,335,351,383

｛ｂ_n｝
2,2,2,4,4,4,4,4,4,8,8,8,8,8,8,8,8,8,8,16,16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16,32,・・・

２が３つ、４が６つ、８が１０、１６が１５・・・

　なにやら規則性が見えてきた・・・

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

さいごに

　2000年の７月〜８月にかけて行った研究によって「４本ハノイ」の結果がまとまり、それを2000年9月１日の文化祭で発表しました。この結果は大変面白い結果でしたので、５本ハノイについても調べはじめました。最後の表は2000年12月ごろにできました。そして、2001年８月に文化祭にむけて5本ハノイについてのレポートを作りましたが、文化祭のために昨年の「４本ハノイ」とあわせて、作り直すことにしました。

　トップへ 　取れたての定理集へ 　少年少女数学愛好会へ 　ホームへ

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