独自ルールを用いた “ハノイの塔”の拡張 立命館高校　３年９組 馬部　由美絵.

Presentation on theme: "独自ルールを用いた “ハノイの塔”の拡張 立命館高校　３年９組 馬部　由美絵."— Presentation transcript:

1 独自ルールを用いた “ハノイの塔”の拡張 立命館高校　３年９組 馬部　由美絵

2 ハノイの塔 フランスの数学者エドゥアール・リュカが1883年 に発売した数学のゲーム ルールは以下の３つ ・左から右の棒へ移動させる
　・左から右の棒へ移動させる 　・一回につき一枚のみ移動可能 　・小さい円盤の上に大きい円盤は乗せれない

3 目的 ハノイの塔について、棒に刺さっているす べての円盤を、別の棒に移し替えるために 必要な、最小の手数回数を求めるための一 般項を求める。『ハノイの塔』のルールを 変化させ、拡張する。

4 一般的なハノイの塔 ルール ・左から右の棒へ移動させる ・一回につき一枚のみ移動可能 ・小さい円盤の上に大きい円盤は乗せれない

5 〈1枚〉n = a1= 1 〈2枚〉n = a2 = 3 〈3枚〉n = a3 = 7 〈4枚〉n = 4 a4 = 15 an-1 のときと同じ移動 一番下の円盤を隣の棒に移す移動

6 　　　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 – = 2 k+1 - 1　　　　　 　　ゆえに、①はn = k + 1の時も成り立つ。 (1) (2)より、①は全ての自然数 n について成り立つ。 したがって、求める一般項は an = 2n - 1

7 ＮＥＷルール① ルール ・左から右の棒へ移動させる ・１回につき１枚のみ移動可能 ・小さい円盤の上に大きい円盤は乗せれない
・隣の棒にしか移動させることができない

8 〈1枚〉n = a1= 2 〈2枚〉n = a2 = 8 〈3枚〉n = a3 = 26 〈4枚〉n = a4 = 80 an-1 のときと同じ移動 一番下の円盤を隣の棒に移す移動

9

10 ＮＥＷルール② ・左から別の棒へ移動させる →つまり真ん中の棒へ移動させる ・１回につき１枚のみ移動可能
　　→つまり真ん中の棒へ移動させる ・１回につき１枚のみ移動可能 ・小さい円盤の上に大きい円盤は乗せれない ・隣の棒にしか移動させることができない

11 〈1枚〉　n = a1= 1 〈2枚〉　n = a2 = 4 〈3枚〉　n = a3 = 13 〈4枚〉　n = a4 = 40 an-1 のときと同じ移動 一番下の円盤を隣の棒に移す移動

12

13 ＮＥｗルール③ ・左から別の棒へ移動させる →つまり真ん中の棒へ移動させる ・１回につき１枚のみ移動可能
　　→つまり真ん中の棒へ移動させる ・１回につき１枚のみ移動可能 ・小さい円盤の上に大きい円盤は乗せれない ・隣の棒にしか移動させることができない ・一方通行のみの移動

14 〈1枚〉n = 1 a1= 1 〈2枚〉n = 2 a2 = 5 〈3枚〉n = 3 a3 = 15
と同じ移動（下２枚より上に乗っている円盤を２個先の棒へ） 一番下の円盤を隣の棒に移す移動 二番目に下にある円盤を隣の棒に移す移動 an-1と同じ移動（下２枚より上に乗っている円盤を１個先の棒へ）

15

16 考察 ルール①と、一般的なルールの場合の一般項を比較す ると、公比が異なるよく似た数式になることがわかり ます。どちらも等比数列の式から－１という式になり ます。シンプルできれいな数式になりました。 　ルール①と、ルール②の一般項を比較すると、ルー ル①の数の２分の１がルール②の時の数になることが わかります。円盤の移動先の棒の位置を、一つ手前に 変えたことにより、数が２分の１になりました。ここ から、もし円盤の異動先の棒の位置を、一つ先に変え ると、ルール①の数の２倍になるのではないかと考え られます。 　ルール③の一般項は、他の一般項とは少し違ってお り、二段階の漸化式になりました。一般項に無理数が 入っているのにも関わらず、自然数 n 代入すると整 数となって出てきます。

17 今後 ルール③の時の一般項のｃ１、ｃ２を求める。 一般項ａｎの証明をする。 別の独自のルールを考えて拡張する。
今までは独自のルールによって円盤の移動 の条件を限定してきたので、逆に円盤の移 動の条件を広げられるような新しいルール を考える。

18 Thank you!