ハノイの塔2009/03/01 23:37

ハノイの塔
 妻が知り合いの木工作家から、以前販売した木の玩具を値下げしたので、おまけです、ということで「ハノイの塔」を貰ってきた。
 積み重なった円盤を別の場所に動かすという有名なパズルである。ただし、円盤はひとつづつ動かし、そのとき、小さい円盤が上になるように置かなければならない。
 きわめて有名なパズルなのだが、じつは、じっさいにやるのは初めてだった。ただ、最小回数が、円盤の数をnとして、Σ2k(k=0,n-1)、つまり2n-1になるということはなんとなく知っていた。円盤の枚数が9なので、511回になる。
 方法はすぐにマスターできたが、こういうパズルは目の前にあると、なんとなくやってしまうものである。しかも511回というのはけっこう時間がかかる。で、円盤の枚数はそのままで、新しいルールをひとつ考えてみた。円盤をふたつの場所に互い違いに積む(写真下)のである。考え方としては一緒だが、短い時間ですむ。219回になる、はずである。27+26+24+23+21+20と、Σ2k(k=0,7)から25と22を引いた値である。
 このパズル、だれか有名な数学者の考案だったよなと、ネットで調べると、フィボナッチ数の一般化で有名な数学者・リュカによるものだということだった。