取格子游戏的构造性策略
在MIT BBS上看到一个有趣的题目
一个M*N的方阵，每个格子里放一个硬币。甲乙轮流取：选定一枚硬币后，必须取走它上方、右方和右上方的所有硬币（如果有的话）。拿走最左下角那个输。问谁有必胜策略？
有人立即给出了答案：
假设后手有必胜策略。
先手取(M,N)，如果后手的必胜策略是取(i, j)，那么先手开局不取(M,N)而取(i,j)，则先手必胜。矛盾。
所以先手必胜。
这样的解法被称为存在性证明。上面问题可以在两个方面加以扩展：
1、求构造性策略。
即需要给出先手的必胜操作具体是怎么样的。比如当N=M时，可以先取(2, 2)处的格子（假设左下方格子坐标为(1, 1)），然后与后手对称地取格子。
2、如果是任意的游戏状态，其各方的必胜策略又是如何？
一个游戏状态可以表示为
，其中
，分别表示第一列到最后一列各列剩余的方格数量。当
时，
为后手的必胜状态集。对于较大的
后手的状态集不太好求。
Q.E.D., ©zhiqiang, 2011.02.27。请参考右边的相关文章列表。
有點暈
先手开局不取(M,N)而取(i,j),后手再取(M,N)，不也是后手必胜吗？怎么先手胜了呢？
先手取(i, j)后，(M, N)就不能取了，因为(i, j)右上方的格子都要被取走。这里(M, N)指最右上角的方格。
“假设后手有必胜策略。
先手取(M,N)，如果后手的必胜策略是取(i, j)，那么先手开局不取(M,N)而取(i,j)，则先手必胜。矛盾。
所以先手必胜。
”
可是，如果除了先手必胜、后手必胜之外，还有一种可能是无论先手、后手，都没有必胜策略呢？
用归纳法容易证明下述定理
对于文章里的游戏，由于每人每步至少取一个格子，故游戏必定在M×N步结束。另外，显然该游戏最后总是分出了胜负，故该游戏必定有一方有必胜策略。
假如是一个一行的方阵，也就是只有一行的方格。则当方格是奇数时，后手必胜
不妨在m<n情况下，如果假设左下角是 （1，1）我们可以得到一个构造性策略：谁先碰(1,1) (2,2) (3,3)。。。(m,m)这些点谁输。策略就是碰了这些点后，后手只需要使矩阵沿向量 （2，2）对称即可获胜
由此往下推我出现问题了~
我当先手，我拿左起第二个，你怎么办
假设后手有必胜策略。
先手取(M,N)，如果后手的必胜策略是取(i, j)，那么先手开局不取(M,N)而取(i,j)，则先手必胜。矛盾。
所以先手必胜。
证明有问题，先手取(M,N)，如果后手的必胜策略是取(i, j)，这是存在了一个条件“先手先取了(M,N)”后手才有策略(i, j)，而如果直接取(i, j)，不见得是必胜策略
比如2*3情况下
先手取（2，2），后手有必胜策略，取（1，3）；但若先手取（1，3），后手的必胜策略为（2，2）
好像有问题
我也有此疑问。。
先手取(M,N)后，后手的必胜策略是取(i,j)。这个策略的前提是(M,N)被取走。如果(M,N)没被取走，取(i,j)显然不一定是必胜策略。
我写成下面这样应该清楚些：原游戏记为A；考虑一个规则一样的游戏B，与A的唯一区别是右上角(M, N)处的棋子已经被取走。
首先，游戏B肯定有必胜方，先手或者后手。
如果游戏B中先手必胜，假设先手的必胜策略的第一步是取走(i, j)，那么在游戏A中的先手同样可取走(i, j)，从第二布开始游戏A和游戏B变成一样的，这样在游戏A中也是先手必胜。
如果游戏B中后手是必胜的，那么游戏A中的先手第一步取走(M,N)，此时游戏A变成游戏B，不过游戏A中的先手变成游戏B中的后手，从而必胜。
如果游戏B中先手必胜，假设先手的必胜策略的第一步是取走(i, j)，那么在游戏A中的先手同样可取走(i, j)，从第二布开始游戏A和游戏B变成一样的，这样在游戏A中也是先手必胜。
“从第二布开始游戏A和游戏B变成一样的”这个不一定成立的！
你的前提是取(m,n)+(i,j)两步之后剩下的残局等于取(i,j)一步之后剩下的残局，这可不一定。就像zhaosoul说的。
或者考察3*3的矩阵。
原来是
***
***
***
(m,n)是(2,2)，当(2,2)及(2,2)的右上角都被取走后，先手必胜的策略是取(3,1)，即(i,j)是(3,1)。
即如果矩阵是
*
*
***
那么先手必胜策略是取(3,1)。剩下
*
*
**
就是说，如果某个选手面对的是上面那个矩阵，他必输。
那如果直接取(3,1)呢，残局就是
**
**
**
面对这个残局的选手可就不一定输了。
你的推论成立的条件是，i<=m且j<=n。
兄弟，M×N是棋盘的大小，(M, N)是右上角那个格子，你说的i<=m且j<=n是必然成立的