尼姆游戏

题目

尼姆（Nim）游戏：桌上有若干堆石子，比如三堆分别是 3、4、5 颗。两人轮流行动，每次从某一堆里取走至少 1 颗、至多整堆，取走最后一颗石子的人获胜。

面对任意初始局面，怎么判断先手必胜还是必败？又该怎么走？

答案与解析

关键在于把所有堆的数量做按位异或（XOR，记作 ⊕），得到“尼姆和”：

$N = a_1 \oplus a_2 \oplus \cdots \oplus a_k$

• 若 $N = 0$：这是必败局（P 局），轮到谁谁输（假设对手不犯错）；
• 若 $N \ne 0$：这是必胜局（N 局），先手总能一步把它变成 $N=0$ 留给对方。

以上面的 3、4、5 为例，写成二进制：

3 = 011
4 = 100
5 = 101
--------
XOR= 010 = 2   (非零 → 先手必胜)

先手要找一堆，把它改成“与当前尼姆和 XOR 后更小的值”。比如选 5（101），目标值应为 $5\oplus 2 = 7$？不对，应使新值 $x$ 满足 $x \oplus (\text{其余堆的异或}) = 0$，即 $x = \text{其余堆的异或} = 3\oplus4 = 7$？但 7>5 不能减。改选 4（100）：$4\oplus2=6>4$ 也不行。选 3（011）：$3\oplus2 = 1$，把 3 那堆取到剩 1 颗（取走 2 颗），新局势 1、4、5 的异或 = $1\oplus4\oplus5 = 0$，成功甩出必败局。

背后的数学

尼姆游戏是组合博弈论的基石，由查尔斯·博顿在 1901 年给出完整解。它的美妙在于把“胜负”完全编码进一个整数运算。

更进一步，Sprague–Grundy 定理表明：一大类“公平双人无随机、无平局”的博弈，都能被拆解成若干独立的尼姆堆，每堆对应一个“Grundy 数”（尼姆值）。尼姆和是这类博弈的通用判据——这也是为什么计算机能秒算无数棋类残局的胜负。