ハノイの塔 ~数列の漸化式の有用性

数学まるかじり
1 数列の漸化式とは

 

1,3,5,7,9,・・・

 

のように,数字を並べた列のことを数列といいますが,上のように書き並べていくときりがありませんよね。そこで数列を表現する方法が大きく2種類あって,

 

① n番目の数がどんな数かを答える方法

② 数列がもつ性質を答える方法

 

が有名です。

 

数列に名前を付けるときはアルファベットの小文字を使います。先ほどの

 

1,3,5,7,9,・・・

 

という数列の名前を「a」と名付けたとすると,この数列の1番目の数をa1,2番目の数をa2,という風に,右下に小さな添え字をつけて表現します。つまり,

 

a1=1,a2=3,a3=5,・・・

 

といった具合ですね。

 

話を戻しましょう。数列を表現する方法が2種類あるといいましたが,

 

① n番目の数がどんな数かを答える方法

 

の場合は,先ほどの数列を 「an=2n-1」と表現し,これを一般項といいます。

 

この方法は非常に便利で,一度作ってしまえば10番目の数だろうが100番目の数だろうが,nに代入することですぐに計算できてしまいます。

 

ただし欠点としては,n番目を文字で表すのが結構難しい,ということです。もっと複雑な数列も世の中にはありますから,一般項を求めるだけで相当苦労する場合もあるのです。

 

 

② 数列がもつ性質を答える方法

 

の場合は,先ほどの数列を「1から始まって2ずつ増えていく」という風に,数の変化の様子を表現する方法です。式でいうなら,

 

a1=1, an+1=an+2

 

ということになります。この太字の式を「漸化式」といいます。

 

比較的複雑な数列であっても,どんな規則で並んでいるかを言うだけなら難しくありませんので,様々な数列を表現することができます。

 

ただし欠点としては,「100番目の数は何?」と聞かれても,即答するのが難しいということ。

 

1から始めて,順に2ずつ増やしていくわけですから,100番目が知りたければ99番目の数が,さらにその前の98番目の数が,・・・という風に,前の項が分からなければ次の項を求めることができません。

 

「漸」とは「ちょっとずつ」という意味。前の数から次の数へ,ちょっとずつしか変化が分からない式,ということになりそうです。

 

 

 

2 なぜ漸化式が必要なのか

 

一般に,数列を研究する場合には①の方法,つまり「一般項」を求める方法の方がはるかに役に立ちます。

 

2,6,12,20,30・・・

 

という数列を,

 

「増え方が4,6,8,10…ってな具合の数列」

 

と言うよりも

 

「一般項がn2+nの数列」

 

と言った方がいろいろ話が早いですからね。

 

しかし先ほども述べたように,世の中には一般項を簡単に算出できない場合もたくさんあります。数列の変化が複雑すぎて,全体の様子が一望できないことがあるのです。

 

 

しっかり勉強している方は,確率の問題で漸化式を用いることがあって驚いたことはないでしょうか。

 

ある試行を100回行ったときの確率,n回行ったときの確率,のように,全部の場合を書き出すのが困難なことってありますよね。

 

そんな時は,「n回目でこれが起こったら,次のn+1回目ではどうなるだろう」

 

という風に,2つの数の間で限定して考える方法が有効。

 

まさに,漸化式の出番なわけです。

 

漸化式は「ある一部分の結果から全体の姿を導き出す」魔法のような方法ともいえるのです。

 

 

 

3 「ハノイの塔」の問題

 

漸化式の有用性を知るうえで,有名な問題があります。

 

「ハノイの塔」の問題です。

 

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

 

 ハノイの塔は、インドの梵天様が宇宙創造時に作ったと言い伝えられており,棒はダイヤモンドで、円盤は純金で出来ていて64枚あるそうです。

 

円盤の大きさは全て異なっています。全ての円盤は1本目の棒に,小さい順に上から下へ突き刺さっていました。

 

僧侶たちはこの円盤を毎日一枚ずつ引き抜き,3本目の棒へ移すよう命じられました。そして,次のルールを守ることを課せられたのです。

 

   ① 一回に1枚しか動かすことが出来ない。

   ② 移動の途中で,小さい円盤の上に大きい円盤が乗ってはいけない。

   ③ 3本の棒以外のところに,円盤を置いてはいけない。

 

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

 

 この寺院を信奉する人々は,この作業が終了するとき,ハノイの塔は跡形も無く崩れ,同時に世界の滅亡がやってくると信じているそうです。

 

はるか昔から1日も欠かさず行われている作業で,始まってからどれくらいの年月が過ぎたのかは誰にも分かりませんが,現在でもこの寺院では,世界の終末へのカウントダウンとも言うべきこの怖しい作業を続けているのです。

 

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

 

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

 

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

 

 文字が出てくるとアレルギーを起こす人がいるかもしれませんので,苦手な方は以下の——部分を飛ばして結果だけご覧ください。(笑)

 

————————–(以下計算)———————————-

 

初めに64枚じゃなくて,「n枚」の円盤があったとしましょう。これを3本目に移し終わるのに「an日」かかる,と表しておきます。

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

初めにn+1枚の円盤があったならば,一番下の大円盤以外のn枚を2本目の棒に移動するのに,an日が必要ですね。

 

そのあと,一番下の大円盤を3本目に移動するのに1日かかります。最後に2本目に刺さったn枚の円盤を,3本目の大円盤の上に移すのに,またan日かかります。

 

 

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

 

an+1=2an+1

 

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

 

この漸化式を解くと,一般項はan=2n-1と求まります。

 

————————–(計算ここまで)——————————-

 

 

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

 

 

 

 

でもご心配なく。実際に計算してみると,

 

264-1=18446744073709551615日

 

かかると出てきます。1億年,1兆年どころか,その次の単位,1京年という所まで行ってしまいます。

 

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

 

 

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

コメント