組合せゲーム

今の所、過去問並べただけ。

1 後退解析
- 1.1 DAGの後退解析
2 勝敗の単調性
3 不変量に着目する
4 グラフ理論
5 Nim
6 非不偏ゲーム
7 ニムの代数構造

後退解析

非不偏ゲームの遷移は、各ゲームを頂点とする有向グラフ $G$ で表すことができる。勝敗は $v \in V(G)$ について

$v$ が $\mathcal{P}$ のとき、任意の $v’ \in v$ は $\mathcal{N}$
$v$ について、任意の $v’ \in v$ が $\mathcal{N}$ のとき、$v$ は $\mathcal{P}$

である。$\mathcal{P}$ であることが確定している頂点から順に決定すればよい。勝敗の確定しなかった頂点は勝敗の確定しなかった頂点に遷移するのが最適である。従って、永遠に勝敗が決まらず、$\mathcal{D}$ である。将棋ではこのような状態を避けるため、同一局面が4回現れると引き分けとする、千日手が設定されている。

$\delta^+(v) = \emptyset$ のとき $ v \in \mathcal{P}_0$ とする。先手がどのように指しても後手が $n$ 手以下で $\mathcal{P}_0$ にできる局面を $\mathcal{P}_n$ とする。つまり、$\forall u \in \delta^+(v), \exists w \in \delta^+(u), \exists k, 1 \leq k \leq n \land v \in \mathcal{P_k}$ のとき $v \in \mathcal{P}_{n+1}$ とする。明らかに $\mathcal{P}_n \subset \mathcal{P}_{n+1}$ である。有向グラフ $G, H$ で表される二つのゲームの和は、有向グラフ $G \times H$ で表せる。

ニム数が未確定の頂点は、暫定的にニム数を $\infty$ として、帰納的にニム数を計算していく。$m = \mathrm{mex}_{v’ \in v}(\mathcal G(v’))$ とする。$\mathcal{G}(v’) > m$ となる任意の $v’$ が有限回打ち消し可能な選択肢であることが分かっているとき、$\mathcal{G}(v) = m$ としていく。それ以上更新ができなくなったところで、ニム数が $\infty$ である頂点 $v$ は $\mathcal{G}(v) = \infty(\mathcal{A})$ とする。ただし、$\mathcal{A} = \{a \in \mathbb{N}:a = \mathcal{G}(v
‘) : v’ \in v\}$ である。$\mathcal{P}$ からは $\mathcal{N}$ にしか遷移できず、$\mathcal{N}$ からは $\mathcal{P}$ に遷移できるので、$\mathcal{P}$ から $\mathcal{N}$ への遷移は打ち消し可能な選択肢であるが、打ち消し可能な回数で帰納法をすることにより、打ち消し可能な回数は有限回であることが分かる。$v$ の打ち消し可能な回数を $\mathrm{rank}(v)$ と置く。

$\mathcal{G}(v) = 0$ $\Leftrightarrow$ $v$ は $\mathcal{P}$ 局面
$\mathcal{G}(v)$ が正整数ならば $v$ は $\mathcal{N}$ 局面
$\mathcal{G}(v) = \infty(\mathcal{A})$ で $0 \in \mathcal{A}$ ならば、$v$ は $\mathcal{N}$ 局面
$\mathcal{G}(v) = \infty(\mathcal{A})$ で $0 \not\in \mathcal{A}$ ならば、$v$ は $\mathcal{D}$ 局面

$\mathrm{rank}(u) = \infty$ ならば $v$ に関わらず $\mathrm{rank}(u+v) = \infty$ である。ここから、ゲームの和のニム数は
$$\mathcal{G}(u + v) = \mathcal{G}(u) \oplus \mathcal{G}(v)$$
となる。ただし、$\infty(\mathcal{A})\oplus \infty(\mathcal B) = \infty(\emptyset), \infty(\mathcal{A})\oplus b = \infty(\mathcal{A}\oplus b) = \infty(\{a \oplus b : a \in \mathcal{A}\})$ とする。

非不偏ゲームで A から B の遷移があり、A の帰結類を求める場合、A の選択肢と B の選択肢の共通部分に $\mathcal{P}$ がある場合とそうでない場合で場合分けができる。前者の場合、A は $\mathcal{N}$ である。後者の場合は、共通部分を全て存在しないものとしてゲームを解析できる。

$\mathcal P$ に接続する頂点は全て $\mathcal N$ である。例えば Wythoff’s game で同じx座標の $\mathcal P$ 局面が二つ以上ないのはこの事実からすぐに分かる。

ニム数 $n$ の頂点が存在する最小のグラフは $K^{n+1}$ を頂点番号の小さい方から大きい方へ向きづけたグラフである。従って、辺は少なくとも $\Theta(n^2)$ 個必要である。ニム数は、ゲームの誕生日の順に頂点を貪欲に彩色したときの色数に等しい。

DAGの後退解析

DAGの場合、後退解析は簡略化できる。閉路が存在しないので、勝敗が決まらない頂点は存在しない。

ゲームの終了状態に、勝敗を割り振る。
勝敗が未確定の頂点を、一時的に、負け状態と仮定する。
トポロジカル順序の逆順に頂点 $v$ を見る。
$v$ が勝ちなら何もしない。$v$ が負けなら、$v$ に遷移可能な頂点を勝ちにする。

トポロジカル順序が自明ならば、手で勝敗が簡単に書き下せる場合がある。

問題1:石が $N$ 個ある。交互に $1$ 個以上 $K$ 個以下の石を取り去る。石が取れなくなった方が負け。どちらが勝つか。$O(1)$で求めよ。（有名問題、yukicoder 8）

DAGの後退解析をすればよい。先手の敗北条件は $N = 0 \pmod {K+1} $ である。

問題2:問題1において、取り去ったあとの石の個数が $x_1, x_2, \ldots, x_M$ のいずれかになる操作が禁止されたとするとする。勝敗を $O(N+M)$ で求めよ。（yukicoder 1313）

DAGの後退解析。

問題3:問題1において、相手が直前に取り除いた石と同数の石が取り除けない場合の勝敗を $O(N)$ で求めよ。（yukicoder 1770）

DAGの後退解析。「直前に相手が $x$ 個取り除いてなければ」勝ちという条件を論理和で配るので、各頂点の状態は

負け
直前に相手が $x$ 個取り除いなければ、勝ち
直前に相手が何個取り除いていようが、勝ち

のいずれか。１つ目の状態が最短でも $K+1$ 個おきにしか起きないので、更新回数は全体で $O(N)$ になる。

問題5:問題1において、取り去ったあとの石の個数が2進表記したとき 1 が奇数個となる操作が禁止されたとするとする。勝敗を $O(N)$ で求めよ。（SRM 701 Div2 Hard）

DAGの後退解析。問題2の類題。

問題1において、K+1の倍数でも取り除けるとするとどちらが勝つか。（Russia 2011, adapted）

問題6:有向グラフ G の各頂点には数字が書いてある。頂点 1 に駒を置き、交互に

駒を辺に沿って動かす。
ゲームを終了する。

のどちらかを選ぶ。十分長いターンが経ってもまだゲームが終了していないときは、後手の手番後に強制終了する。ゲームが終了したときに、駒が置いてある頂点の数字を先手は最大化、後手は最小化したい。数字はいくつになるか。（ARC038D）

スコアについて二分探索すると後退解析になる。

問題11:
いくつかの根付き木が与えられる。交互に次のいずれかの操作を繰り返す。

1ターン目ならば駒を好きな木の根に置く。
葉でなければ、駒を子に移動する
葉であれば、まだ選ばれていない木の根に駒を移動する

操作できなくなったほうが負け。どちらが勝つか。
（Kupc2019E）

木の根を選び、葉まで駒を動かしてから、次の根を選ぶのが先手後手のどちらになっているか考える。

先手の意思で、先手後手を入れ替えることができる
先手の意思で、先手後手をそのままにすることができる

(True, True) を選ぶと先手の勝ち。(False, False) を選ぶと後手の勝ち。従って (False, False) が選ばれるのは最後。(True, False) ならば先手後手は必ず入れ替わる。(False, True) ならば先手後手は必ずそのまま。従って、(False, True) は勝敗と無関係。

