取格子游戏的构造性策略

作者:, 发表于

在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.


上一篇:何时适可而止?2010年11月21日
最近看到一个有趣的问题: 我们可以连续抛一枚均匀的硬币,并且随时可停下,在停下后可获得的回报为(正面出现次数/抛硬币的次数)。如果希望

下一篇:如何匿名统计平均收入2012年1月14日
网络的力量太大,这两次把问题放到网上不到半天,这些问题不但被解答,而且连出处都被翻出来了。这让我自己少了很多思考的乐趣。以后不能把问


  • 支持使用微薄、微信和QQ的账户登陆进行评论。由各自网站直接认证,不会泄露你的密码。
  • 登陆后可选择分享评论到所绑定的社交网络,如微薄、人人和QQ空间。
  • 评论提交后无法修改。如需修改,请删除原评论再重新提交。
  • 评论支持LaTeX代码,行内公式请用\(a+b=c\),行间公式请用\[a+b=c\]。公式只支持英文字符。