立命館高校 3年9組 馬部 由美絵 フランスの数学者エドゥアール・リュカが1883年 に発売した数学のゲーム ルールは以下の3つ ・左から右の棒へ移動させる ・一回につき一枚のみ移動可能 ・小さい円盤の上に大きい円盤は乗せれない ハノイの塔について、棒に刺さっているす べての円盤を、別の棒に移し替えるために 必要な、最小の手数回数を求めるための一 般項を求める。『ハノイの塔』のルールを 変化させ、拡張する。 ルール ・左から右の棒へ移動させる ・一回につき一枚のみ移動可能 ・小さい円盤の上に大きい円盤は乗せれない 〈1枚〉n = 1 〈2枚〉n = 2 〈3枚〉n = 3 a1= 1 a2 = 3 a3 = 7 〈4枚〉n = 4 a4 = 15 an-1 のときと同じ移動 一番下の円盤を隣の棒に移す移動 an 2an 1 1 an 1 2an 1 an 1 an 12 n 1 2 n an 2 n 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回につき1枚のみ移動可能 ・小さい円盤の上に大きい円盤は乗せれない ・隣の棒にしか移動させることができない 〈1枚〉n = 1 a1= 2 〈2枚〉n = 2 a2 = 8 〈3枚〉n = 3 a3 = 26 〈4枚〉n = 4 a4 = 80 an-1 のときと同じ移動 一番下の円盤を隣の棒に移す移動 an 1 3an 2 a1 2 a1 2 a2 a1 1 a1 1 a1 3a1 2 8 a3 a2 1 a2 1 a2 3a2 2 26 a4 a3 1 a3 1 a3 3a3 2 80 an 1 1 3an 1 bn 1 3bn b1 a1 1 3 bn 3 3n 1 3n bn an 1より an 1 3an 2 an bn 1 3n 1 a n 3n 1 an 3n 1・・・① 〈証明〉 (1) n 1の時 an 31 1 2ゆえに、①は成り立つ 。 (2) n kの時①が成り立つと仮 定する。 ak 1 3ak 2 3 3k 1 2 3k 1 3 2 3k 1 1 ゆえに、①は n k 1の時も成り立つ。 (1)(2)より、① 以上より、求める一般 はすべての自然数nについて成り立つ。 項はan 3n 1 ルール ・左から別の棒へ移動させる →つまり真ん中の棒へ移動させる ・1回につき1枚のみ移動可能 ・小さい円盤の上に大きい円盤は乗せれない ・隣の棒にしか移動させることができない 〈1枚〉 n = 1 a1= 1 〈2枚〉 n = 2 a2 = 4 〈3枚〉 n = 3 a3 = 13 〈4枚〉 n = 4 a4 = 40 an-1 のときと同じ移動 一番下の円盤を隣の棒に移す移動 a1 1 an 1 3an 1 a2 a1 a1 1 a1 3a1 1 4 a1 1 a3 a2 a2 1 a2 3a2 1 13 1 1 an 1 3 an 2 2 bn 1 3bn a4 a3 a3 1 a3 3a3 1 40 an 1 3an 1 1 n 3 1 ・・・① 2 〈証明〉 an (1) (2) 1 3 1 1ゆえに、①は成り立つ 。 2 n kの時①が成り立つと仮 定する。 n 1の時 a1 1 3 2 2 1 3 bn 3n 1 3n 2 2 1 bn an より 2 1 1 1 a n 3n 3n 1 2 2 2 1 a n 3n 1 2 b1 a1 1 1 1 1 ak 1 3ak 1 3 3k 1 1 3k 1 3k 1 1 2 2 2 2 ゆえに、①は n k 1の時も成り立つ。 (1)(2)より、 ①は全ての自然数nについて成り立つ。 1 以上より、求める一般 項はan 3n 1 2 ルール ・左から別の棒へ移動させる →つまり真ん中の棒へ移動させる ・1回につき1枚のみ移動可能 ・小さい円盤の上に大きい円盤は乗せれない ・隣の棒にしか移動させることができない ・一方通行のみの移動 〈1枚〉n = 1 a1= 1 〈2枚〉n = 2 a2 = 5 〈3枚〉n = 3 a3 = 15 an 1 1 と同じ移動(下2枚より上に乗っている円盤を2個先の棒へ) 2 一番下の円盤を隣の棒に移す移動 二番目に下にある円盤を隣の棒に移す移動 an-1と同じ移動(下2枚より上に乗っている円盤を1個先の棒へ) an 2an 1 an 2 3 a1 1 a2 5 a* 2 a* a* 3 a 1 a 1 a 1 a 1 a3 2 1 a1 1 2 1 2 1 a1 1 2 2a2 a1 3 15 2 2 2 2 a 1 a 1 a 1 a 1 a4 3 1 a2 1 3 1 3 1 a2 1 3 2a3 a2 3 43 2 2 2 2 a * 1 an bn a * bn 1とおく an 1 bn 0 bn 1 2bn 1 1 bn 2 1 3 an 2an1 an2 3 bn 2bn 1 bn 2 斉次式 bn cx nとおく 〈 bnの証明〉 cx n 2 cx n 1 cx n 2 bn c1 1 3 c2 1 3 と x n 2 x n 1 x n 2 右辺 2bn 1 bn 2 x2 2x 2 n n x 0とする bn 2bn 1 bn 2 において 2c 1 3 2c 1 3 2c 1 3 c 21 3 1 3 c 21 3 1 3 c 21 3 1 3 1 c 21 3 1 3 1 c 1 3 4 2 3 c 1 3 4 2 3 c 1 3 1 3 c 1 3 1 3 c 1 3 c 1 3 n 1 2c1 1 3 n 1 n2 2 1 n 1 n2 1 n 1 n2 n2 1 2 n2 n2 2 n2 n2 2 1 2 n 1 bn 左辺 n 2 n2 2 2 1 2 n2 x 1 3 bn c1 1 3 an bn 1より an c1 1 3 c2 1 3 c2 1 3 n n n n 1 ルール①と、一般的なルールの場合の一般項を比較す ると、公比が異なるよく似た数式になることがわかり ます。どちらも等比数列の式から-1という式になり ます。シンプルできれいな数式になりました。 ルール①と、ルール②の一般項を比較すると、ルー ル①の数の2分の1がルール②の時の数になることが わかります。円盤の移動先の棒の位置を、一つ手前に 変えたことにより、数が2分の1になりました。ここ から、もし円盤の異動先の棒の位置を、一つ先に変え ると、ルール①の数の2倍になるのではないかと考え られます。 ルール③の一般項は、他の一般項とは少し違ってお り、二段階の漸化式になりました。一般項に無理数が 入っているのにも関わらず、自然数 n 代入すると整 数となって出てきます。 ルール③の時の一般項のc1、c2を求める。 一般項anの証明をする。 別の独自のルールを考えて拡張する。 今までは独自のルールによって円盤の移動 の条件を限定してきたので、逆に円盤の移 動の条件を広げられるような新しいルール を考える。
© Copyright 2024 ExpyDoc