ハノイの塔 〜漸化式の意味
トップへ戻る  分野ごとの要点  授業プリント  オンライン教科書 高校数学問題集 
公式集  数学まるかじり  学習支援 数学T 数学A 数学U  数学B 数学V 
   

太古の昔より,ハノイという町のある寺院に,円盤の突き刺さった3本の棒がありました。ハノイの塔と呼ばれています。

 ハノイの塔は、インドの梵天様が宇宙創造時に作ったと言い伝えられており,棒はダイヤモンドで、円盤は純金で出来ていて64枚あるそうです。円盤の大きさは全て異なっています。全ての円盤は1本目の棒に,小さい順に上から下へ突き刺さっていました。僧侶たちはこの円盤を毎日一枚ずつ引き抜き,3本目の棒へ移すよう命じられました。そして,次のルールを守ることを課せられたのです。

   @ 一回に1枚しか動かすことが出来ない。
   A 移動の途中で,小さい円盤の上に大きい円盤が乗ってはいけない。
   B 3本の棒以外のところに,円盤を置いてはいけない。

 何のためにこんなことをしているのでしょうか。そこには恐るべき伝説があります。

 この寺院を信奉する人々は,この作業が終了するとき,ハノイの塔は跡形も無く崩れ,同時に世界の滅亡がやってくると信じているそうです。はるか昔から1日も欠かさず行われている作業で,始まってからどれくらいの年月が過ぎたのかは誰にも分かりませんが,現在でもこの寺院では,世界の終末へのカウントダウンとも言うべきこの怖しい作業を続けているのです。

 さて,この作業,最短で何日で終わるのでしょうか? これは世界があとどのくらいで終わりを迎えるのかを知ることに他なりません。(伝説がホントならですが)

 実際に小型の模型を作って実験してみればいいのでしょうが,64枚も円盤があると結構時間がかかって大変です。

 実はこの問題,数列の漸化式を利用して解決することが出来ます。

 文字が出てくるとアレルギーを起こす人がいるかもしれませんが(笑),初めに64枚じゃなくて,「枚」の円盤があったとしましょう。これを3本目に移し終わるのに「日」かかる,と表しておきます。


円盤が1枚増えて,「 枚」だったなら,かかる日数は「日」と書かなければなりません。

初めに 枚の円盤があったならば,一番下の大円盤以外の枚を2本目の棒に移動するのに,日が必要ですね。そのあと,一番下の大円盤を3本目に移動するのに1日かかります。最後に2本目に刺さった枚の円盤を,3本目の大円盤の上に移すのに,また日かかります。

以上,枚の円盤を動かすのにかかる日数は,日となりますから,

      

という関係が成り立つことになるわけです。もちろん, ですね。


この漸化式を解き, に64を代入すれば,ああ,怖しい・・・ 宇宙創造時から数えてあとどのくらいで世界の破滅が来るのか,分かってしまうことになります。


でもご心配なく。実際に計算してみる18446744073709551615日かかると出てきます。1億年,1兆年どころか,その次の単位,1京年という所まで行ってしまいます。

ピンときませんよね。例えば1秒に1枚円盤を動かしたとしても,5800億年かかる計算です。宇宙創造時から数えて,現在約130億年が経過しました。


 当分世界は,安泰のようです。人間のエゴで,その寿命を早めたりしない限りは・・・



数学まるかじりへ