Chomp类游戏——必胜策略分析

首先介绍一个重要定理——策梅洛定理(Zermelo)

策梅洛定理,表明在二人参与的游戏/博弈中，如果满足：
--------游戏的步骤数有限
--------信息完备(二人都了解游戏规则，了解游戏曾经所发生过的信息)
--------不会产生平局
--------确定性(游戏中不会加入随机因素)
则先行一方有必胜策略，或者后行一方有必胜策略。

问题：有一个n*m的棋盘，每次可以取走一个方格并拿掉它右边和上边的所有方格。拿到左下角的格子(1,1)者输，那么谁会赢呢？

先给结论：除了(1, 1)先手必败外，其他都是先手必胜。

证明如下：

根据策梅洛定理，这个问题至少有一方存在必胜策略。

如果后手必胜，也就是说无论先手取哪个石子，后手都能获得必胜策略。那么假设先手取得最右上角得石子，接下来后手通过某种方法让自己进入必胜局面。但事实上，先手在第一次取得时候就可以和后手这次取得一样，抢先进入必胜局面，与假设矛盾。

例1：

有n张卡片，第i张纸片上写着数字i，每次可以取走一张纸片和数字是该纸片因数的纸片，那么谁会赢呢？

solve：除了n=1的情况，先手必赢。

例2：

现在有一颗含n个节点的有根树，根节点是1，每个点初始时都为白色。每次可以把任意一个白色节点到根节点经过的所有的点(包括该节点)变成黑色。谁最后把整棵树染黑了，谁就输了。

solve: 除了n=1的情况，先手必赢。