Sprague–Grundy theorem proof

首先要有个重要引理。

引理：

任意有限公平博弈的值一定是某个的值。

证明：

考虑归纳法，设某个公平博弈能转移到的值都已经是某个的值，即。设表示中最小的未出现的自然数，由于是有限博弈，则可以令。下证明。

简单的想法就是作差后考虑策略，即

$\begin{align*} &G=\ast_n\iff G-\ast_n=0\iff G+\ast_n=0\\ &\iff \lbrace \ast_{n_1},\ast_{n_2},\cdots| \ast_{n_1},\ast_{n_2},\cdots\rbrace+\lbrace \ast_0,\ast_1,\cdots,\ast_{n-1} | \ast_0,\ast_1,\cdots,\ast_{n-1}\rbrace=0 &\end{align*}$

若先手选取一个，则后手在另一个博弈中选择对应的即可，此时等价于。

若先手选取一个，则后手在中选择，此时等价于。

综上，，于是归纳也成立。

有了这个引理后，我们能容易地将所有有限公平博弈的值转到上，于是我们只要证明：

Sprague–Grundy theorem:

对任意的两个，它们的和满足，其中为二进制下的异或操作。

证明：

从定义入手，考虑展开后的形式，即

$\begin{align*} &\ast_n+\ast_m\\ &=\lbrace \ast_0,\ast_1,\cdots,\ast_{n-1} | \ast_0,\ast_1,\cdots,\ast_{n-1}\rbrace + \lbrace \ast_0,\ast_1,\cdots,\ast_{m-1} | \ast_0,\ast_1,\cdots,\ast_{m-1}\rbrace\\ &=\lbrace \ast_{0}+\ast_m,\ast_1+\ast_m,\cdots,\ast_{n-1}+\ast_m,\ast_0+\ast_n,\ast_1+\ast_n,\cdots,\ast_{m-1}+\ast_n | \cdots\rbrace \end{align*}$

根据前面的引理，我们知道。注意到在中，的下标都是严格小于的，从这一点上来看，我们可以数学归纳法。不妨假设的都满足，于是。于是我们只要证明值中最小的没出现的自然数即可。这个证明是简单的，我们分两步。