问题描述
有一个m*n方格的巧克力，最左上角一个方格有毒，两个人轮流在这个巧克力上选一个方格吃，当一个方格被选了以后，它的右边和下边的所有方格全被吃掉。每个人每轮必须吃，吃到有毒的一方为输。怎么选择你的策略？
背景知识
策梅洛定理（Zermelo's theorem）:二人参与的游戏中，如果满足以下条件，那么先行一方有必胜策略或者后行一方有必胜策略。
- 游戏步骤有限；
- 信息完备（参与者知晓游戏规则）
- 不会产生平局
- 确定性（不存在运气成分或者放水行为）
简单情景
-
棋盘只有一行，但多于一格
先手只需吃掉左上角以外位置的巧克力即可。对于只有一列的棋盘，采取同样的方法。
-
棋盘是正方形，但多于一格
先手只需吃掉位置(2, 2)的巧克力，随后模仿后手的吃法，在另一行或列对称地进行相同的操作。
-
棋盘只有两行
先拿走右下角的一块，随后不管后手选择拿走哪块，都保证上行比下行多一块
Three rowed
用有向图的方法标识可行方案。用点Pi表示棋盘所有的可达状态，并用P和N分别标识所有先者胜或后者胜的状态；用有向边，如(P1, P2)，表示存在从状态P1到状态P2的一步可行走法（吃法）。那么，标记有向图中出度为0的点为P，标记至少存在一条边到P点的所有点为N，然后，标记那些所有边到达的都是N状态的点为P，重复操作。
论文[1]陈述了两个结论，并予以证明：
-
对任意a≥1，棋盘位置
是一个P position； -
当a, b满足a≥b≥0, 且a-b≠1，棋盘位置
是一个N position. 并且，当a=b时，下一步应走(a, a-1)；当a≥b-2时，下一步应走(b+1, b).
证明（联合归纳）：结论1显然是正确的。由结论2，从状态(a, a-1)经一步能到达的状态都是N position，如(a-1, a-1), (a-1, a-2), (a-1, a-3), ..., (a, 0)，因此P2(b)隐含P1(a)。并且，a=b或a-b=2，P2(b)隐含在P1(b-1)或P1(b)中。所以有，P1(b-1)和P1(b)隐含P2(b), P2(b-1), ..., p2(1)，能推出P1(b)。又P1(1)是一个P position，得证。
对不确定的棋盘大小M*N，不存在一个多项式时间算法。特别地，当M=2时，对于(a, a-1)这样的棋盘，能确定P和N状态，并且能找到先者胜的方案。下面讨论M=3的情况，设P(a, b, c)。
分析：根据最开始的依据，出度为0的点是P点、能一步达P点的是N点和只能从N点一步到达的状态是P点，可以从两行的棋盘总结出如下规律。
| N position | P position |
|---|---|
| (b+1, b, 1) | (b+1, b, 0) |
| (1, 1, 1) | (1, 0, 0) |
| (a, 0, 0) | (1, 0, 0) |
| a-b≥2时，(a, a, 0) (a, b, 0) |
特别地，当格子数一共有4格或5格时，情况如下：
| N position | P position |
|---|---|
| (5, 0, 0) (4, 1, 0) | (2, 2, 1) (3, 1, 1) |
| (4, 0, 0) (3, 1, 0) (2, 2, 0) (2, 1, 1) |
由前面的结论，我们知道，
-
c=1时的P状态只有(2, 2, 1)和(3, 1, 1)
满足c=1，且格子数至少为6的N状态是以下情况之一：(3, 2, 1), (3, 3, 1), (4+p, 1, 1), (2+p, 2+q, 1)，p≥q≥0.
因为上述四种状态能一步达到P状态，如下：
(3, 2, 1) —> (3, 1, 1); (3, 3, 1) —> (3, 1, 1); (4+p, 1, 1) —> (3, 1, 1);
(2+p, 2+q, 1) —> (2, 2, 1)
-
c=2时，(a, b, 2)为P状态，当且仅当a-b=2
参考资料
【1】Doron Zeilberger, Three-Rowed CHOMP, Department of Mathematics, Temple University, Philadelphia, Pennsylvania 19122, Advances in Applied Mathematics 26, 168–179 (2001)
网友评论