27 *n と *n は同サイズの山2つのnimは必敗なので等価。同サイズでなければ必勝なので等価でない 27 *n と *n は同サイズの山2つのnimは必敗なので等価。同サイズでなければ必勝なので等価でない 28 28 29 定理 29 定理 30 - G1≡*n1, ..., Gk≡*nk ならば、G={G1, ..., Gk} ≡ *mex(n1,...,nk) 30 - G1≡*n1, ..., Gk≡*nk ならば、G={G1, ..., Gk} ≡ *mex(n1,...,nk) 31 where mex(S) = min(nat \setminus S) 31 where mex(S) = min(nat \setminus S) 32 帰納的に、全てのゲームはなんらかの *n と等価 32 帰納的に、全てのゲームはなんらかの *n と等価 33 33 > 34 定理の証明 > 35 - {G1, ..., Gk} は *mex(n1,...,nk) と等価。 > 36 つまり和を取ると必敗。 > 37 *mex(n1,...,nk) 側を動かした場合、相手は対応する Gi に���移する。 > 38 {G} 側を mex(n1,...,nk) より小さいゲームに動かした場合���mex側を対応する値に変える。 > 39 {G} 側を mex より大きいゲームに動かした場合、その大きいゲームをmexに下げる。 > 40 で両側等価を保ててしまう。 > 41 > 42 等価(和を取ると必敗) => 勝ち負け一致 の証明 > 43 - 偶奇を考えれば良い。必勝ゲーム+必敗ゲーム なら初���で必勝を必敗に変えて常にその状態を > 44 保てば勝てる。ゆえに一致しないなら和をとったゲームは必勝。 > 45 34 46 35 おまけ 47 おまけ 36 @G を G のnim値とする。つまりG≡*@G 48 @G を G のnim値とする。つまりG≡*@G 37 G = X + Y ならば @G = @X xor @Y 49 G = X + Y ならば @G = @X xor @Y 38 山が複数のnimの勝敗は全部xorとった1つ山のnimに等しいのと同じ原理。 50 山が複数のnimの勝敗は全部xorとった1つ山のnimに等しいのと同じ原理。