独自ルールを用いた “ハノイの塔”の拡張 立命館高校 ３年９組 馬部 由美絵
ハノイの塔 フランスの数学者エドゥアール・リュカが1883年 に発売した数学のゲーム ルールは以下の３つ ・左から右の棒へ移動させる ・左から右の棒へ移動させる ・一回につき一枚のみ移動可能 ・小さい円盤の上に大きい円盤は乗せれない
目的 ハノイの塔について、棒に刺さっているす べての円盤を、別の棒に移し替えるために 必要な、最小の手数回数を求めるための一 般項を求める。『ハノイの塔』のルールを 変化させ、拡張する。
一般的なハノイの塔 ルール ・左から右の棒へ移動させる ・一回につき一枚のみ移動可能 ・小さい円盤の上に大きい円盤は乗せれない
〈1枚〉n = 1 a1= 1 〈2枚〉n = 2 a2 = 3 〈3枚〉n = 3 a3 = 7 〈4枚〉n = 4 a4 = 15 an-1 のときと同じ移動 一番下の円盤を隣の棒に移す移動
an = 2n – 1 ・・・① ( n= 1, 2, 3, ) 〈証明〉 (1) n = 1の時21 – 1 = 1 ゆえに、①は成り立つ。 (2) n = kの時①が成り立つと仮定する。 a k= 2k - 1・・・② n = k + 1の時を考えると、②より ak+1 = 2k – 1 + 2 = 2 k+1 - 1 ゆえに、①はn = k + 1の時も成り立つ。 (1) (2)より、①は全ての自然数 n について成り立つ。 したがって、求める一般項は an = 2n - 1
ＮＥＷルール① ルール ・左から右の棒へ移動させる ・１回につき１枚のみ移動可能 ・小さい円盤の上に大きい円盤は乗せれない ・隣の棒にしか移動させることができない
〈1枚〉n = 1 a1= 2 〈2枚〉n = 2 a2 = 8 〈3枚〉n = 3 a3 = 26 〈4枚〉n = 4 a4 = 80 an-1 のときと同じ移動 一番下の円盤を隣の棒に移す移動
ＮＥＷルール② ・左から別の棒へ移動させる →つまり真ん中の棒へ移動させる ・１回につき１枚のみ移動可能 →つまり真ん中の棒へ移動させる ・１回につき１枚のみ移動可能 ・小さい円盤の上に大きい円盤は乗せれない ・隣の棒にしか移動させることができない
〈1枚〉 n = 1 a1= 1 〈2枚〉 n = 2 a2 = 4 〈3枚〉 n = 3 a3 = 13 〈4枚〉 n = 4 a4 = 40 an-1 のときと同じ移動 一番下の円盤を隣の棒に移す移動
ＮＥｗルール③ ・左から別の棒へ移動させる →つまり真ん中の棒へ移動させる ・１回につき１枚のみ移動可能 →つまり真ん中の棒へ移動させる ・１回につき１枚のみ移動可能 ・小さい円盤の上に大きい円盤は乗せれない ・隣の棒にしか移動させることができない ・一方通行のみの移動
〈1枚〉n = 1 a1= 1 〈2枚〉n = 2 a2 = 5 〈3枚〉n = 3 a3 = 15 と同じ移動（下２枚より上に乗っている円盤を２個先の棒へ） 一番下の円盤を隣の棒に移す移動 二番目に下にある円盤を隣の棒に移す移動 an-1と同じ移動（下２枚より上に乗っている円盤を１個先の棒へ）
考察 ルール①と、一般的なルールの場合の一般項を比較す ると、公比が異なるよく似た数式になることがわかり ます。どちらも等比数列の式から－１という式になり ます。シンプルできれいな数式になりました。 ルール①と、ルール②の一般項を比較すると、ルー ル①の数の２分の１がルール②の時の数になることが わかります。円盤の移動先の棒の位置を、一つ手前に 変えたことにより、数が２分の１になりました。ここ から、もし円盤の異動先の棒の位置を、一つ先に変え ると、ルール①の数の２倍になるのではないかと考え られます。 ルール③の一般項は、他の一般項とは少し違ってお り、二段階の漸化式になりました。一般項に無理数が 入っているのにも関わらず、自然数 n 代入すると整 数となって出てきます。
今後 ルール③の時の一般項のｃ１、ｃ２を求める。 一般項ａｎの証明をする。 別の独自のルールを考えて拡張する。 今までは独自のルールによって円盤の移動 の条件を限定してきたので、逆に円盤の移 動の条件を広げられるような新しいルール を考える。
Thank you!