===== 例题 =====

**来源**：Part I, 1.5.3–Ferguson

**题目大意**：有一堆 $31$ 颗的石子，每次可以取 $1\sim6$ 颗，但是每种数量至多取 $4$ 次。问胜负情况。

**题解**：不妨先不考虑 $4$ 个的限制。这个比较简单，模 $7$ 余 $0$ 的状态是负态。然而如果先手按这种策略操作，只要后手一直取 $4$，先手最后一轮将无 $3$ 可用。

事实上，先手先取 $5$ 仍可保证取胜。如果后手一直也取 $5$ ，先手取 $2$ 来应对。取了 $4$ 个 $5$ 和 $3$ 个 $2$ 后，还剩 $5$ 个，此时已经不能再取 $5$ 了，因此后手不论怎么取都会输。如果后手某一回合不取 $5$ 了，先手可以立即转移到模 $7$ 余 $0$ 的状态，可以验证这时不论如何先手不会没东西可用，因为开始的若干操作拖延了一回合。

===== 例题 =====

**来源**：Part I, 1.5.5–Ferguson

**题目大意**：有两堆石子，每次操作可以将某堆石子清空，然后把剩下的一堆石子分成两个非空的堆。问胜负情况。

**题解**：如果两堆石子都是奇数，那么先手负，否则先手胜。如果至少有一堆石子是偶数，那么我们可以把这堆石子拆成两个奇数堆，从而转移到负态。而如果两堆石子都是奇数个，显然拆出来至少有一个偶数。

===== 例题 =====

**来源**：Part I, 1.5.6–Ferguson

**题目大意**：给你一个矩形网格，每次选取一个格子，将该格子右上方的部分删除，删掉左下角格子的玩家输。证明除 $1\times1$ 外，先手必胜。

**题解**：假如删掉右上角的格子后是负态，那么命题已经成立。否则后手一定可以进行某种操作转移到一个负态，而容易发现这个操作先手同样可以完成。

===== 例题 =====

**来源**：Part I, 1.5.7.a–Ferguson

**题目大意**：有一堆 $n$ 颗的石子，先手可以任意取，但是不能取完，之后每个人至多只能取上一次取的数量。问胜负情况。

**题解**：我们首先归纳地证明，对于每个 $k\ge0$，如果当前石子数能被 $2^{k+1}$ 整除，且至少能拿 $2^{k}$ 个石子，那么当前这个人不会取 $\le2^{k}$ 个石子。

$k=0$ 时显然，如果先手只拿 $1$ 个，那么之后所有人都只能拿 $1$ 个石子，显然先手就输了。

假设 $\le k$ 时成立。$k+1$ 时，假如先手取了 $x<2^{k+1}$ 颗石子，那么后手直接取 $\text{lowbit}(x)$ 颗石子，我们已经证明了先手不能取 $\le\text{lowbit}(x)$ 颗石子，而先手又没有其它选择，因此这样必败。假如先手取 $2^{k+1}$ 颗石子，后手也同样取 $2^{k+1}$ 颗石子，这样到最后先手还是会输。

这样一来结论就简单了。假如石子个数是 $2$ 的幂，那么先手必败，因为后手可以取 $\text{lowbit}$。否则先手取 $\text{lowbit}$ 即可。

===== 例题 =====

**来源**：Part I, 1.5.7.b–Ferguson

**题目大意**：和上一题大体相同，但是至多可以取上一次取的数量的两倍。

**题解**：首先介绍斐波那契进制，即将一个正整数表示为若干不相邻的斐波那契数之和，可以证明这样的表示是存在且唯一的。

设当前数的斐波那契进制表示为 $a_{1}+\cdots+a_{n},a_{1}>\cdots>a_{n}$。

假如 $n\ge2$，那么先手可以删掉 $a_{n}$，由于 $a_{n-1}>2a_{n}$，因此后手不能一次取完。我们来证明后手不论怎么取，仍然会回到刚刚的情况。假设后手取完后，$a_{n-1}$ 变为了 $b_{1}+\cdots+b_{m}=a_{n-1}-x$，我们想要证明 $2x\ge b_{m}$。采用反证法，假设 $2x<b_{m}$，这样 $x$ 的斐波那契进制表示必然和 $b_{m-1}$ 不相邻，从而 $a_{n-1}=b_{1}+\cdots+b_{m-1}+x$，这样就与 $a_{n-1}$ 的斐波那契进制表示唯一矛盾了。