勝敗の単調性

あるパラメータ A が大きいほど先手が有利ならば、

$f_1(S, a) :=$ 状態 S でパラメータ A = a のときの勝敗

を持つ dp から

$f_2(S) :=$ 状態 S のとき、先手が勝つための A の最小値

を持つ dp に変更でき、状態数が減らせる。

X さんにとっての必勝法が存在するゲームを考える。X さんにとって、局面 $B$ が局面 $A$ と比べて劣勢であるとする。ならば、$A$ に遷移した後に、$B$ に遷移しないような必勝法が存在する。つまり、Xさんにとって B が A に比べて劣勢であるとき、$A < B$ と定めると、局面が $G_1, G_2, \ldots $の順で遷移して、 $i < j$ のとき $G_i > G_j$ または $G_i, G_j$ が比較不能が成り立つようなものが存在する。

問題13:
N 個の石が相異なる非負整数座標 $x_1, x_2, \ldots, x_N$ ($0 < x_1 \leq \cdots < x_N$) に置かれている。交互に、最も大きい座標に置かれている石を、他の石と重ならないように、より小さい非負整数座標に置き換える。操作できなくなったほうが負け。どちらが勝つか。
(ARC137C)

単調性より、$x_N$ が大きいほど先手が有利。戦略盗みにより、$x_N-x_{N-1} \geq 2$ ならば先手の勝ち。さもなくば、$x_N-x_{N-1} =1$ を保ちながら遷移するしかないので、最適手は $O(N)$ でシミュレートできる。

問題14:木の根以外の頂点に得点が書き込まれている。駒が根においてある。次の手順をゲーム終了まで繰り返す。

先手は好きな頂点を1つ選び書き込まれた数字を零にする。
後手は子に駒を移動する。葉に移動した場合はゲーム終了。葉でもなくとも、後手の意思で終了にできる。

ゲーム終了時点で駒がある頂点に書き込まれた数字が得点になる。先手は得点を最小化、後手は得点を最大化したい。何点になるか。(ABC246G)

得点はX点以上か？について二分探索して、後退解析。取り除ける頂点が多いほど先手は有利なので、dp[v] := (頂点 v の部分木でゲームをしたとき得点を X 未満にするには、予め何個の頂点の得点を零にしておく必要があるか) について dp ができる。

問題12:
$a_1, a_2, \ldots, a_N$ 個の石からなる山が $N$ 個ある。Aさんは右端の山から好きな個数の石を取ることができ、Bさんは左端の山から好きな個数の石を取ることができる。交互に操作を行う。操作できなくなったほうが負け。どちらが勝つか。
(AGC048D)

指せる手の単調性より

$a_1$ が大きいほど A さんが有利
$a_N$ が大きいほど B さんが有利

だから、操作は

山から石を一つだけ取る
山から石を全て取る

のどちらかであるとしても勝敗は変化しない。

残っている山が $l, \ldots, r$ 番目で、$l$ 番目の山以外は初期状態と石の個数が同じである。A さん先手で、A さんの勝ちとなる $a_l$ の最小値 $f(l, r)$
残っている山が $l, \ldots, r$ 番目で、$r$ 番目の山以外は初期状態と石の個数が同じである。B さん先手で、B さんの勝ちとなる $a_r$ の最小値 $g(l, r)$

$f(l, r-1), g(l+1, r)$ から $f(l, r), g(l, r)$ が $O(1)$ で求まる。

不変量に着目する

二部グラフ

二部グラフ上のゲームの場合、各部集合が何らかの不変量と関連していることが多い。特に、グリッドグラフが頻出である。

問題8:$H$ 行 $W$ 列のマスがある。N 個の駒を $(x_i, y_i)$ $(1 \leq i \leq N)$ に置いた。交互に駒を一つ選んで一つ左か下に動かすことを繰り返す。同じマスに複数の駒をおいてはいけない。操作ができなくなったほうが負け。どちらが勝つか。（yukicoder2951）

$(x+y) \bmod 2 = 0$ に置かれた駒の個数 A
$(x+y) \bmod 2 = 1$ に置かれた駒の個数 B

と置く。(A, B) の勝敗を2次元平面にプロットすると、のようになる。青マスが勝ち。端のはてなのマスは、はてな同士を行き来することで勝敗が決まらないように思えるが、最終的に $x = y$ 方向に移動せざるを得なくなることから、外側のはてなの方が勝ちになる。よって、$A – B \neq 0 \pmod 3 \Leftrightarrow $ 先手必勝。

問題15:グリッドグラフの部分グラフと、非隣接な頂点 s, t が与えられる。交互にグラフの頂点を削除する。自分の操作で頂点 s, t を非連結にした方が勝ち。先手と後手のどちらが勝つか。(UTPC2021L)

s, t の点連結度が1のとき先手の勝ち。
s, t の点連結度が2のとき、点連結度を1にしたほうが負けなので、その直前では、2つの内素な s-t パスだけになる。二部グラフなので、このときの頂点数はそれまでの操作によらない。従って勝敗も O(1) で分かる。

グリッドグラフ

先手は1×1の白のパーツ、後手は1×1の黒のパーツをお互いに重ならないように置く。2×2の自分の色ができた方が勝ち。引き分けになることを示せ。

上手くマッチングを作る。

先手は1×2または2×1の白のパーツ、後手は1×2または2×1の黒のパーツをお互いに重ならないように置く。1×5または5×1の自分の色ができた方が勝ち。引き分けになることを示せ。

先手は1×1の白のパーツ、後手は1×1の黒のパーツをお互いに重ならないように置く。1×5または5×1の自分の色ができた方が勝ち。黒の2×2が白の2×2より先に発生しないような後手の手順が存在することを示せ。

偶奇

偶奇が不変量に関連していることがある。

問題7:正整数列が与えられる。次のどちらかの操作を交互に行う。

すべての要素を 1 減らす。全ての要素が正整数である場合のみこの操作ができる。
正整数を一つ選び、1 減らす。

操作ができなくなった方が負け。どちらが勝つか O(1) で求めよ。

（KUPC2020春E）

（最小値、総和）の偶奇の遷移は下図のようになる。$N$ の偶奇によらず二部グラフになる。最小値 0 だと、全要素を 1 減らす遷移ができないが、可能な遷移は部分グラフであるので、なお二部グラフである。

問題9:$\gcd(A) = 1$ の数列 $A$ がある。先手と後手は交互に「$2$ 以上の要素を選んで $1$ 減らしてから全体を $\gcd(A)$ で割ること」を繰り返す。操作できなくなったほうが負け。どちらが勝つか。（AGC010D）

