漸化式 ハノイの塔

皆さんお元気ですか? 夏が戻ってきたような暖かい日があったり冷え冷えとした日があったりして木々が次第に紅葉してきましたね。

今日は前回の『数列と論理(名古屋大学入試問題)』で触れた漸化式の問題をやってみましょう。

昨日の問題をもう一度書きます。

 

ハノイの塔の漸化式

図のように3つに区切られた区画の一つに大きい円盤から小さい円盤へといくつかの円盤が積んであるときに、この円盤をそっくり別の端まで移動するという問題で規則は次のようになっています。

ハノイの塔|数学|ルシディチュード-灯台教養学部

*一度に円盤は一個ずつしか動かせない。

*三つの区画の外に円盤を置くことは許されない。

*小円盤の上に大円盤を乗せてはならない。

この規則にしたがって、次の問題にトライしてみましょう。

  問題

n個の円盤が積み重ねてある時、何回で別の端まで移動させることができるかをnの式で表しなさい。


 

【解説】

皆さん自分でやってみましたか?

これを漸化式を使わずに解こうとすると、なかなか厄介ですよ。

下図のように考えてみます。

漸化式 ハノイの塔|数学|ルシディチュード―灯台教養学部

まず (n -1)枚を隣のマスへ移します(図②)。

これは ハノイと塔の(n-1)の場合と同じことですから、an-1 で移すことができますね。

そうしたら一番下の一枚を一番右端へ移します(図③)。(ここで一回オペレーションが起こります。)

最後に、映しておいた(n-1)枚を一番下の一枚を移した右側へ移せば、全てが一番右側へ移せます(図④)。

従って、

an = 2an-1 + 1

ですから、この漸化式を解くと、   

an = 2(an-1+1) + 1

an+1 = 2(an-1+1)

an+1 = Tn

とおくと、

Tn=2Tn-1

=2n-1T1

T1=a1+1

a1=1は明らかですから

Tn=2

Tn=2n

従って

an =2n - 1   

 

どうですか、皆さん。漸化式の威力、体感しましたか?

フィボナッチ数列は次回に説明しましょう。まず自分で考えてみてください。



数学TOPへ


ABOUT US

ルシディチュード―灯台教養学部へようこそ。このサイトは、一般教養を学べる無料オンラインサイトです。Luciditude ルシディチュード= Lucid (明晰な、明快な)+ -(i)tude(状態、性質)。“すべての人の灯台としての教養を”をコンセプトに、大人も子どもも、ご家族みんなで、わかりやすく幅広く学べる一般教養をご紹介します。同時に、キャリア形成に役立つ能力開発についても発信します。雑談知識のインプット、生涯学習としてご活用ください。数学と英語は受験問題と解説を掲載しています。受験生はもちろん、受験生でない皆さんもぜひチャレンジしてみてください。

>>read more