假如 $n=1$，和刚刚相同可证得先手必败。

===== 例题 =====

**来源**：Part I, 1.5.8–Ferguson, 2017 ECL-Final L

**题目大意**：一个 $1\times n$ 的格子，每次往一个空格子中填入 ''%%S%%'' 或 ''%%O%%''，先填出 ''%%SOS%%'' 的胜。问胜负情况。

**题解**：我们称一个格子是好的，当且仅当其中填入 ''%%S%%'' 和 ''%%O%%'' 都将导致后手胜利。容易证明，这样的格子只会在 ''%%S**S%%'' 中出现。因此好格子是成对出现的，即最后只剩下好格子时，一定是偶数个。假如 $n$ 是偶数，那么先手负，否则后手负。另外还需要证明对方一定能摆出好格子。

若 $n$ 为偶数，且 $n\ge16$。假如先手摆 ''%%S%%''，后手可直接摆出。否则先手摆 ''%%O%%''，那么一定有一边有至少 $8$ 个格子，后手在该侧离边界 $3$ 个格子的地方摆 ''%%S%%''，即 ''%%SXXX%%'' 或 ''%%XXXS%%''（''%%X%%'' 表示空格子）。如果先手在远离边界的一侧摆，那么后手也可以直接填出。如果先手在边界一侧摆，后手就可以在另一侧摆出 ''%%S**S%%''，由于第一回合先手摆了 ''%%O%%''，因此这样填不会陷入非法状态（注意如果先手先填 ''%%S%%'' 则不能保证）。

若 $n$ 为奇数，且 $n\ge7$。先手在中间摆 ''%%S%%''，不论后手什么操作，先手在另一侧填即可。

暴搜可以证明其它时候都是平局。$n=14$ 的一个证明可以参见 Ferguson 的习题答案。

（ang 怎么出原题的啊

===== Nim-k 博弈 =====

把 Nim 游戏的规则修改一下，每次可以取至多 $k$ 堆。那么负态的条件是，所有堆数各个二进制位的和模 $k$ 都为 $0$。

===== SG 定理 =====

**证明**：假如当前异或和为 $0$，不论先手如何操作，都会恰改变一个 $\text{sg}$，因此异或和变为非 $0$。

假如当前异或和不为 $0$。考虑异或和的最高位，一定有某个 $\text{sg}$ 该位为 $1$，该 $\text{sg}$ 异或上异或和后一定变小，从而先手可以进行这样的操作，并转换成负态。

===== SJ 定理 =====

定义使得所有 $\text{sg}$ 变为 $0$ 的人负（即使原游戏还可以进行操作）。证明胜态为：

  * 若异或和为 $0$，所有 $\text{sg}\le1$
  * 若异或和不为 $0$，至少有一个 $\text{sg}>1$

**证明**：

  * 对于胜态：
    * 若所有 $\text{sg}$ 为 $0$，已经成立。
    * 否则若异或和为 $0$，又至少有一个 $1$，把 $1$ 变成 $0$ 即可。
    * 若异或和不为 $0$，若有至少两个 $\text{sg}>1$，那么按照 $\text{SG}$ 定理行动即可。这样之后，至少还有一个 $\text{sg}>1$，因此是负态。若只有一个 $\text{sg}>1$，那么按照奇偶性决定将它变成 $1$ 还是变成 $0$。
  * 对于负态：
    * 若异或和为 $0$，则至少有**两个**（不可能是一个）$\text{sg}>1$。不论怎么操作，异或和会变为非 $0$，而 $\text{sg}>1$ 的至少还有一个，因此是胜态。
    * 若异或和不为 $0$，则所有 $\text{sg}\le1$。把 $0$ 变成 $1$ 或 $1$ 变成 $0$ 均为胜态。而如果把某个 $\text{sg}$ 变成 $>1$，由于只有一个 $>1$，异或和不为 $0$，因此还是胜态。