关于Sprague-Grundy定理的核心疑问：Grundy值的不变性本质与MEX同态性的归纳证明

架构老林

2026-4-22

Sprague-Grundy定理的核心疑问：Grundy值的不变性本质与MEX同态性的归纳证明

我完全懂你现在的困惑——当初我啃Sprague-Grundy定理的时候，也对着“为啥不用0/1分胜负”和“MEX凭啥是同态”这两个问题卡了好久，咱们一步步把这层窗户纸捅破。

一、Grundy值的不变性：不止是胜负，更是游戏的“等价类”

你说的“把必胜态映射到1，必败态映射到0”，其实只抓住了单个游戏的胜负结果，但组合游戏的核心是多个独立子游戏的叠加——比如你同时玩两个Nim堆、或者两局规则相同的 impartial 游戏。这时候0/1的映射就完全不够用了：

举个最简单的例子：两个Nim堆各有1个石子，每个单独都是必胜态（1），但叠加起来却是必败态（因为不管你拿哪堆，对手拿另一堆就赢了）。如果用0/1映射，1+1没法得到0，但用Grundy值的话，每个堆的Grundy数是1，异或后是0，正好对应必败态。

Grundy值真正保留的不变性是：两个游戏G和H等价，当且仅当对于任意游戏K，G+K和H+K的胜负结果完全相同。这里的“等价”是比单纯胜负更强的关系——它保证了不管和什么游戏叠加，两者的表现都一致。而0/1映射只能区分“单独玩的时候是赢还是输”，没法处理叠加后的复杂情况。

这也是Sprague-Grundy能压缩计算的关键：如果一个大游戏能拆成若干独立子游戏，整个游戏的Grundy数就是子游戏Grundy数的异或，不用遍历整个大状态空间；如果子游戏有重复的结构（比如多个相同的Nim堆），直接复用Grundy数就行。

首先明确一下：这里的“同态”指的是游戏叠加的Grundy数等于各子游戏Grundy数的异或，也就是对于任意两个游戏G和H，g(G+H) = g(G) XOR g(H)，其中G+H表示玩家可以在任意一个子游戏中进行操作的组合游戏。

我们用数学归纳法来证明这个结论，归纳的依据是游戏状态的“深度”（即从当前状态到终端状态的最长路径长度）：

终端状态（没有任何可操作的后继状态）的Grundy数是0。两个终端状态叠加后还是终端状态，g(G+H)=0=0 XOR 0，显然成立。

假设对于所有深度小于当前状态的游戏，同态性都成立——也就是说，对于任意两个状态G'、H'，如果它们的所有后继状态都满足g(G'+H')=g(G') XOR g(H')，那么这个等式对G'和H'本身也成立。

设当前状态G的Grundy数为a = g(G)，H的Grundy数为b = g(H)，我们需要证明g(G+H) = a XOR b。

根据Grundy数的定义，g(G+H)等于其所有后继状态的Grundy数的MEX（最小的非负整数不在这个集合里）。所以我们需要证明两点：

G+H的后继状态只有两种：要么是G的某个后继G'加上H，要么是G加上H的某个后继H'。

对于G的后继G'，根据Grundy数的定义，g(G') ≠ a（因为a是G的后继Grundy数的MEX，所以a不在G的后继Grundy数集合里）。根据归纳假设，g(G'+H) = g(G') XOR b。如果g(G') XOR b = a XOR b，那么会推出g(G')=a，矛盾。
同理，对于H的后继H'，g(H') ≠ b，所以g(G+H')=a XOR g(H') ≠ a XOR b。

因此，a XOR b不可能出现在G+H的后继状态的Grundy数集合中。

设c = a XOR b，对于任意整数k < c，我们需要找到G+H的一个后继状态，其Grundy数等于k。

令d = k XOR a，分两种情况讨论：

如果d < b：因为b = g(H)是H的后继Grundy数的MEX，所以H必然存在一个后继H'，使得g(H')=d。根据归纳假设，g(G+H') = a XOR d = a XOR (k XOR a) = k，正好是我们要找的数。
如果d >= b：令e = k XOR b，此时e < a（推导：因为k < a XOR b，所以k XOR b < a）。同理，G必然存在一个后继G'，使得g(G')=e，那么g(G'+H) = e XOR b = (k XOR b) XOR b = k，也符合要求。

这就说明所有小于c的数都在后继集合里，结合前面的结论，G+H的Grundy数的MEX就是c = a XOR b，也就是g(G+H)=g(G) XOR g(H)。

这样就完成了归纳证明，说明MEX定义的Grundy数确实满足同态性。

备注：内容来源于stack exchange，提问作者xade93