2000櫻雲祭(文化祭)

ホームへ

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

ハノイの塔


 ベトナムのハノイにある寺院には、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

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




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

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

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

Ads by TOK2