减法游戏
减法游戏示例
示例： 晶字12画，两个人一同写，每人每次最多谢2画，最少写1画，谁写最后一画谁赢，那么是先写的赢还是后写的赢？
这个游戏是一个典型的** impartial game**（无偏博弈），类似于“减法游戏”或“尼姆游戏”的变种。我们来严格分析一下。
减法游戏是组合博弈论（Combinatorial Game Theory, CGT）中最经典的无偏博弈（impartial game）之一。
游戏规则总结：
- 总笔画：12 画
- 每回合玩家必须写 1 或 2 画（不可写 0 画，也不可写超过 2 画）
- 谁写下最后一画，谁获胜
关键：赢位与后写分析（倒推法）
我们从终点往回看，标记每个剩余笔画数是“先写必胜“还是“后写必胜”： 这里是用倒推法完整分析剩余1到12画的所有位置（胜/负判断）：
| 剩余笔画 | 先写选择的笔画数 | 留给后写的可能选择 | 先写的胜负判断 | 说明 |
|---|---|---|---|---|
| 1 | 写1→剩0 | 0 | 胜 | 直接写最后一画 |
| 2 | 写2→剩0 | 0 | 胜 | 直接写最后两画 |
| 3 | 写1→剩2 写2→剩1 | 写2→剩0 写1→剩0 | 输 | 无论怎么写都留给后写最后一画 |
| 4 | 写1→剩3 写2→剩2 | 写1→剩2 写2→剩1 写2→剩0 | 胜 | 可以写1留下3（转到3,先写变后写） |
| 5 | 写1→剩4 写2→剩3 | 可参考4、3 | 胜 | 可以写2留下3（转到1、2,后写变先写） |
| 6 | 写1→剩5 写2→剩4 | 可参考5、4 | 输 | 无论怎么写都留给后写最后一画（转到5、4,后写变先写） |
| 7 | 写1→剩6 写2→剩5 | 可参考6、5 | 胜 | 可以写1留下6（转到6,先写变后写） |
| 8 | 写1→剩7 写2→剩6 | 可参考7、6 | 胜 | 可以写2留下6（转到6,先写变后写） |
| 9 | 写1→剩8 写2→剩7 | 可参考8、7 | 输 | 无论怎么写都留给后写最后一画 （转到8、7,后写变先写） |
| 10 | 写1→剩9 写2→剩8 | 可参考9、8 | 胜 | 可以写1留下9（转到9,先写变后写） |
| 11 | 写1→剩10 写2→剩9 | 可参考10、9 | 胜 | 可以写2留下9（转到9,先写变后写） |
| 12 | 写1→剩11 写2→剩10 | 可参考11、10 | 输 | 无论怎么写都留给后写最后一画 （转到11、10,后写变先写） |
规律（一目了然）：
| 剩余笔画除以3得到的余数 | 谁会赢 |
|---|---|
| 0 | 后写赢 |
| 1 | 先写赢 |
| 2 | 先写赢 |
12 ÷ 3 = 4 余 0 → 后写
所以：先写必输，后写必胜（后写的赢）。
规律出现了：每 3 画一个周期
- 当剩余笔画数是 3 的倍数时 → 后写（0, 3, 6, 9, 12…）
- 其他时候 → 先写
12 ÷ 3 = 4，正好是 3 的倍数 → 后写
也就是说：面对 12 画的字，后写赢（也就是“后写的赢”）。后写有必胜策略：后写永远回应使得双方写完一轮后总共减少 3 画（例如先写写 1，你写 2；先写写 2，你写 1），这样一直保持剩余是 3 的倍数，直到最后留下 3 画给后写，后写无论怎么写你都能拿走最后 1 或 2 画获胜。
总结
- 参与玩家数为两个，总笔画数 N
- 每回合玩家必须写 最小 a 画 ，最多 b 画（ b > a）
- 后写玩家就以控制每轮笔画数的和等于 (a + b)
- 如果 N ÷ (a + b) ，没有余数，那么后写一定赢；如果有余数，先写只要在第一轮写余数画，此时后写就面对就是没有余数的场景，后写就会输。
- 没有余数时的必胜策略：后写永远使得双方写完一轮后总共减少 (a + b) 画
练习
一堆棋子共28粒，甲乙双方每轮最少拿1粒，最多拿4粒，谁拿最后1粒谁就赢。请问谁会赢？
解答：后拿玩家以控制每轮拿的棋子数等于 (1 + 4) = 5粒。 28 ÷ 5 = 5···3，余数是3。先拿的玩家只要第一次拿3粒，就一定能赢。