Number Duel 数学
Nim 游戏与 Sprague-Grundy 定理
想象一个简单的游戏：桌上有几堆石头，两个人轮流拿。每次从一堆里拿任意个（至少拿1个），拿走最后一个的赢。
这就是 Nim。它是数学中最重要的游戏之一——不是因为人们为了娱乐玩它（虽然确实有人玩），而是因为理解 Nim 就掌握了解开整个策略游戏家族的钥匙。
基本游戏
从一个具体例子开始。三堆石头：3、4、5 个。
堆A: ●●●
堆B: ●●●●
堆C: ●●●●●
你先手。应该怎么拿？直觉帮不了你——答案需要二进制运算。
二进制的技巧
Charles Bouton 在1901年证明了 Nim 有完全解。关键是nim和（nim-sum）：所有堆的大小的异或（XOR），用二进制计算。
对于我们的例子（3、4、5的堆）：
3 = 0 1 1
4 = 1 0 0
5 = 1 0 1
XOR ---------
0 1 0 = 2
Bouton 定理：
- nim和 = 0：当前局面是必败态（轮到谁谁就输，假设对手也完美）
- nim和 ≠ 0：当前局面是必胜态（轮到的人有必胜走法）
nim和是2（非零），所以先手必胜。必胜策略：找一步让 nim和变成0。
试试堆C（5个）。我们需要从5中拿走一些，使3、4、剩余的堆C异或为0：
011 ⊕ 100 ⊕ 011 = 000 ✓
所以从堆C拿2个（5→3），之后无论对手怎么拿，你总能找到一步恢复 nim和=0。
为什么是异或？
答案很美：异或有自反性——a ⊕ a = 0。这意味着 nim和=0 时所有堆在二进制下是"配对平衡"的。对手打破一对，你恢复一对。对手总是逃不掉——你总有应对。
Nim 的变体
Bash 博弈（巴什博弈）
一堆N个石头，每次最多拿K个。如果N是(K+1)的倍数，后手赢；否则先手赢。策略：先手拿 N mod (K+1) 个，之后对手拿x个你就拿 (K+1-x) 个。
Wythoff 博弈
两堆石头，你可以从一堆拿任意个，或从两堆拿相同数量。这个游戏的必败态和黄金比例有关：
(1, 2), (3, 5), (4, 7), (6, 10), (8, 13)...
每对是 ⌊nφ⌋ 和 ⌊nφ²⌋，其中 φ = (1+√5)/2 是黄金比例。这就是Beatty 序列，黄金比是最"无理"的无理数，使得序列不重叠不遗漏。
Sprague-Grundy 定理
1935年，Sprague 和 Grundy 独立证明了一个惊人的结论：
每一个公平的两人博弈都等价于某个 Nim 堆。
"公平"指双方可选的走法相同。"等价"指数学结构完全一样。
给每个局面分配一个 Grundy 数：
- 没有后继局面 → Grundy 数 = 0
- 其他局面 → Grundy 数 = mex{所有后继的 Grundy 数}（mex = 最小的不在集合里的非负整数）
由多个独立子博弈组成的游戏，总 Grundy 数 = 各子博弈 Grundy 数的异或。这就是 Nim 的一般化。
和 Number Duel 的联系
Number Duel 的游戏不是纯公平博弈，但同样的思维方式适用：
- 在 Sum Duel 中，每一步都改变可选的格子和对手的选项。和 Nim 一样，你要把对手推向"必败态"。
- 在 Fifteen Duel 中，游戏等价于井字棋，已被完全求解。
Sprague-Grundy 定理是这种分析的理论基础。不管游戏看起来多复杂，底层总有一个 Nim 式的结构等你发现。