Artifact 5e1e68bb34c03f9de66d8d793311b2316f1e00da
// SRM338 Div1 LV3
定理のステートメント
対象となるゲーム
- 二人ゲーム
- 二人とも動かせる手の集合は同じ
- 動かせなくなった方が負け
- 無限ループしない
nim
- サイズ s1, s2, .., sk の山がある
- どれか一つ山を選んで 1 ～ 山サイズ の任意個取り除ける
- 最後の山を取った方が勝ち（山がなくなって打つ手が無くなった方が負け）
*n をサイズ n の山が1個だけの nim とする
- *0 は負け
- *n は勝ち n>=1
ゲーム
- 状態 G から打てる手で遷移する先を G1, ..., Gk とする
G = {G1, ..., Gk} と書く
等価
- 二つのゲームG, Fが等価なことを G ≡ F と書く
等価というのは勝ち負け一致よりもっと強い。二つのゲームの和を取ると必敗になること
*n と *n は同サイズの山2つのnimは必敗なので等価。同サイズでなければ必勝なので等価でない
定理
- G1≡*n1, ..., Gk≡*nk ならば、G={G1, ..., Gk} ≡ *mex(n1,...,nk)
where mex(S) = min(nat \setminus S)
帰納的に、全てのゲームはなんらかの *n と等価
定理の証明
- {G1, ..., Gk} は *mex(n1,...,nk) と等価。
つまり和を取ると必敗。
*mex(n1,...,nk) 側を動かした場合、相手は対応する Gi に遷移する。
{G} 側を mex(n1,...,nk) より小さいゲームに動かした場合、mex側を対応する値に変える。
{G} 側を mex より大きいゲームに動かした場合、その大きいゲームをmexに下げる。
で両側等価を保ててしまう。
等価(和を取ると必敗) => 勝ち負け一致 の証明
- 偶奇を考えれば良い。必勝ゲーム+必敗ゲーム なら初手で必勝を必敗に変えて常にその状態を
保てば勝てる。ゆえに一致しないなら和をとったゲームは必勝。
おまけ
@G を G のnim値とする。つまりG≡*@G
G = X + Y ならば @G = @X xor @Y
山が複数のnimの勝敗は全部xorとった1つ山のnimに等しいのと同じ原理。