gcd で割らなければ、$\sum (A_i-1)$ 回操作ができる。A の要素に奇数が含まれていれば gcd は奇数で、$A_i, A_i/\mathrm{gcd}(A)$ の偶奇は同じ。従って、$\sum (A_i-1)$ が不変。A の要素に奇数が一つ以上含まれていれば、奇数を二つ以上にして相手に渡せる。従って、 gcd(A) = 1 より奇数は必ず含まれているので $\sum (A_i-1) = 1 \pmod 2$ ならば先手の勝ち。A に奇数が一つだけ含まれていて、$\sum (A_i-1) = 0 \pmod 2$ ならば、その奇数から 1 引いて gcd で割ってから相手に渡すことになる。このような操作は $O(\log(\max(A))$ 回しか行われない。

問題10:それぞれ、$a_i$ 個の石（$1 \leq i \leq N$）からなる山がある。先手と後手は交互に次のどちらかの操作をする。

山を２つに分割する。
各山から石を一つ取り除く。ただし、各山に2つ以上の石がなくてはならない。

操作できなくなったほうが負け。どちらが勝つか。（yukicoder1852）

(i) : $\min(a)=1$ のとき、 $S := \sum (a_i-1)=1 \Leftrightarrow $ 先手の勝ち。
(ii) : $\min(a) > 1$ のとき、$a_1$ を $1, a_1-1$ に分割すると、(i) の $S \leftarrow S-1$ の場合に帰着される。従って、$S$ が奇数なら先手の勝ち。さもなくば、$\forall i, a_i \leftarrow a_i-1$ の操作しか先手はできず、後手に $S \leftarrow S-N$ の状態で渡される。$N$ が奇数なら、先手の負け。$N$ が偶数なら、$\min(a)$ の偶奇で勝敗が決する。

問題16:
グラフGが与えられる。交互に辺を追加する。連結になった方が負け。どちらが勝つか。
(AOJ2376)

連結になる直前の連結成分の大きさが $k, n-k$ とすると、追加された辺の本数は $n(n-1)/2-|E|-k(n-k)$ である。従って $k(n-k)$ の偶奇によって勝敗が決まることが分かる。$n$ が奇数ならば、$k(n-k) \bmod 2$ は $k$ に依らず決定する。従って、以降は $n$ が偶数の場合のみを考える。先手は、偶成分が2つの状態を作ると勝ち、あるいは、奇成分が2つの状態を作ると勝ちのどちらかに排反でなる。次の三つの数をパラメータにして考察する。

偶成分の個数
奇成分の個数
連結成分の個数を変えずに追加できる辺の個数の偶奇

この三つの数は、各操作によって次のように変化する。

偶成分と偶成分をマージ $(-1, 0, 1)$
偶成分と奇成分をマージ $(0, -1, 1)$
奇成分と奇成分をマージ $(1, -2, 0)$
連結成分内で辺を追加 $(0, 0, 1)$

ところで$$(-1, 0, 1) + (1, -2, 0) = (0, -2, 1)$$だから
偶成分2つより、奇成分2つの方が作りにくい。先手が偶成分2つの状態を作りたいとする。奇成分は常に偶数個あるから、偶成分が一つでもある状態で回ってこれば、偶成分が2つ以上にして相手に渡せる。相手は偶成分を高々一つしか減らせないので、これは勝ちである。奇成分しかない場合を考える。相手に偶成分を作ってもらうために、奇成分のみの状態で手番を相手に渡す必要がある。つまり、連結成分内の辺の追加で手番を入れ替えなければならない。頑張って場合分け。

問題:
グラフGが与えられる。偶点を交互に取り除く。行動できなくなったほうが負け。どちらが勝つか。

偶点の偶奇 $a$ は $|V|-\sum_v d(v) = |V|-2|E|$ に等しい。偶点 $v$ を除くと $a \leftarrow a-1-2d(v) \bmod 2$ となるから、$a$ の偶奇で勝敗が決まる。

グラフ理論

グラフGが与えられる。先手と後手は交互に辺を選ぶ。全ての操作が終わった後、後手が選んだ辺が全域グラフであれば後手の勝ち。後手が勝つための必要十分条件はGに辺素な2つの全域木が取れることであることを示せ（Lehman）。

後手が勝つならば、先手はその戦略を採用することで、先後どちらも2つの全域木が取れる。逆にこの時、後手が勝てることは、木がマトロイドであることと基交換定理から従う。

Nim

一山崩し

与えられた $S \subseteq \mathbb{N}$ から好きな数 $x$ を選んで交互に $N \leftarrow N-x$ とする。それ以上操作できなくなった方が負け。$S = \{s_1, s_2, \ldots, s_n \}_{<}$ として、このゲームを
$\mathrm{sub}(S)$ あるいは $\mathrm{sub}(s_1, s_2, \ldots, s_n)$
と書くことにする。また、$S$ が有限集合の時、$\mathrm{allbut}(S)=\mathrm{sub}(\mathbb{N} \setminus S)$ と書く。

$\forall, x \in S, \exists y ∈ S, x + y = C$ ならば周期 $C$ と分かる。また、$\{1, 2, \ldots, k\} \subseteq S$ かつ $\forall x ∈ S \setminus \{1, 2, \ldots, k\}, (k + 1) | x$ ならば、$N = 0 \pmod {k + 1}$ ⇔ 後手勝ちである。

$\#S \leq 2$ の時の勝敗は？
$S = \{a, b\}$ と置く。$a < b$ としてよい。$N \leftarrow N \bmod {(a+b)}$ としても勝敗は変わらない。$N < b$ かつ $\lfloor N/a \rfloor =1 \pmod 2$ または $b \leq N < a + b$ のとき先手勝ち。

$S = \{s_1, s_2, \ldots, s_n\}_{<}$ とする。$s_{i+1} \leq s_i + s_1$ とするとニム列は $0^{s_1}1^{s_2-s_1}2^{s_3-s_2-s_1} \cdots$ のようになって、周期はある $i$ を用いて $s_1+s_i$ となる。

$\mathrm{sub}(S)$ のニム列が純周期的で周期 $p$ のとき、$\mathrm{sub}(S\cup \{mp\}) $ $(m \geq 0)$ と同じニム列を持つ。

ニム列はsubは周期的、allbutは算術周期的になる。

$2s_n < b$ のとき $G=\mathrm{allbut}(s_1, s_2, \ldots, s_n)$ と $H=\mathrm{allbut}(s_1, s_2, \ldots, s_n, b)$ のニム列は等しい。

帰納法で示す。$n < b$ ならば明らかに$\mathcal{G}_H(n)=\mathcal{G}_G(n)$ である。$n < k$ で成り立つとする。$\mathcal{G}_G(k) \neq \mathcal{G}_H(k)$ ならば $\mathcal{G}_H(n-b) = g_H(n)$ である。
帰納法の仮定より
\begin{align}
\mathcal{G}_G(n-b) \leq \mathcal{G}_G(n-b+s) \\
\Leftrightarrow \mathcal{G}_H(n-b) \leq \mathcal{G}_H(n-b+s) \\
\end{align}
である。
$n-b < n-b+s_n < n-s_n$ より $n-b+s_n$ は $H$ の選択肢であるから、$\mathcal{G}_H(n-b) < \mathcal{G}_H(n-b+s)$ であるが、これは $x \neq n-b, x < n-s_n$ で $\mathcal{G}_H(x) = \mathcal{G}_H(n-b)$ の存在をしているので矛盾。

$ax+by > 0$ となる格子点の集合 $U$ を考える。sub(a, b) は $N = ax + by$ となる格子点 $(x, y)$ から格子点 $(x-1, y), (x, y-1) \in U$ のどちらかに移動を繰り返すゲームだともいえる（ARC144F）。

二山崩し

$n$ 個の石からなる山がある。A, B は交互に山から石を取る。直前に相手が石を $k$ 個取ったならば、$2k$ 個まで石を取れる。石を取れなくなったほうが負けである。ただし、初手ですべての石を取ってはいけない。（フィボナッチニム）

現在の石の個数 $n$ を固定すると、直前に相手が取った石の個数 $x$ が大きいほど勝ちやすい。$n$ をフィボナッチ符号で表したときの最小のフィボナッチ数 $F_k$ が $x \leq F_k$ なら勝ちである。$n-F_k$ を相手に渡す。$n’=n-F_k\neq 0$ とする。相手は $y$ 個の石を取り除いたとする。 $n’$ の最小のフィボナッチ数を $F_l$ ($l < k$) としたとき、 $F_{l}-y$ のフィボナッチ符号における最小のフィボナッチ数が $2y$ 以下であることを言えばよい。それは次のような計算により分かる。\begin{align}
101010 + 1 &= 101011 \\
&= 101100 \\
&= 110000 \\
&= 1000000 \\
\end{align}

\begin{align}
10101001 + 10 &= 10101011 \\
&= 10101100\\
&= 10110000\\
&= 11000000\\
&= 100000000\\
\end{align}従って、$n$ がフィボナッチ数ならば後手の勝ち、さもなくば、先手の勝ち。

石の個数が $a, b$ の山がある。「片方から好きな個数の石を取り除く」「両方から同じ個数の石を取り除く」の何れかができる。操作できなくなった方が負けである場合、どちらが勝つか(Wythoff’s game)

$(a, b)$ の遷移をマス目上に書いてみると、\begin{align} x_i &= \mathrm{mex}\{x_j, y_j\}\\ y_i &= x_i + i\end{align} によって定まる二つの山 $(x_i, y_i), (y_i, x_i)$ が負けであることが分かる。

code

レイリーの定理より、$\alpha, \beta$ が無理数で $1 / \alpha + 1 / \beta = 1$ ならば $\{ \lfloor i\alpha \rfloor : i \in \mathbb{N}\}, \{\lfloor i\beta \rfloor : i \in \mathbb{N}\}$ は $\mathbb N$ の分割である。特に黄金比 $\phi$ は $1 / \phi + 1 / \phi^2 = 1$ を満たし、$x_i = \lfloor i\phi \rfloor, y_i = \lfloor i \phi^2\rfloor$ となる。確かに、\begin{align} & i + x_i = \lfloor i (\phi +1)\rfloor = \lfloor i \phi^2\rfloor = y_i \\ &\lfloor n\phi \rfloor = \mathrm{mex}\{\lfloor i\phi \rfloor, \lfloor i \phi^2 \rfloor : i < n\}\end{align} となっている。

（レイリーの定理の証明）無理数 $\alpha, \beta$ が $1 / \alpha + 1 / \beta = 1$ を満たすとする。$A := \{i\alpha : i \in \mathbb{N}\}, B := \{i\beta : i \in \mathbb{N}\}$ と置く。$i \alpha = j \beta \Leftrightarrow \alpha / \beta = j / i$ は、左辺 $\alpha / \beta = \alpha-1$ が無理数、右辺 $j/i$ が有理数なので、起こりえない。従って、$A, B$ は交わらない。$f(x) = \#\{y \leq x : y \in A \cup B\}$ とすると、$f:A\cup B \rightarrow \mathbb{N}$ の全単射である。$f(i\alpha) = \lfloor i \alpha \rfloor, f(i\beta) = \lfloor i\beta \rfloor $ なので、$\{\lfloor i \alpha \rfloor : i \in \mathbb{N}\}$ と $\{\lfloor i \beta \rfloor : i \in \mathbb{N}\}$ は相補的である。
$\mathbb{N}$ の分割 $A = \{a_1, a_2, \ldots,\}_<, B = \{b_1, b_2, \ldots, \}_<$ が $b_i = a_i + i, a_1 = 1$ を満たすならば、そのような数列は明らかに一通りしかなく、レイリーの定理はその表現を与える。一方、フィボナッチ進法を使って、そのような集合を別の方法で表現することができる。$x \leq y$ の先手負けの状態 $(x, y)$ のゼッケンドルフの表現は次の様になっている。

i	x	y	i のゼッケンドルフの表現	x のゼッケンドルフの表現	y のゼッケンドルフの表現
0	0	0	00000000	00000000	000000000
1	1	2	00000010	00000010	000000100
2	3	5	00000100	00001000	000010000
3	4	7	00001000	00001010	000010100
4	6	10	00001010	00010010	000100100
5	8	13	00010000	00100000	001000000
6	9	15	00010010	00100010	001000100
7	11	18	00010100	00101000	001010000
8	12	20	00100000	00101010	001010100
9	14	23	00100010	01000010	010000100
10	16	26	00100100	01001000	010010000
11	17	28	00101000	01001010	010010100

$\mathcal{P}$ ポジションは $(0, 0)$ または $(\overleftarrow{x}, x)$ の形をしている。また、$x$ の正規ゼッケンドルフ表現の LSB は偶数の位置に、$\overleftarrow{x}$ の LSB は奇数の位置にある。LSB の偶奇性と、$\overleftarrow{x}, x$ は一方からもう一方が定まることから、$(\overleftarrow{x}-i,x), (\overleftarrow{x},x-i), $ は $\mathcal{P}$ にならない。
$x = \overrightarrow x + \overrightarrow{\overrightarrow{x}}$ なので、\begin{align}
& \overleftarrow x-x \\
={}& (y + \overrightarrow x)-x \\
={}& \overrightarrow{x}
\end{align}
である。$\overrightarrow{x}$ は LSB が奇数の位置にあるゼッケンドルフ表現で表せる。各正整数 $n$ に対して、このような表現はただ一つ存在し、第二正規ゼッケンドルフ表現と呼ぶ。第二正規ゼッケンドルフ表現は $n-1$ の正規ゼッケンドルフ表現に $1$ を足せば得られる。例えば、$1010 + 1 = 10000$　である。一意性は、第二正規ゼッケンドルフ表現 $1$ を引くと $n-1$ の正規ゼッケンドルフ表現になり、正規ゼッケンドルフ表現が一意であることから従う。以上から、$(\overleftarrow x, x)$ が $\mathcal P$ ならば $(\overleftarrow x-i, x-i)$ は $\mathcal{P}$ でない。

$(y, x) $ ($y \geq x$) が $\mathcal{N}$ だとする。(i) $x$ の LSB が偶数の場合：$y \geq \overleftarrow{x}$ ならば $(y-i, x)$ で $\mathcal{P}$ に遷移できる。そうでないとする。$\overrightarrow{d}:=y-x < \overleftarrow{x}-x$ なので、$(\overleftarrow d, d) = (y-i, x-i)$ となる $i$ が存在して $\mathcal{P}$ に遷移できる。ただし、$\overrightarrow d$ は第二正規表現とする。(ii) $x$ の LSB が奇数の場合：$x$ のLSBは1番目にはならないことに注意。$y \geq x \geq \overrightarrow {x}$ なので $(y-i, x)$ で $\mathcal{P}$ に遷移できる。

$\phi = (1+\sqrt{5})/2$ として正整数 $x$ を $x-1$ か $\lfloor x / \phi \rfloor $ で置き換えることを交互に繰り返す。ただし、$x$ より小さい非負整数で置き換えなくてはならない。ニム数を求めよ。

$k = \lfloor i \phi \rfloor $ と置くと、$i\phi < k + 1 \Leftrightarrow i – 1/\phi < k$ なので $\lfloor \lfloor i\phi \rfloor /\phi \rfloor = i – 1$ である。同様に $k = \lfloor i\phi^2 \rfloor $ と置くと \begin{align} k \leq &i \phi^2 < k + 1 \\ \Leftrightarrow i \phi – 1 / \phi < & k/\phi \leq i \phi \\ \Leftrightarrow i+i / \phi -1/\phi < &k/\phi \leq i + i / \phi \end{align} なので $\lfloor\lfloor i \phi^2 \rfloor/\phi \rfloor = \lfloor i\phi \rfloor $ である。それぞれのフィボナッチ進法を考えることで、ニム数が求まる。

複数山崩し

石の個数が $x_1, x_2, \ldots, x_n$ 個の山がある。先手は山を一つ以上選びそれぞれから $a$ 個の石を取り去る。後手は山を一つ以上選びそれぞれから $b$ 個の石を取り去る。操作できなくなった方が負けであるとき、勝つのはどちらか（ARC143C）。

真似っこ戦略により、$x_i \leftarrow x_i \bmod (a+b)$ としても結果は変わらない。全ての要素が $a$ 未満ならば先手の負け。さもなくば、先手は可能な限り多くの山から $a$ 個ずつ石を取り去って、相手に渡す。このとき、$b$ 個以上の山があれば後手の勝ち、さもなくば先手の勝ち。

非不偏ゲーム

左右のそれぞれが先手のときの勝敗を個別に分析する必要はない。

左右のうち、右が先手の時の勝敗が完全に分かっている。
そのことから、左が先手のときの最善の一手目が得られる。

このとき、左が先手の時の勝敗が完全に得られる。（Xならば確実に勝つ/負ける）という条件が存在する方が条件が簡単になりやすく、そちらを主にして勝敗を分析するとよい。

k ($\geq 3$) 個の相異なる素数の積からなる数 $N$ が与えられる。A, B は交互にNの約数である合成数を書く。
Nを書いてはいけない。また、すでに書かれた数に対して、互いに素な数や、約数・倍数である数は書けない。どちらが勝つか。（Saint Petersburg 1997）

まずAは相異なる2つの素数の積 $pq$ を書く。Bは $p$ か $q$ の倍数であって、$pq$ の倍数でないものを書く。 $pk$ を書いたとする。Aは常に続いて $qk$ が書ける。従って先手の勝ち。

$2k \times 2k$ のマスに A,B は交互に有理数を書き込む。全て書き終わった後に、各行で最大の数を黒く塗る。$1$ 行目と $2k$ 行目を繋ぐ、黒く塗られたパスができると A の勝ち、さもなくば A の負けである。どちらが勝つか。(USAMO　2004-4)

各行について、B は k 個のマスを選び、そのどれかを黒くすることができる。これは、A が書いたマスの行について、応手することでできる。各行 k 個のマスを非連結になるように選べるので、Aの負け。

五目並べ
$5 \times 5$ のマスで、A, B は交互に白と黒の駒を置く。Aは白の駒が5個並んだ列・行・対角の何れかが作れると勝ち、さもなくば負けである。どちらが勝つか。

下のようなペアが作れるので後手の勝ち。
x626y
5ccd3
1bod1
5baa3
y424x

$5 \times 5$ のマスで A, B は交互に 1 と 0 を書き込む。$3 \times 3$ の部分マスのうち、書き込まれた数の和の最大値がAの得点である。Aの得点を 6 点以下に抑えるようなBの戦略を示せ。（IMO Shortlist 1994, C1）

1行目と2行目、3行目と4行目の上下に隣接するマスをペアにすれば良い。

1*4000のマスにA,Bは交互にSかOを書き込む。先にSOSを作ったほうが勝ち。どちらが勝つか（USAMO 1999-5）

書き込める場所が全てS..Sの形になると何を書き込んでもSO.かS.Sができて、相手がSOSを作れるので負け。負けるときは全てこのパターンである。先手は最初の二手で S..S の形を少なくとも一箇所作ることができ、マスの偶奇性も合わせると先手の勝ち。

$1000000$ が書かれている。書かれている数を $n$ として、A, B は交互に $n-1, \lfloor (n+1)/2 \rfloor$ のどちらかで $n$ を置き換える。先に 1 を書いた方が勝ち。どちらが勝つか（Saint Petersburg 2001）

$n$ が偶数とする。偶数 $n$ を持ったとき、$\lfloor(n+1)/2\rfloor$ を渡すと負けるとする。
$\lfloor(n-1)+1)/2\rfloor = \lfloor (n+1)/2\rfloor$
であるから、 $n-1$ に対して、相手の応手は $(n-1)-1$ である。$n=2$ のときに勝ちであるから帰納法により、任意の偶数 $n$ で勝ちである。

