27 27 *n と *n は同サイズの山2つのnimは必敗なので等価。同サイズでなければ必勝なので等価でない 28 28 29 29 定理 30 30 - G1≡*n1, ..., Gk≡*nk ならば、G={G1, ..., Gk} ≡ *mex(n1,...,nk) 31 31 where mex(S) = min(nat \setminus S) 32 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 48 @G を G のnim値とする。つまりG≡*@G 37 49 G = X + Y ならば @G = @X xor @Y 38 50 山が複数のnimの勝敗は全部xorとった1つ山のnimに等しいのと同じ原理。