ハノイの塔 １年９組　馬部　由美絵

動機 数学について研究したことが無かったので、早苗先生の「数学玉手箱」でネタを探した。そこでこのハノイの塔というパズルを見つけ、おもしろそうだと思ったので、このテーマについて研究してみることにした。

調査 ハノイの塔とは パズルの一種であり、すべての円盤を右端の棒に移動させることができたら完成。 調査　ハノイの塔とは パズルの一種であり、すべての円盤を右端の棒に移動させることができたら完成。 すべての円盤を移動させるには２ⁿ―１回 の手数がかかる。 インドに建つ６４段の円盤を移し替えたとき、世界が滅びると言われている！？ 64枚の円盤を移動させるには、最低でも1844京6744兆737億955万1615回かかり、1枚移動させるのに1秒かかったとして、約5,845億年かかる

実験 目的 　実際に自分でパズルをやり、調べた際に書かれていた手数の回数と一致するか確認する。

実験（１） 準備 ダンボール・ストロー３本 を使い、写真①のような 「ハノイの塔」を作った。 方法 　ダンボール・ストロー３本 　を使い、写真①のような 　「ハノイの塔」を作った。 方法 　ルールに従い、「ハノイの塔」を使用して左のストローに積み重ねられた円盤を右のストローに移動させる。その際、移動させた回数を記録し、そこから方程式を証明する。１段から６段までの各段数をそれぞれ実験する。

結果 調べた数値と今回の実験（１）の結果を比較してみると、一致していることが分かった。 段数 １段 ２段 ３段 ４段 ５段 ６段 回数 １ ７ １５ ３１ ６３ 次に、棒を４本に増やしてみても数値が同じになるか確かめてみた。

実験（２） 準備 実験（１）で使用した 「ハノイの塔」にストロー をもう一本追加し、棒を四本にした 「ハノイの塔ＮＯ．２」 （写真③） 方法 　実験（１）で使用した 　「ハノイの塔」にストロー 　をもう一本追加し、棒を四本にした 　「ハノイの塔ＮＯ．２」 　（写真③） 方法 　上記の「ハノイの塔ＮＯ．２」を使用し、実験（１）のように１段から６段までの各段数を実験する。 写真③

結果 調べた数値と今回の実験（２）の結果を比較してみると、一致していることが分かった。 段数 １段 ２段 ３段 ４段 ５段 ６段 回数 １ ９ １３ １７

考察 実験（１）の結果から、求めたい段数の移動回数は、ひとつ前の段数の移動回数に２をかけて１引いたものになることがわかる。 Ｍ＝２ｘ－１ 　　　　　Ｍ＝２ｘ－１ 実験（２）の結果から、求めたい段数の移動回数は、ひとつ前の段数の移動回数に４たしたものになることがわかる。 　　　　　Ｍ＝４＋ｘ ＊求めたい段数の移動回数をＭ 　求めたい段数の一つ前の移動回数をＸとする

発展　ハノイの塔にひそむ規則性① 板の枚数2とスタートとゴールをのぞいた「一時待避用の棒」の本数1とを用いて「hanoi(2, 1) == 3」と表現する。 この待避用の棒が1本あることを「スペースが1個ある」と表現する。 スペースが1個のハノイの塔問題に関しては「hanoi(n, 1) = 2 * hanoi(n - 1, 1) + 1」が正の整数nに付いて成り立つ。 　スペースが2以上の場合には、 　いったいどういう規則性があるのか調べてみた。

発展 ハノイの塔にひそむ規則性② スペースが１つの場合の移動回数 発展　ハノイの塔にひそむ規則性② スペースが１つの場合の移動回数 　0, 1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095, 8191, 16383, ... スペースが２つの場合の移動回数 　0, 1, 3, 5, 9, 13, 17, 25, 33, 41, 49, 65, 81, 97, 113, 129, ... スペースが３つの場合の移動回数 　0, 1, 3, 5, 7, 11, 15, 19, 23, 27, 31, 39, 47, 55, 63, 71, ...　　　　　　　　　 この上３つの数列の隣り合う数字の差（段差数列）を求めると、それぞれ 　1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, ... 　1, 2, 2, 4, 4, 4, 8, 8, 8, 8, 16, 16, 16, 16, 16, ... 　1, 2, 2, 2, 4, 4, 4, 4, 4, 4, 8, 8, 8, 8, 8, ... そして、同じ数がいくつ続くかを新たな数列にすると、それぞれ 　1: 1, 1, 1, 1, 1, ... 　2: 1, 2, 3, 4, 5, ... 　3: 1, 3, 6, 10, 15, ...　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 この数列の列はパスカルの三角形を45度回転して斜めに読んだものであることがわかります

発展 ハノイの塔にひそむ規則性③ スペースが3個の場合の数列は三角数と呼ばれる。 発展　ハノイの塔にひそむ規則性③　　 スペースが3個の場合の数列は三角数と呼ばれる。 　　つまり、スペースがm個のハノイの塔の移動回数の数列の階差数列は、 m次元の三角形を用意して、 0段目には1、1段目には2、k段目には2kと書き、小さい順に読みあげたものである。 階差数列が2になっているのは、1枚板を増やしたときに移動回数が2増えるということ。 　　2はスペースがmの時にm個続くが、これはm個スペースがあれば、m枚までの板は積み重ねずに平たくスペースに並べられるということ。 　　そして4が続く領域では「一度小さい板を空いているスペースに置いた後、大きい板を別のスペースに置き、スペースが足りなくなったので小さい板を大きい板の上に移動する」という作業が行われている。 　　この時、スペースがm個なら、最初に平たく置くことができたm枚のうち、小さい方のm-1枚は一番大きい板に乗せることができ、残ったスペースはm-1個になる。これが繰り返されることで三角数が現れる。

感想 数学的に解析するレポートというのは初めてだったので、きちんと実験によって結果を出し、まとめることができるか不安だったが、考察・発展までまとめてレポートを完成させることができたのでよかった。 ただのパズルだが、自分で実際にやってみることで規則性がよりよく理解することができた。他にも、数学の授業や携帯サイトなどで、数学的なゲームをしたこともあります。そのようなゲームにも、何か規則性が隠れているかもしれないな、と思った。また機会があれば、いろんなゲームの規則性を見つけてみたい。

参考文献 インターネットサイト 一般化したハノイの塔の問題にひそむ規則性 ハノイの塔 – Wikipedia 本 　一般化したハノイの塔の問題にひそむ規則性 　ハノイの塔 – Wikipedia 本 　パズルで算数アタマをみがく本（中学入試攻略編） 　著者：秋山仁　　発行所：小学館

ご静聴、ありがとうございました！！