grundy数とNim - kamojirobrothersのブログ

典型90の031で困ったので。

031 - VS AtCoder（★6）
https://atcoder.jp/contests/typical90/tasks/typical90_ae

納得できなかったので、簡単に証明をあてたり補足したり。

grundy数

いろいろと端折ってDAGから初めます。
詳細は、以下などを参照ください。
Grundy数（Nim数, Nimber）の理論

$V = \{0, 1, \ldots, n-1\}$ を頂点集合とし、 $E$ を辺集合とします。
ここで、 $E$ の元は頂点 $i$ から $j$ への辺を、 $(i, j)$ で表すものとします。
また、 $grundy[i]$ で頂点 $i$ の grundy 数を表すことにします。
また、 ${\rm mex}$ により、集合に含まれない最小の非負整数を表すものとします。

grundy 数が $0$ で後手必勝、 $0$ より大きい値で先手必勝とします。

grundy数の性質

1. $grundy[i] = 0$ は後手必勝
2. $grundy[i] = x = {\rm mex}(\{j | (i,j) \in E\})$
3. $grundy[i] = x$ である場合、任意の $p (0 \geq p < x)$ に対して、 $grundy[j] = x$ なる頂点 $j$ への辺が存在する（遷移できる）

考察1

$grundy[i] = 0$ のとき、 $(i, j) \in E$ なる任意の $j$ に対して、 $grundy[j] >0$ が成立する。

性質2を書き下した。

考察2

$grundy[i] = x$ のとき、 $(i, j) \in E$ なる任意の $j$ に対して、 $grundy[j] \neq x$ が成立する。
さらに、各 $p (0 \geq p < x)$ に対して、 $(i, j_p) \in E$ なる $j_p$ を選んで、 $grundy[j_p] = p$ となるようにできる。

性質 2 と 3 を書き下した。

Nim

Nim の後手必勝の条件は、 $x_0 \ xor\ \cdots \ xor \ x_{n-1} = 0$ であることです。
（以下、この条件を ${\rm Xor} \ x_i = 0$ のように表します。）
ここで、 $x_i$ は、grundy 数です。
これを証明します。

方針

競技プログラミングでよく出てくるゲームでは相手にある状態（負けの状態）を押し付け続けることが必勝法になります。

証明

相手に、 ${\rm Xor} \ x_i = 0$ を押し付け続けることができれば勝利できます。
特に、すべての $i$ に対して、 $x_i = 0$ であれば、 ${\rm Xor} \ x_i = 0$ であるため、この状態であれば負けています。

あとは、自分の手番において ${\rm Xor} \ x_i \neq 0$ であれば、相手に押し付け続けることができることを示せば十分です。
これは、grundy数の性質の 3. から grundy数をそれより小さい、任意の数字にできることから分かります。
また、 $xor$ の性質から、 ${\rm Xor} \ x_i = 0$ に操作を行ったとき、必ず ${\rm Xor} \ x_i \neq 0$ となります。

補足

$grundy[i] = x$ でも、ある $y > x$ と頂点 $j$ が存在して、 $(i, j) \in E$ と、 $grundy[j] = y$ となることがあります。
これは、 $grundy[i] = {\rm mex}(\{0, 1, 3,4\}) = 2$ などの場合に発生します。

なぜこれを考える必要がないのか?がこの補足です。
簡単に言うと、利点がないため必勝法において利用されることがないためです。

grundy数の性質 3. から、grundy数が大きくなるほど（元の選択肢を包含する形で）選択肢が増えます。

例えば、grundy数が 2 のときは、grundy数が 0、1 になる頂点に移動できます。
grundy数が 4 のときは、grundy数が 0、1、2、3 になる頂点に移動できます。
これは、grundy数が 2 の場合の移動先をすべて含んでいます。

相手の選択肢を増やす操作に利点がありません。
特に、grundy数はmexで十分意味を持つことも分かります。