2001年文化祭展示

2001年文化祭展示へ ホームへ 

ハノイの塔


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

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


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




3本柱のハノイの塔


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

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



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




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

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




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




 これは4枚の場合です。

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

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

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

 a1=1、an=2an-1+1 から、
   an=2n−1
ということになります。




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




4本ハノイ

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

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



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




 4枚の4本ハノイです。

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



 5枚の4本ハノイです。

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



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





 6枚の4本ハノイです。

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



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




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

枚数(n)4本ハノイ3本ハノイ一枚残二枚残三枚残四枚残五枚残六枚残七枚残八枚残九枚残十枚残
111          
2333         
35775        
49151199       
5133119131317      
617632721172133     
725127352925253765    
833255513733334169129   
941511675341414973133257  
10491023836957495781137261513 
116520479985736565891452655171025
12814095131101898181971532735211029
1397819116313310597971131612815291033
14113163831951651371131131291772895371041
15129327672271971691451291451933055451049
16161655352592292011771611612093215611057

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




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

 n枚の4本ハノイの移動回数を bn とします。上の表から数列 bn の階差数列を調べてみたら、
  2,2,4,4,4,8,8,8,8,16,16,16,16,16,32,32,・・・

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


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




5本ハノイ

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

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

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

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


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




枚数(n)3本ハノイ4本ハノイ5本ハノイ一枚残二枚残三枚残四枚残五枚残六枚残七枚残八枚残九枚残十枚残
1111          
23333         
375575        
415971197        
531131119131111      
66317152717151515     
71272519352519191919    
8255332351332723232327   
9511412767413531353943   
1010234931834943393531353943 
112047653999575147433939434751

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




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

 そしてn枚の4本ハノイの最小手数の数列{an}と、その階差数列{bn}は次のようになる。
{an
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

{bn
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,・・・

2が3つ、4が6つ、8が10、16が15・・・

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


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




さいごに

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




 トップへ  2001年文化祭展示へ  ホームへ

Ads by TOK2