A, B は交互に、現在書かれている数をnとして2nかn+1で書き換える。ただし、Nより大きい数を書くことはできない。また、何も書かれていないAの初手では1を書かなくてはならない。書き換えられなくなったほうが負け。どちらが勝つか（IMO Shortlist 2004, C5）

後退解析。偶奇性よりNが奇数なら先手の勝ち。Nが奇数とする。$N = 4k$ のとき、\[2k+1, 4k]\) には勝ちと負けが交互に現れる。$i \in [k+1, 2k]$ は $2i$ に遷移できるので勝ち。$i \in [1, k]$ は $[k+1, 2k]$ に遷移しても仕方がないので、ここでゲームが閉じている。従って、$4k, k$ のゲームの勝敗が一致する。$N = 4k+1$ のとき、$[2k+1, 4k+1]$ には負けと勝ちが交互に現れる。$i \in [k+1, 2k]$ は $2i$ に遷移できるので勝ち。$i \in [1, k]$ は $[k+1, 2k]$ に遷移しても仕方がないので、ここでゲームが閉じている。従って、$4k+1, k$ のゲームの勝敗が一致する。

$\mathbb{Z}/5\mathbb{Z}$ 上の5頂点サイクルの上でA, Bがゲームをする。各頂点 i には変数 $x_i$ が定まっている。初期値は 0 である。各ターンでは、まずAが変数の値を合計で1だけ増やす。Bはある$k$を選び、$x_k,x_{k+1}$を0にする。ある時点で$x_i>2$ となる i があればAの勝ち、そのようなことが永劫起きなければBの勝ち。どちらが勝つか。(IMO Shortlist 2009, C5)

