8
取格子游戏的构造性策略
source link: https://zhiqiang.org/math/a-square-game.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
取格子游戏的构造性策略
系列：头脑风暴
在 MIT BBS 上看到一个有趣的题目
一个 M*N 的方阵，每个格子里放一个硬币。甲乙轮流取：选定一枚硬币后，必须取走它上方、右方和右上方的所有硬币（如果有的话）。拿走最左下角那个输。问谁有必胜策略？
有人立即给出了答案：
假设后手有必胜策略。
先手取(M,N)，如果后手的必胜策略是取(i, j)，那么先手开局不取(M,N)而取(i,j)，则先手必胜。矛盾。
所以先手必胜。
这样的解法被称为存在性证明。上面问题可以在两个方面加以扩展：
1、求构造性策略。
即需要给出先手的必胜操作具体是怎么样的。比如当 N=M 时，可以先取(2, 2)处的格子（假设左下方格子坐标为(1, 1)），然后与后手对称地取格子。
2、如果是任意的游戏状态，其各方的必胜策略又是如何？
一个游戏状态可以表示为a1,a2,⋯,ana1,a2,⋯,an ，其中a1≥a2≥⋯≥ana1≥a2≥⋯≥an ，分别表示第一列到最后一列各列剩余的方格数量。当n=2n=2 时，{(a1,a2)|a1=a2+1}{(a1,a2)|a1=a2+1} 为后手的必胜状态集。对于较大的nn 后手的状态集不太好求。
Q. E. D.
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK