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