Nim 游戏

一般来说，Nim 游戏的规则如下：

有 堆石子（排成一行），第 堆有 个，两名玩家轮流取走任意一堆的任意（正整数）个石子。

无法行动的玩家失败（经典规则下，即拿走最后一枚石子的玩家获胜）。

显然对于一堆石子的情形，其 SG 函数值为 ；由 SG 定理，整局游戏的 SG 函数值为 。

SG 函数值非零时先手必胜（N 态），SG 函数值为零时后手必胜（先手必败，P 态）。

变种 1：每次只能从最左侧或最右侧取

TODO

变种 2：每次只能从最多的一堆中取，并列时任选

设初始状态为 ，不妨令序列不降。

• 若 ，则 为后继状态之一。
  • 若 为 P 态，则 已经为 N 态；
  • 若 为 N 态，则其后继状态存在 P 态，又注意到 的后继均为 的后继，因此 为 N 态。
• 假设石子最多的堆共有 堆，由上述结论，显然 为 的倍数时为 P 态，否则为 N 态。

变种 3：每次只能从最少的一堆中取，并列时任选

1. 时先手必胜（N 态）。
2. 若不存在 ，则当且仅当 时为 P 态，否则为 N 态。
3. 若 且存在 ，设有且仅有 堆满足 ，则当且仅当 时为 N 态，否则为 P 态。

Proof

前两种情况显然，这里只讨论情况 3。

首先，显然 的情形与 的情形等价；否则与 的情形等价。

其次，以 为例，先手只能将 的情形交给对手，而对手可以将 的情形交还，直到 ，此时轮到对手，故 为 P 态。

变种 4：先手可以任选一堆，今后不能选择与上一堆相同的

与 Nim 游戏无本质区别，留给读者自证。

变种 5：先手可以任选一堆，今后必须选择与上一堆相邻的

TODO

变种 6：先手可以任选一堆，今后必须选择与上一堆相同的，除非已经取尽

若 ，则当且仅当 时为 N 态；若 ，则为 N 态。留给读者自证。

变种 7：每次取完后，可以立刻从另一堆中取走同样多的石子

TODO

变种 8：每次取石子的数量上限为 3

考虑每堆石子的 SG 函数值，显然为 。

因此整局游戏的 SG 函数值为 。

变种 9：无法行动的玩家胜利

即 Anti-Nim 游戏，其他反常游戏的做法类似。

存在结论：

1. 若 ，则局面为 N 态当且仅当共有偶数堆石子；
2. 若 ，则局面为 N 态当且仅当 。

Proof

• 局面 A 显然。
• 对于局面 B，分 3 种情况讨论：
  • （B0）只存在一个 ，此时显然先手必胜（N 态），且 。
  • （B1）至少 2 个 ，且 。
  • （B2）至少 2 个 ，且 。
  • 对于局面 B1，由 Nim 游戏结论，显然一定可以转移到 B2。
  • 对于局面 B2，显然或者转移到 B0，或者转移到 B1，且有时只能转移到 B0。
  • 综合以上两条结论，不难得出原命题成立。

变种 10：游戏中有且只有一次跳过的机会

TODO

变种 11：每次玩家取完后，若存在其他取法，对手可以要求更换方法，每轮限一次

TODO