在 MIT BBS 上看到一个有趣的题目
一个 M*N 的方阵，每个格子里放一个硬币。甲乙轮流取：选定一枚硬币后，必须取走它上方、右方和右上方的所有硬币（如果有的话）。拿走最左下角那个输。问谁有必胜策略？
有人立即给出了答案：
假设后手有必胜策略。
先手取(M,N)，如果后手的必胜策略是取(i, j)，那么先手开局不取(M,N)而取(i,j)，则先手必胜。矛盾。
所以先手必胜。
这样的解法被称为存在性证明。上面问题可以在两个方面加以扩展：
1、求构造性策略。
即需要给出先手的必胜操作具体是怎么样的。比如当 N=M 时，可以先取(2, 2)处的格子（假设左下方格子坐标为(1, 1)），然后与后手对称地取格子。
2、如果是任意的游戏状态，其各方的必胜策略又是如何？
一个游戏状态可以表示为$ a_1, a_2, \cdots, a_n$ ，其中$ a_1\geq a_2\geq\cdots\geq a_n$ ，分别表示第一列到最后一列各列剩余的方格数量。当$ n=2$ 时，$ \{(a_1, a_2)|a_1=a_2+1\}$ 为后手的必胜状态集。对于较大的$ n$ 后手的状态集不太好求。
Q. E. D.
