１９世紀の数学者リュカの考案したゲームに「ハノイの塔」があります．ハノイの塔とは３本の柱Ａ，Ｂ，Ｃがあり，柱Ａにある何枚かの円盤を１枚ずつ柱Ｂを中継点にして柱Ｃに移動させるものです．ただし，どの柱でも上の円盤の方が小さくなければなりません．

（問）６４枚の円盤があるとき，移し替えが完了するには何回移動しなければならないのか？

　円盤が３枚であるとします．Ａにある３枚をＢに移すにはＣを中継点にしてＢに移動させる．このためには上の２枚をＣに移し，３枚目をＢにもってきた後，Ｃの２枚をＢに移動させる．次に円盤が４枚であるとします．上の三枚がくっついているとして，この３枚をＢに移し，一番下の円盤をＣにもってきて，Ｂの３枚をＣに移せばよい．

　このような再帰的な方法を用いれば円盤が何枚あってもＡからＣに移動させることができるのですが，ｎ枚の円盤を移動させるのに必要な最小回数をａnと書くことにすれば，漸化式

　　ａn＝２ａn-1＋１

で表せることがわかります．いま述べたｎ−１枚がくっついているとして・・・という考え方を小学５年生の息子に説明したところ，彼にも意味が理解できた様子でありました．

　ａnの具体的な値は

　　ａn＋１＝２（ａn-1＋１）

　　ａn-1＋１＝２（ａn-2＋１）

　　・・・・・・・・・・・・・

　　ａ2＋１＝２（ａ1＋１）

より，容易に

　　ａn＝２^n−１

で与えられることがわかりますが，こうして円盤が３枚のとき→４枚のとき→ｎ枚のときに一般化することができます．

（答）６４枚の円盤があるとき，２^64−１回の移動をしなければならない．１秒に１回移動をさせるにしても完了までには５８２０億年かかることになる．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