硬币游戏

作者:, 发表于

Alice和Bob两人玩一种硬币游戏。游戏在一个 \(2\times2\) 的棋盘上进行,棋盘上每个格子上都有一枚硬币。在每一回合,Alice可以决定选择翻转某两枚或者一枚硬币,接着Bob可以选择将棋盘旋转90,180或者270度,也可以什么都不做。

游戏轮流进行直到棋盘上所有硬币都正面朝上或者反面朝上,Alice获得胜利。

如果Alice在游戏过程中无法看到棋盘上的银币,也不知道游戏刚开始的状态,甚至不知道Bob每回合是否旋转了棋盘,那么Alice有策略能够获得胜利么?他的最优策略是什么?

接下来我们推广这个游戏。共有 \(n\) 枚硬币,分别放在一个正 \(n\) 边形棋盘的顶点上。每回合Alice可以翻转任何一些银币,Bob则可任意以 \(n\) 种不同的方式(旋转 \(360/n\) 的倍数角度)之一旋转棋盘。游戏一直到所有硬币正面朝上或者反面朝上,Alice获得胜利。

这时候Alice还能取胜吗?

解答在此,但强烈推荐独立思考此题,特别是 \(n=4\) 的情况。

via Sariel’s blog

Q.E.D.


上一篇:Windows游戏中的NP完全问题2008年6月13日
上篇文章扫雷是NP完全问题之后,You Xu提到"不光扫雷是NP 完全问题,空当接龙问题也极有可能是一个NP完全问题。目前最好的通用 planner只能解半副牌

下一篇:硬币游戏的答案2008年7月30日
前两天贴出了一个硬币游戏,希望寻找一种胜利策略。这是一个非常有意思的题目,没事做的时候可以用来锻炼思考能力。我迫不及待的想在这里公布


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