組 三山崩しの必勝法 番 氏名 a00 + b0 2 f 0 ; a01 + b1 2 f 0 ; a02 + b2 2 f 0 ; .. . 0 al + bl 2 f 0 ; また ゲーム：三山崩し A ; B ; C 3 つの負でない整数があり , 自分と相 手が交互に , A ; B ; C のいずれか 1 つから自然数 n を引くことを繰り返し , 最後に A = B = C = 0 とできた者を勝者とするゲーム。 n X 自然数 N に対して N= k=0 n X 以下 k=0 k 2 Ç xk h xk 2 f 0 ; 1 g ; k = 0 ; 1 ; 2 ; ÅÅÅ; n i a0m + bm 2 f 0 ; 2 g のとき を, a0m + bm = 1 c0m = 1 a0l + bl 2 f 0 ; 2 g なので c0l = 0 k=0 2 k Ç ak ; B = ただし n X k=0 2k Ç bk ; C = n X k=0 c0m = cm m = l + 1 ; l + 2 ; l + 3 ; ÅÅÅ; n について は 2 進展開を表すものとする。 ê ë cl = 1 である とすると a00 + b0 + c00 2 f 0 ; 2 g a01 + b1 + c01 2 f 0 ; 2 g a02 + b2 + c02 2 f 0 ; 2 g .. . 3 つの数を A ; B ; C 。この 3 つの数 A ; B ; C について n X c0m = 0 のとき 「三山崩し」において A= なので 1; 2g m = 0 ; 1 ; 2 ; ÅÅÅ; l について 自然数 N の 2 進展開という。 2k Ç xk 1; 2g 1; 2g 1; 2g a0n + bn + c0n 2 f 0 ; 2 g 2k Ç ck 3 つの数 A0 ; B ; C 0 について am + bm + cm 2 f 0 ; 2 g ( m = 0 ; 1 ; 2 ; ÅÅÅ; n ) C 0 < C ; A0 = が成立している状態を「有利な状態」とする。 n X k=0 ただし 証明すべきこと 2k Ç a0k ; B = n X k=0 2k Ç bk ; C 0 = a0m + bm + c0m 2 f 0 ; 2 g I : 「有利な状態」にして相手に渡したとき , 相手がどのような取り方をしても , 次の手で 「有利な状態」に戻すことができる。 となるので ê n X 2k Ç c0k ë m = 0 ; 1 ; 2 ; ÅÅÅ k=0 が成立する。 よって, II : 「有利な状態」を維持すれば , 必ず勝つ。 「有利な状態」にして相手に渡したとき, 相手がどのような取り方をして も, 次の手で「有利な状態」に戻すことができる。 ことが証明できた。 証明 I 0 「有利な状態」から, 相手の操作によって A ; B ; C に変化したとする。 A0 = n X k=0 2k Ç a0k ; B = A 6= A0 n X k=0 2k Ç bk ; C = n X k=0 証明 II 2k Ç ck j 回目の操作後, 『相手に渡す前の「有利な状態」で am + bm + cm = 2 を 満たす最大の整数 m を M(j) 』, 相手から戻された状態から, 再び「有利な 状態」にしたときの am + bm + cm = 2 を満たす最大の整数 m を M (j + 1) , am + bm + cm = 2 を満たす整数が存在しないとき, すなわち, 自分が「すべ なので an = a0n anÄ1 = a0nÄ1 anÄ2 = a0nÄ2 .. . al+1 = a0l+1 al 6= a0l ての駒を取り終わった状態」のときは M (j) = Ä1 とする（「有利な状態」で ないとき M(j) は定義しない）と, M(j) > = M (j + 1) が成立する。 と変化したとすると al + bl + cl 2 f 0 ; 2 g は a0l + bl + cl 2 f 1 ; 3 g すなわち さらに M (j) = M (j + 1) > = 0 が無限に続くと A ; B ; C の少なくとも 1 つは, いつまでも 2M(j) 以上となり となる。 これは A ; B ; C は有限回ですべてが 0 となることに矛盾する。 a0n + bn + cn 2 f 0 ; 2 g a0nÄ 1 + bnÄ1 + cnÄ1 2 f 0 ; 2 g したがって a0nÄ 2 + bnÄ2 + cnÄ2 2 f 0 ; 2 g .. . 0 al+1 + bl+1 + cl+1 2 f 0 ; 2 g a0l + bl + cl 2 f 1 ; 3 g ここで M(H) > = 0 ならば K> = H で M (K) > M(K + 1) を満たす K が存在し, ある自然数 L について M(L) = Ä1 が成立する。 である。 証明 I a0l ; bl ; cl のうち cl が 1 であるとすると 証明 II から, 「有利な状態」で相手に渡すことができれば必ず勝つことができる。 l C> = 2 なので, ゲームは終了しない。 ことが証明できた。 1
© Copyright 2024 ExpyDoc