2009枚のコインが表向きに並んでいる。A, Bは交互に連続する50枚のコインを裏返す。ただし、その時、裏返すコインの左端はもともと表でなければならない。それ以上操作できなくなったほうが負け。どちらが勝つか。(IMO Shortlist 2009, C1)

3つの箱がある。各ターンでは A, B, C は順にコインを箱に入れていく。A, B, Cはそれぞれ1か2,2か3,3か1番目の箱に入れられる。コインを入れた箱のコインの枚数が1999枚になると負け。 AとBが協力するとCを負けさせられることを示せ。(Russia 1999)

無限に続く2次元マス目上で、A, Bは交互にそれぞれ o, x を書く。Aは11個の連続する o を縦・横・斜めのいずれかを作れたら勝ちである。BはAの勝ちを阻止できることを示せ。(IMO Shortlist 1994, C6)

石の山が2つある。どちらか片方の山から $2x$ 個取り出して、もう一方の山に $x$ 個加える操作が許されている。A, B が交互に操作して、先に操作できなくなったほうが負け。先手が勝つ条件を求めよ(Russia 1999)

2つの山の個数をそれぞれ $a, b$ と置くと $|a-b| \geq 2$ が先手が勝つための条件。

A, B は交互に $\mathbb{ F}_{2^n}$ の元を取る。取り終わると、それぞれ自身が取った元の集合から元を一つ捨てる。残った元の和が $0$ になったほうが勝ち。どちらも $0$ になった場合は引き分け。A の捨てるカードが $x$ のとき、Aは勝つことができるか。（Shortlist 2014/C8）

A, B は半順序集合 $\mathbb{Z}_{\geq 0} \times \mathbb{Z}_{\geq 0}$ から交互に点を選び、その点の上位集合を取り除く。先に操作できなくなったほうが負けである。このゲームは有限回で終了することを示せ。（chomp）

ヒルベルトの基底定理

60個の空の箱が一列に並んでいる。Aはn個の石を自由に分配する。その後、次の操作を繰り返す。

- Bはある整数 $1 \leq i \leq 59$ を選び、1個目からi個目までの箱の集合Xとi+1個目から60個目までの箱の集合Yに分割する。AはXの各箱から一つずつ石を取り去り、Yの各箱に入れるか、その逆を行う。

途中でからの箱ができるとAの負け。さもなくばAの勝ち。Aが勝つための条件を求めよ。
（2019 ISL C7）

無限に続くマス目上でA, Bは交互にそれぞれo, xを書き込む。Aは連続する5個の縦・横のいずれかのoができると勝ちである。Bがこれを阻止できることを示せ。（1995 Israeli Math Olympiad）

n人が円環に座っている。最初一人だけがk個の石を持っている。各ターンでは石を2つ以上持っているある人が、両隣の人に一つずつ石を渡す。そのような人がいなければゲームは終了する。$k \leq n$ のときゲームはいつか終了し、さもなくば永劫続くことを示せ。

$5 \times 9$ のマスの上にコインが置いてある。各ターンでは、各コインは隣接するマスに移動する。ただし、直前の移動方向と直交する向きに移動しなければならない。また、コインが重なってはいけない。コインが33枚のときは、ゲームは有限回で終了することを示せ。また、32枚のとき、永遠に続くことがあることを示せ。。(1996 Irish Math Olympiad)

