硬币游戏

作者: , 共 503 字 , 共阅读 0

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.

类似文章:
相似度: 0.401
前两天贴出了一个硬币游戏,希望寻找一种胜利策略。这是一个非常有意思的题目,没事做的时候可以用来锻炼思考能力。我迫不及待的想在这里公布解答,因为我已经把它解决掉了。如果有人还想继续享受思考的乐趣,请飘至原问题
相似度: 0.366
$ n$ 枚硬币排成一排,两人轮流取,每人每次可取其中一枚或者相邻的两枚。
在 MIT BBS 上看到一个有趣的题目
题目来源:《A practical Guide to quantitative finance interviews》,解答和书上的可能不一样。
我很早之前就想过这个问题,但一直只知道一个 trivial 的答案。前两天无意中发现网上已经有高手给出了更好的方案,故记录在此。有兴趣的可以自己想一想。
英文是 communication complexity ,不知道该翻译成通信复杂性,还是通讯复杂性呢。这里先用通讯复杂性吧。这是一个理论计算机的子领域,在过去 30 年衍生了很多东西。它是我的研究的主要内容,这里简略介绍一下。
一个游戏:持续的抛一个均匀硬币,直到抛到出现反面为止,假设在之前你抛除了$ k$ 次正面,你将得到$ 2^{k+1}$ 次方这么多钱。
相似度: 0.093
最近看到一个有趣的问题:
数学 » 数学游戏, 概率
蚁迹寻踪及其他数学探索》提到一个游戏:
数学 » 赌博
何时适合而止中,我们提到一个有趣的硬币问题,抛一个硬币,选择合适的时点,使得正面数与总次数的比值最大。这个问题目前还没有被完全解决,之前我们也只是用模拟法逼近了一下结果
环保攻防战 告発せよ 摘発せよ ~環境破壊との闘い~ 于 2008 年 7 月 13 日播出 49mins
前两天贴出了一个硬币游戏,希望寻找一种胜利策略。这是一个非常有意思的题目,没事做的时候可以用来锻炼思考能力。我迫不及待的想在这里公布解答,因为我已经把它解决掉了。如果有人还想继续享受思考的乐趣,请飘至原问题