さて64枚の円板を全部移し終わると世界が終わるという話を「ハノイの塔」で紹介しました。この64枚を移すには何回かかるでしょうか。
4枚の時は15回でした。
一番下の円板を動かせるのはその上のすべての円板が他の場所に移されたときです。4枚のときの7回目の状態になったときに初めて4が動かせます。
AからCに移すものとし、n枚のときにan回かかるものとします。
1枚なら直接AからCへ移す1回ですからa1=1です。2枚のときは上の1枚をまず、Bに移し、2枚目をCに移して、Bの1枚をCに移しますからa2=a1+1+a1=3です。
n枚のときは上のn-1枚をまず、Bに移し、一番下の1枚をCに移し、Bにあるn-1枚をCに移します。上のn-1枚をBに移すのは、Cに移すときのBとCを入れ替えて考えればよいので、an-1回です。従って、an=an-1+1+an-1=2an-1+1回です。
この最後の式はn=2のときはa2=2a1+1となります。
同様に、a3=2a2+1=2×3+1=7、a4=2a3+1=2×7+1=15となります。
このように次々にanを求めることができます。このan=2an-1+1のような式を漸化式といいます。
漸化式を使えば次々と求められるのですが、64枚の場合のa64を求めるのは大変です。実はこの場合、an=2n-1となることがわかっています。だからa64=264-1となります。
これは非常に大きな数なので、おおよそどれくらいの数になるかを求めてみます。おおよその数なので、264でも大差ないといえます。
対数を使います。log10264=64log102で、log102がおおよそ0.3010なので、19.264となります。つまり、1019=10000000000000000000を超えます。
1枚を動かすのに1秒かかるとして、1年が60×60×24×365=31536000秒ですから、3000億年を超えます。地球が誕生してから46億年といわれていますから、世界が終わるときを心配する必要はなさそうです。