来源：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$ 堆。那么负态的条件是，所有堆数各个二进制位的和模 $k$ 都为 $0$。
证明：假如当前异或和为 $0$，不论先手如何操作，都会恰改变一个 $\text{sg}$，因此异或和变为非 $0$。
假如当前异或和不为 $0$。考虑异或和的最高位，一定有某个 $\text{sg}$ 该位为 $1$，该 $\text{sg}$ 异或上异或和后一定变小，从而先手可以进行这样的操作，并转换成负态。
定义使得所有 $\text{sg}$ 变为 $0$ 的人负（即使原游戏还可以进行操作）。证明胜态为：
证明：