$\mathbb Z^2$上で正方形状に$n^2$個のコインが置かれている。$p=(x, y)$ のコインは $(x \pm 1, y), (x, y \pm 1$ に移動できる。ただし、移動するマスを $q$ とすると $(p+q)/2$ にはもともとコインがあって、移動後にそのコインを取り除かなければならない。操作を繰り返すことで、コインが一枚だけの状態にできることを示せ。（1993 IMO）

A はそれぞれ 1, 2, ..,. n 個からなる石の山を好きな順序で並べる。その後、Bから始めて、交互に石を一つずつ取り去る。相手が直前に操作した山の隣の山にしか操作できない。ただし、Bの初手は好きな山を選べる。それ以上操作できなくなったほうが負け。どちらが勝つか。（XIX Olimpíada Matemática Rioplatense (2010)）

$n = 1, 2 \pmod 4$ のとき B, $n = 0, 3 \pmod 4$ のとき A の勝ち。

Z^2上で、$y \leq 0$ となる全ての座標 $(x, y)$ 上にコインが置かれている。各コインは隣接するコイン x の隣の空きマスに移動して、x を取り除く操作ができる。$y \geq 4$ となるマス $(x, y)$ に有限回の操作でコインを移動できないことを示せ。（Conway’s Soldiers）

最後の石を取った方が負けというNIMの勝敗を求めよ。（Misere Nim）

N個のマスが一列に並んでいて、A, B は交互にそれぞれo, xを書き込む。ただし、同じ文字が隣接してはいけない。すべてのマスに文字が書き込まれたら、引き分け。さもなくば、それより前に操作できなくなったら負け。帰結類を求めよ。（IMO 2015 Shortlist, C4）

A, Bは交互に[n]の元を取っていく。全て取り終わったあと、Aの取った元の和が3の倍数だとAの勝ち、さもなくばAの負けである。Aの勝ち負けを求めよ（JMO 2007）

正の整数nが与えられる。A, B は交互にnのある真の約数dを選んでnをn-dで置き換える。それ以上操作できなくなったほうが負け。勝敗を求めよ。（Baltic Way 2013）

$m \times m+1$ のグリッドグラフがある。はじめ、駒は一番下の横棒の頂点のどこかにある。A, Bは交互に駒を動かす。ただし同じ辺を二度通ることはできない。それ以上動かせなくなったほうが負け。どちらが勝つか。（Korea Final Round 2009）

二次元平面の(0,0)に天使がいる。天使と悪魔は交互に次の操作をする。天使は(x, y)から(x+1, y)か(x, y+1)に移動することを1回以上k回以下繰り返す。悪魔は天使が移動できないを座標を一つ追加する。天使がそれ以上移動できなくなるように悪魔はできるか。（JMO 2013）

Aは[N]から整数xを一つ選ぶ。Bは[N]の部分集合Sを選び、$x \in S$であるかどうか何回でも尋ねることができる。AはBの質問に答える際に嘘をついても良いが、k+1回連続で嘘をついてはいけない。Bは好きなだけ質問をしたあとに[N]のn元集合Xを答える。$x \in X$ ならばBの勝ち、さもなくば負け

$n \geq 2^k$ならばBが勝つことを示せ
任意の十分大きいkに対して、$n \geq 1.99^k$ であって、Bが勝てるnが存在することを示せ。

（IMO2012）

$K^2000$がある。Aは辺を一個削除する。Bは2個か3個削除する。これをA, Bは交互に繰り返す。孤立点を作ったほうが負け。どちらが勝つか。(All-Russian MO 1999)

$m \times n$ のマスがあり、A, Bは交互にマスを黒く塗る。中央のマスを黒く塗った方が勝ち。ただし、相手が直前に塗ったマスと頂点を共有するマスしか塗れない。また、初手で中央を塗ることはできない。$4 \mid n-m$のとき後手必勝であることを示せ。

(-1, 0),(0,-1),(-1,-1)の移動が許されているときの勝敗

半分以下の石を取り除くときのニム数は？

$\mathcal{G}(n) = \begin{eqnarray}
\begin{cases}
0 &(n = 0) \\
1 + \lfloor \log_2(n) \rfloor &(\text{otherwise})\\
\end{cases}
\end{eqnarray}$

$\mathcal G(n) = \mathrm{mex}_{i + j < n}\ (\mathcal G(i) \oplus \mathcal G(j))$ のとき、$\mathcal G(i) \oplus \mathcal G(j) \leq \mathcal G(i) + \mathcal G(j)$ なので帰納法より $\mathcal G(n) \leq n $ が成り立つ(ABC278G)。

山を空でない二つの山に分割するゲーム

$\mathcal G(n)=\begin{cases}
0 & (n = 0) \\
0 & (n\text{ が偶数}) \\
1 & (n\text{ が奇数})
\end{cases}$

$1 \leq k < n / 2$ 個の石を取り除くときのニム値は？

$\mathcal G(2^{k+1}x + 2^k) = x$。$x / 2 < y < x$ には $\mathcal G(2^{k+1}y + 2^k) = y$ で遷移可能。$0 \leq y \leq x / 2$ への遷移は、$x, y$ の辞書順比較で場合分けをすると、存在が分かる。$n=2^k$ のとき $\mathcal{P}$ である。

半直線状に並んだマス目上に石が置いてある。石は各マスに高々一つしかない。交互に石を左側に移動させる。ただし、すでにある石を飛び越えるような石の移動は禁止されている。ニム数を求めよ。左端に石を捨てるような操作ができるときはどうなるか。

石を右側から二つずつペアにし、ペアにした石の座標の差を石の個数にするようなニムになる。

各ターンで一つ以上k個以下の山から好きな個数の石を
取り除けるときの勝敗（Moore’s nim）

各山の個数を2進展開して、各桁について和を取ったとき、すべての和がkの倍数か否か。

二つの山がある。どちらか一方の山を取り去り、もう一方の山から石を一個消去した後に二つの山（0個の石の山ができてよい）に分けることを先手と後手は交互に繰り返す。ニム数を求めよ。(delete nim)

$\mathcal G(a, b)=\nu_2( (a \lor b) + 1)$

いくつかの石の山が３つある。各山の石の個数は相異なる。山を選び正整数個の石を取りさることを交互に繰り返す。ただし、同じ数の石の山ができてはならない。石の数が0個の山にこのルールは適用しない。勝敗を求めよ（Antonim）

$(a+1)\oplus(b+1)\oplus(c+1)$がP局面

同じ個数の山から同時に同じ数の石を取り除かなければならないニムがAntonimと等価であることを示せ。

いくつかの石の山がある。各山の石の個数は相異なる。山を選び正整数個の石をりさることを交互に繰り返す。ただし、同じ数の石の山ができてはならない。石の数が0個の山にもこのルールを適用する。ニム数を求めよ（Welter=佐藤のゲーム）

a, bが最初に相異なる桁eを用いて $(a|b)=2^e-1$ と定義する。ただし、$a=b$すなわち$e=\infty$のときは-1とする。$n_1, n_2, \ldots, n_k$ のニム数は $\sum^\oplus n_i \oplus \sum_{i < j}^\oplus (n_i|n_j)$になる。

ニムの代数構造

足し算は$a + b = \mathrm{mex}_{a’ < a\\ b’ < b} (a’ + b, a + b’) = a\ \mathrm{xor}\ b$ により定義する。
これは、$a \neq a’\ \Rightarrow a + b \neq a’ + b$ を満たす最も簡単な数を再帰的に定義している。同様に、$a \neq a’\land b \neq b’ \Rightarrow (a + a’)(b + b’) \neq 0$ となってほしい。分配法則で $ab = ab’+a’b+a’b’$ とすると、$$ab = \mathrm{mex}_{a < a’\\ b < b’}(ab’+a’b+a’b’)$$ が定義になりそうである。実際、このように定めると、体になる。
次の計算により、$0, 1$ が零元と単位元になっている。
\begin{align}
a0 &= \mathrm{mex}(\emptyset) = 0 \\
a1 &= \mathrm{mex}_{a’ < a}(a0+a’1+a’0)\\
&=\mathrm{mex}_{a’ < a}(a’)\\
&=a\\
\end{align}
交換法則 $ab = ba$ は定義から明らか。

$a \neq 0$ かつ $b \neq 0$ のとき $a’=b’=0$ とすると $a’b+b’a+a’b’=0$ なので $ab \neq 0$ である。言い換えると、$ab = 0 \Leftrightarrow a = 0 \lor b = 0$ である。$a’b+ab’+a’b’=ab \Leftrightarrow (a-a’)(b-b’)=0$ だから
$\mathrm{mex}_{a’ < a \\ b’ < b}(a’b+b’a+a’b’)=\mathrm{mex}_{a’ \neq a \\ b’ \neq b}(a’b+b’a+a’b’)$ である。この事実を交換法則と分配法則の証明に使う。
\begin{align}
a(bc) &
= \mathrm{mex}_{a’ \neq a \\ b’ \neq b \\c’ \neq c} (a’bc+a(b’c+bc’)+a'(b’c+bc’)) \\
&=\mathrm{mex}_{a \neq a \\ b’ \neq b \\c’ \neq c} ((a’b+ab’)c+abc’+(a’b+ab’)c’) \\\\
&= a(bc)
\end{align}が得られる。
足し算は$a + b = \mathrm{mex}_{a’ < a\\ b’ < b} (a’ + b, a + b’) = a\ \mathrm{xor}\ b$ により定義する。
これは、$a \neq a’\ \Rightarrow a + b \neq a’ + b$ を満たす最も簡単な数を再帰的に定義している。同様に、$a \neq a’\land b \neq b’ \Rightarrow (a – a’)(b – b’) \neq 0$ となってほしい。分配法則で $ab \neq ab’+a’b+a’b’$ とすると、$$ab = \mathrm{mex}_{a’ < a\\ b’ < b}(ab’+a’b+a’b’)$$ が定義になりそうである。実際、このように定めると、体になる。
次の計算により、$0, 1$ が零元と単位元になっている。
\begin{align}
a0 &= \mathrm{mex}(\emptyset) = 0 \\
a1 &= \mathrm{mex}_{a’ < a}(a0+a’1+a’0)\\
&=\mathrm{mex}_{a’ < a}(a’)\\
&=a\\
\end{align}
交換法則 $ab = ba$ は定義から明らか。

$a \neq 0$ かつ $b \neq 0$ のとき $a’=b’=0$ とすると $a’b+b’a+a’b’=0$ なので $ab \neq 0$ である。言い換えると、$ab = 0 \Leftrightarrow a = 0 \lor b = 0$ である。分配法則は $0$ が含まれるときは明らか。それ以外の場合は、帰納法により、
\begin{align}
(a+b)c &= \mathrm{mex}_{a \neq a’\\ b \neq b’ \\ c \neq c’}((a’+b)c+(a+b)c’+(a’+b)c’, (a+b’)c+(a+b’)c’+(a+b’)c’)\\
&= \mathrm{mex}_{a \neq a’\\ b \neq b’ \\ c \neq c’}((a’c+ac’+a’c’)+bc, ac+(b’c+bc’+b’c’)) \\
&= ac+bc
\end{align}となる。$a’b+ab’+a’b’=ab \Leftrightarrow (a-a’)(b-b’)=0$ だから
$\mathrm{mex}_{a’ < a \\ b’ < b}(a’b+b’a+a’b’)=\mathrm{mex}_{a’ \neq a \\ b’ \neq b}(a’b+b’a+a’b’)$ である。$1$ が含まれるときは交換法則は明らか。それ以外の場合は、帰納法により次の様に示す。
\begin{align}
a(bc) &
= \mathrm{mex}_{a’ \neq a \\ b’ \neq b \\c’ \neq c} (a’bc+a(b’c+bc’)+a'(b’c+bc’)) \\
&=\mathrm{mex}_{a \neq a \\ b’ \neq b \\c’ \neq c} ((a’b+ab’)c+abc’+(a’b+ab’)c’) \\\\
&= a(bc)
\end{align}が得られる。

通常の足し算・掛け算は（齟齬がありそうな場所だけ）$\oplus, \otimes$ で表す。
$n = 2^{2^k}, \mathcal{P}_n = \{0, 1, \ldots, n – 1\}$ と置く。

$\mathcal{P}_n$ は掛け算について閉じている。
$\mathcal{P}_n$ は体をなす。
$n^2 = n+n/2 = 2^{2^k}+2^{2^{k-1}}$
$\mathrm{msb}(a) = \mathrm{msb}(a^2)$
$\{a^2 : a \in \mathcal{P}_n\} = \mathcal{P}_n$
$\{a^2 + a: a \in \mathcal{P}_n\} = \mathcal{P}_{n/2}$
$a < n$ ならば $an = a \otimes n$

$\mathcal{P}_1 = \{0\}$ が掛け算について閉じているのは明らか。$r = 2^{2^{k-1}} = \sqrt{n}$ とする。$\mathcal{P}_r$ が掛け算について閉じていると仮定する。
\begin{align}
(a \otimes r \oplus b)(c \otimes r \oplus d) &= (ar + b)( cn+d ) \\
&= acr^2+(ad+bc)r+bd \\
&= acr^2+(ad+bc)r+bd \\
&=ac(r+r/2)+(ad+bc)r+bd \\
&=acr+ac(r/2)+adr+bcr+bd \\
&=(ac) \otimes r + ac(r/2) + (ad) \otimes r + (bc) \otimes r +bd \\
\end{align}
$5$ つの項全てが $r^2 = n$ 未満なので、$\mathcal{P}_n$ は掛け算について閉じている。掛け算と足し算に閉じているので有限な環をなす。また、零因子が存在しないので逆元が存在して、体になる。
$\mathrm{msb}(a^2) = \mathrm{msb}(a)$ は

$$ (a \otimes r \oplus b)^2 = a^2 \otimes r + a^2(r/2)+b^2 $$

より帰納法から従う。

$a^2 = b^2 \Leftrightarrow (a – b)(a + b) = 0 \Leftrightarrow a = b$ なので、$\{a^2 : a \in \mathcal{P}_n\} = \mathcal{P}_n$ である。$\mathrm{msb}(a^2) = \mathrm{msb}(a)$ より $a^2+a \in \mathcal{P}_{n/2}$ である。 $a^2 + a = b^2 + b \Leftrightarrow (a+b+1)(a-b)=0 \Leftrightarrow a = b, b+1$ であるから、$\{a+a^2:a\in\mathcal{P}_n\} = \mathcal{P}_{n/2}$ である。

$$an = \mathrm{mex}(a’n+an’+a’n’)=\mathrm{mex}(a’n+(a+a’)n’)$$
$a’$ を固定して、$n’$ を動かす。
$\mathcal{P}_n$ が体であったから、$\{(a+a’)n’ : n’ \in \mathcal{P}_n\} = \mathcal{P}_n$ である。従って、mex の中身は $a’ \otimes n \leq i < (a’\oplus 1) \otimes n$ の任意の数を取れる。$a \otimes n$ は取れないので、$an = a \otimes n$。
$$n^2 = \mathrm{mex}_{a < n \\ b < n}(an+nb+ab)$$
$a=b$ のとき、除かれる数は $a^2$ となる。$\{a^2 : a \in \mathcal{P}_n\}=\mathcal{P}_n$ であった。$b=a + 1$ とすると、除かれる数は $an+(a+1)n+a(a+1)=n+a(a+1)$ である。$\{a^2+a : a \in \mathcal{P}_n\} = \mathcal{P}_{n/2}$ であったから、$n+\mathcal{P}_{n/2}$ が除かれる。以上より、$\mathcal{P}_n \cup \{n + \mathcal{P}_{n/2}\} = \mathcal{P}_{n+n/2}$ が除かれる。$n^2+n/2$ が除かれることはないので、$n^2 = n^2 + n / 2$ である。
$a \neq b$ かつ $b \neq a + 1$ のとき、$a+b > 1$ である。このとき、
$$n(a+b) = n \otimes (a + b) \geq 2n$$
だから $n + n/2$ が除かれることはない。

根付き木の順序を、子を根とする部分木の順序の辞書順で定義する（子の順序は区別しない）。いくつかの根付き木が与えられる。木を一つ選び、それより順序の小さい木に置き換えることを交互に繰り返した時の勝敗を求めよ。（Xmas Contest 2019 K: Set of Trees）

整数列 $a \in [m]^n$ が与えられる。各クエリでは $l, u$ が与えられるので、$n$ 個の山の石の個数がそれぞれ $\max(0, \min(u, a_i) – l)$ で与えられる nim のニム数を $O(n\sqrt{m} \log(n))$ で求めよ。（ECR107G）

整数列 $A$ が与えられる。数列の要素を選んで、より小さい非負整数で置き換える操作を行う。ただし、
排他的論理和が 0 になってはいけない。逆形のときの勝敗を求めよ。（ARC131C）

先手は $[2n]$ の要素を $n$ 個のペアに分ける。後手は各ペアから一つずつ要素を選ぶ。後手は選んだ要素の和を $2n$ の倍数にできるか（CFdiv1D）

長さ $n$ の正整数列 $a$ が与えられる。また、長さ無限の 0 からなる列 $b$ が与えられる。先手と後手は交互に $a$ の要素を一つ選ぶ。先手が $a_i$ を選ぶと $b$ の先頭から $a_i$ 個が 1 になり、後手が選ぶと $b$ の先頭から $a_i$ 個が 0 になる。すでに選ばれた要素は選べない。先手は 1 の個数を最大化、後手は最小化したい。最終的な 1 の個数を求めよ。(yukicoder1906)

正整数列 a が与えられる。交互に全ての要素をある正整数で割った余りで置き換える。ただし、これによって、数列が変化しないような操作は禁止されている。$\max(a) \leq 200$ の下、逆形のときの勝敗を求めよ。（ARC134E）

n 個のマスが一列に並んでいて、そのいくつかに駒がおいてある。2つの位置 i, j であって i 番目のマスには駒があり、区間 [j, i) のマスには駒がないようなものを選び、区間 [j, i] の各マスの駒の有無を反転させる操作ができる。ニム数を求めよ。（
yuki1613）

駒の有無を2進数の0/1に対応付けると、$$\mathcal{G}(n)=\mathrm{mex}\mathcal{G}(n-2^i)$$ である。3の倍数のペアが作れるので、周期3になる。

n 個の石の山が一列に並んでいる。ある山から石をいくつか選んで左隣の山に移動できる。ニム数を求めよ。（stair nim）

奇数番目の山の石の移動は打ち消し可能なので、偶数番目の山の個数の総和がニム数になる。

正整数 k が与えられる。石の個数が n のとき、高々 $\lfloor n / k \rfloor$ 個の石を取れる。ニム数を求めよ。（ARC191F）

n が k の倍数のとき $\mathcal{G}(n) = n / k$ さもなくば $\mathcal{G}(n) = \mathcal{G}(n – \lfloor n / k \rfloor – 1)$ である。n – n / k = (1-1/k)n なので、O(klog(n)) . $\lfloor n / k$ が同じ部分をまとめて処理すると O(n / k). よって$O(\sqrt{n \log(n)})$

根付き木が与えられる。辺を削除して、根が含まれない連結成分を削除する操作ができる。ニム数を求めよ。

根に複数の子が接続している場合は、各辺ごとに新たに根を作って、それらのニム数のXORを取ればよい。子が一つだけの場合は、その子を根とする部分木のニム数に1足した値が元の木のニム数になる。

赤と青の辺からなる根付きパスが与えられる。Aさんは赤い辺を、Bさんは青い辺を削除して、根が含まれない連結成分を削除する操作ができる。ニム数を求めよ。（ハッケンブッシュ）

赤の辺を1, 青の辺を1とする。例えば、根の辺から順に左から右に書くと
$$111001110$$
のようになったとする。すると、ゲームの値は
$$2+.0011101$$
となる（小数部分は2進表記）。先頭の (1 の個数) – 1 が整数部分、小数部分はそれより後ろの部分の最後に 1 を付け足した値になる。同じ値だが、
\begin{align}
1+1+1-\frac{1}{2}-\frac{1}{4}+\frac{1}{8}+\frac{1}{16}+\frac{1}{32}-\frac{1}{64}
\end{align}という表示もある。帰納法より、一番後ろの辺を削除するのが最善手で、
$$\{2+.00111\ |\ 2+.001111\} = 2+.0011101$$
から従う。

赤と青の辺からなる根付き木が与えられる。Aさんは赤い辺を、Bさんは青い辺を削除して、根が含まれない連結成分を削除する操作ができる。ニム数を求めよ。（ハッケンブッシュ）

根の子の数が2個以上ある場合はそれぞれに対して新たに根を作った場合の数の和を取ればよい。従って根の子が一つだけの場合のみ考えればよい。根と子を繋ぐ辺が青で、子の部分木のゲームが根付きパスの
$$111001110$$
と同一視できるとする（この値を $x$ と置く）。すると先頭に 0 を付け足すと
$$0111001110$$となる（この値を $x’$ と置く）。
\begin{align}
x’ &= -1 + (x – k) / 2^k + (1 / 2 + 1 / 4 + \cdots + 1 / 2^k) \\
&= (x – k – 1) / 2^k
\end{align}である。$x’ < 0$ となる最小の $k$ を選べばよい。

マスが一列に並んでいて、そのいくつかのマスに赤と青の駒が置いてある。ただし、駒は一つのマスに高々一つしかない。Aさんは青い駒、Bさん赤い駒を左のマスに移動できる。その際、それより左側にある駒も一緒に移動する。ゲームの値を求めよ。（shove）

左から $i$ 番目の駒の位置を $p_i$、その駒の色を $c_i$ (青なら 1 赤なら -1)、その駒より右側にある駒（右端2個が同色なら削除を可能回数繰り返した後）の数を $r_i$ と置く。$\sum c_i \frac{p_i}{2^{r_i}}$ がゲームの値になる。例えば、一番左側の青駒（ i 番目の駒）を左に一つ移動した場合、ゲームの値が $$\frac{1}{2^{r_1}}+\frac{1}{2^{r_2}}+\cdots+\frac{1}{2^{r_{i-1}}}-\frac{1}{2^{r_i}} = -\frac{1}{2^{r_i}}$$だけ変化する。Aさんはこの手が最適である。Bさんも同様に一番左の赤駒を一つ左に移動するのが最適で $\frac{1}{2^{r_1}}$ だけ変化する。従って、$x = \{x + \frac{1}{2^{r_1}}| x – \frac{1}{2^{r_1}}\}$ であることを示せばよい。$x$ の分母が高々 $2^{r_1}$ なのでよい。

先手と後手はそれぞれ $[n]$ の多重集合$\{1^{A_1}, 2^{A_2}, \ldots, N^{A_N}\}, \{1^{B_1}, 2^{B_2}, \ldots, N^{B_N}\}$が与えられる。手番のプレイヤーは自分の多重集合から元を一つ削除する。次の手番のプレイヤーは同じ元を自分の多重集合から削除するか、何もしないか選択できる。同じ元を自分の多重集合から削除した場合、手番が移る。先に空集合になった方が勝ち(ARC151F)。

少し考えると、$A_i \leftarrow \min(A_i+1, B_i+1, A_i), B_i \leftarrow \min(A_i+1, B_i+1, B_i)$ としても勝敗は変わらないことが分かる。$S_A = \{i^A_i : A_i < B_i\}, S_B = \{i^B_i : A_i > B_i\}, S_{=} = \{i^A_i : A_i = B_i\}$ と置く。

$S_{=} = 0$ ならば $S_A > S_B\iff$ 先手勝ち。自分の方が多い元から優先して削除すればよい。

以下 $S_{=}>0$ とする。

$S_A\geq S_B + S_{=}-1$ ならば先手勝ち。先手は $S_B, S_{=}, S_A$ の順の優先度で要素を選ぶ。後手には $S_A \geq S_B + S_{=}$ で手番が移る。後手が $S_A$ を選んだ時だけ応手する。後手が $S_A$ を選んだときに後手の集合が空になることはない。
$S_A+S_{=} \leq S_B$ ならば後手勝ち。後手は先手が $S_B$ を選んだ時だけ応手する。

以下 $S_B-S_{=} < S_A < S_B+S_{=}-1$ とする。

$S_{B} = 0, S_A > 0$、（両者とも非空の組の）山が三つ以上のとき先手勝ち。先手は $S_{=}$ を選ぶ。
$S_{A} = 0, S_B > 0$、（両者とも非空の組の）山が三つ以上のとき後手勝ち。基本的に後手は応手するが、$S_{B}=0$ のときは、偶奇によって応手するかどうかを決める。
$S_{A}=S_{B}=0$ のとき $S_=$ の種類数を $n$ と置く。$n=1$ならば $S_{=} =1 \pmod 2 \iff $ 先手勝ち。$n > 1$ ならば $S_{=} =n+1 \pmod 2 \iff $ 先手勝ち。$n \neq 1$ のとき $S_{=}$ の要素数1の要素を選ぶと負けになるので要素数1を避けながら互いに即応手を繰り返す。また、この結果から、$n > 1$ のとき、サイズ１の山を $S_=$ に加えても勝敗は不変である。

実験コード