Artifact Content
Not logged in

Artifact d63874d4c871cfe6a11e5aec18ce96f10590e9f0


// 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 と等価


おまけ
  @G を G のnim値とする。つまりG≡*@G
  G = X + Y ならば @G = @X xor @Y
  山が複数のnimの勝敗は全部xorとった1つ山のnimに等しいのと同じ原理。