ハノイの塔

back

漸化式

ハノイの塔のパズルを解いて、その関係性を考察することから、漸化式に興味をもち、

漸化式の理解を深めることが、この教材のねらいである。


  一つの柱に大きい円板から小さい円板へと下から順にいくつかの円板が積んである。

 これらの円板を他の柱に積みかえる。柱は全部で3本ある。ルールは、

 ①円板はいずれかの柱へ1枚ずつ移動することができる。

 ②小さい円板の上に大きい円板は乗せられない。

 このときn枚の円板をそっくり他の柱に移すのに最低何手で移せるだろうか?

 

実際にプリントを正方形に切って操作させて最低手数を数える。3枚だと7手、4枚だと15手

かかる。n枚の円板を全部移すために必要な手数をanとすると、n枚の円板を全部移すには、

まず一番下の円板が移せるようになるまでにn-1枚を他の柱に動かすので、an-1手かかり、

一番下の円板を移すのに1手、また上のn-1枚を戻すのに an-1手かかるので、

合計an=an-1+1+an-1より、an=2an-1+1,a1=1という漸化式がたてられ、

これを解くと、an=2n-1となる。

「インドのバラモン教のある寺院では、黄金の円板64枚があり、日夜僧侶が円板を移しかえて

いる。この64枚がそっくり移されたときがこの世の終わるときだといわれている。」という話が

ある。円板64枚を移しかえる手数は、264-1≒1.8×1019で、1秒間に1回移しても、6000億年も

かかるというのは驚きである。

<参考文献>
[1]何森仁,小沢健一,近藤年示,時永晃 共著(1995),『のびのび数学』,三省堂,pp.154-157.