用SG定理解释Nim游戏

1.Sprague–Grundy 定理

定理叙述

设$x,y$ 是两个有限无偏组合游戏的状态， $x+y$ 表示它们的和游戏，即每一步只能在$x$ 或$y$ 中选择一个进行一次合法操作，而另一个保持不变。

那么

其中$\oplus$ 表示按位异或 XOR

$SG$函数指一次操作之后不能到达的状态的 $SG$函数的最小值

更一般地，对于有限个相互独立的游戏状态$x_1,x_2,\ldots,x_n$，

下面证明两个游戏的情形。多个游戏的结论可以通过反复应用两个游戏的结论得到。

定理证明

对于组合状态$x+y$，一次合法操作只有两种可能：

1. 在$x$ 中进行一步操作$x\to u$，得到$u+y$；

2. 在$y$ 中进行一步操作$y\to v$，得到$x+v$。

因此，$x+y$的所有后继状态组成集合

根据 SG 函数的定义，

下面证明这个 mex 恰好等于$SG(x)\oplus SG(y)$。

使用数学归纳法

我们对组合状态距离终局的最大剩余步数进行归纳。

如果$x+y$ 已经是终局状态，那么$x,y$ 都没有合法后继状态，因此

于是

所以定理对终局状态成立。

现在假设定理对于所有比$x+y$ 更接近终局的组合状态都已经成立。

如果$x\to u$，那么$u+y$ 是$x+y$ 的后继状态，因此根据归纳假设，

同理，如果$y\to v$，则

所以

记

并定义两个集合

于是

因此只需要证明

根据 mex 的定义，只需要证明两件事：

1.$X\oplus Y\notin A\cup B$；

2. 对任意$0\leq W<X\oplus Y$，都有$W\in A\cup B$。

第一部分：证明$X\oplus Y\notin A\cup B$

首先证明

任取一个$x$ 的后继状态$u$，记

因为

根据 mex 的定义， $x$本身不可能出现在$x$ 的后继状态的 SG 值中。

因此

假设

两边同时异或$Y$，得到

这与$U\neq X$ 矛盾。

所以

由于这对于所有$x\to u$ 都成立，因此

完全类似地，对于任意$y\to v$，都有

所以

因此

综上，

第二部分：证明对于所有$W<X\oplus Y$，都有$W\in A\cup B$

首先给出一个关于异或的引理。

引理

设$a_1,a_2,\ldots,a_n$ 为非负整数，并且

那么至少存在一个$a_i$，使得

证明：

设$k$ 是$Z$ 的最高非零位，即

因为

所以在第$k$ 位上，

因此至少存在一个$a_i$，满足

由于$k$ 是$Z$ 的最高非零位，所以异或$Z$ 不会改变$a_i$ 中高于第$k$ 位的任何一位，而会把第$k$ 位从$1$ 变为$0$。

因此

引理得证。

现在任取

定义

由于

所以

从而

根据上面的引理，$Z$ 异或$X,Y,W$ 中至少一个时，会使这个数减小。

也就是说，下面三个不等式中至少有一个成立：

但是

而根据假设，

所以

因此第三种情况不可能发生。

所以前两种情况至少有一种成立，即

或

由于$X$ 与$Y$ 在整个证明中的地位完全对称，所以不妨设

展开得到

因此

又因为

根据 mex 的定义，所有小于$X$ 的非负整数都一定出现在$x$ 的后继状态的 SG 值中。

由于

所以必然存在一个后继状态$x\to u$，使得

于是

根据归纳假设，

所以

因此

Sprague–Grundy 定理得证。

推广到多个游戏

对于三个游戏，由刚刚证明的结论，

不断重复这个过程，可以得到对于任意有限个相互独立的无偏组合游戏，

为什么最终会出现 XOR

整个证明中最关键的地方是：

令

我们证明了

同时对于所有

都有

因此按照 mex 的定义，

也就是说，XOR 并不是人为规定的组合方式，而是它恰好满足 SG 函数所要求的 mex 结构：

因此两个独立游戏组合以后，其 SG 值自然满足

回到nim游戏

观察到剩余的石子数目与SG函数完全同构

故证毕。