硬币游戏的答案

作者: , 共 1758 字
系列:数学之美

查看该系列所有文章

前两天贴出了一个硬币游戏,希望寻找一种胜利策略。这是一个非常有意思的题目,没事做的时候可以用来锻炼思考能力。我迫不及待的想在这里公布解答,因为我已经把它解决掉了。如果有人还想继续享受思考的乐趣,请飘至原问题


1. \( n=4\) 的简单情形,

Tony Liu 和 overwindows 已经给出了正确答案:

  • 第一步:任一对角线翻转
  • 第二步:任一条边翻转
  • 第三步:任一对角线翻转
  • 第四步:任一个硬币翻转
  • 第五步:任一对角线翻转
  • 第六步:任一条边翻转
  • 第七步:任一对角线翻转  

这个策略分成两部分,前三步和后三部。前三步处理棋盘上有偶数颗正面朝上的硬币的情况。第四步把奇数颗正面朝上的情况转化成偶数颗正面朝上的硬币,然后重复使用前三步的策略即可。

2. 接推广到\( n=2^k\) 的情形

在给出策略前,先定义硬币状态为 0 如果正面朝上,为 1 若正面朝下。若干个状态的 XOR 和指状态的和除以 2 的余数。两个硬币对称是指两个硬币处于正多边形棋盘的直径上(此时\( n\) 为偶数)。

假设\( S(k)\)\( n=2^k\) 时的策略。我们来递归构造策略\( S(k)\)

(i). 如果棋盘上任何对称的硬币方向都相同,则将对角的硬币看成一个整体(同时操作)之后,\( 2^k\) 枚硬币转化成\( k-1\) 的情形,调用 \( S(k-1)\) 即可让所有硬币方向相同。此策略记为\( C_1\)

(ii). 如果棋盘上任何对称的硬币方向都相同或者同时都相反,类似(i),先调用\( C_1\) ,若硬币方向都相同,则已经解决了问题。若否,注意到调用\( C_1\) 的过程只会同时改变对称的两个硬币的朝向,这样调用\( C_1\) 之后还是满足任何对称的硬币方向都相反,这时候,翻转连续的\( 2^{k-1}\) 个硬币,从而可以转化成(i)的情况。所以,策略\( C_2=(C_1, F(2^{k-1}), C_1)\) 可以解决任何对称的硬币方向相同或者相反的情况。其中\( F(2^{k-1})\) 表示翻转连续的\( 2^{k-1}\) 个硬币。

(iii). 接下来主要是把问题转化为(ii)中的情况。这时候只需要对某连续\( 2^{k-1}\) 枚硬币调用\( S(k-1)\) 即可。这是因为如果我们把对称的硬币看成一个整体的话,则这次\( S(k-1)\) 的每次操作都只作用于任何对称的硬币的其中一枚上。这样,如果我们考虑对称硬币状态的 XOR 和的话,\( S(k-1)\) 的过程中会出现所有对称的硬币方向都相同或者都相反的情形,也就是(ii)中的情况。由于我们不知道这个状态在什么时候出现,所以在这个\( S(k-1)\) 的每一步后,都需要执行一次\( C_2\) 操作。另外要注意的是,\( C_2\) 的操作不会影响外围的\( S(k-1)\) 操作。

注:此策略的最优性未知。

3. \( n\) 不是 2 的幂次时 Alice 没有必胜策略

考虑 Alice 的最后一步,如果 Alice 总是能够在最后一步或之前使所有硬币方向一样,假设她的最后一步是必要的(存在一种情况在最后一步才达到方向一致),假设 Alice 最后一步翻转的硬币是集合\( T\) ,翻转后使得所有硬币都朝上或者朝下。由于 Bob 可以将棋盘任何旋转若干个位置,这说明对任何的旋转角度\( i=1,2,\cdots,n\) ,均有\( T+i=T\ or\ \bar{T}\) ,其中集合\( T+i=\{t+i\mod n:t\in T\}\) 。这只可能在\( n\) 为偶数并且\( T\) 为所有奇数位置或者所有偶数位置才可能达得到。

而若\( n=2^\alpha\beta\) 并且\( \beta\) 为大于 1 的奇数。这时候我们将所有硬币分为连续的\( \beta\) 组,每组由连续的\( 2^\alpha\) 枚硬币构成。每组的状态(0 或者 1)是组内所有硬币状态的 XOR 和。如果 Alice 存在一个获胜的策略,那么在分组后的游戏中, Alice 也应该总是能获得胜利。但如上一段所指出的,在奇数组的游戏中, Alice 不可能获胜。从而导致了一个矛盾。

Q. E. D.

系列: 数学之美 »
"Good mathematics" could refer (in no particular order) to
写篇三门问题的终结版。欢迎补充材料。
类似文章:
相似度: 0.388
Alice 和 Bob 两人玩一种硬币游戏。游戏在一个\( 2\times2\) 的棋盘上进行,棋盘上每个格子上都有一枚硬币。在每一回合, Alice 可以决定选择翻转某两枚或者一枚硬币,接着 Bob 可以选择将棋盘旋转 90 , 180 或者 270 度,也可以什么都不做。
在 MIT BBS 上看到一个有趣的题目
相似度: 0.187
\( n\) 枚硬币排成一排,两人轮流取,每人每次可取其中一枚或者相邻的两枚。
题目来源:《A practical Guide to quantitative finance interviews》,解答和书上的可能不一样。
利用线性代数可以给某些问题很精妙的证明,Matrix67 就给出了一个这样的例子,这也让我想起以前看见的另外一个例子,分享如下:
相似度: 0.106
最近看到一个有趣的问题:
本文将证明:最佳约会策略里提到策略,忽略前 37%的对象,然后在剩下的对象里挑第一个比前 37%都好的对象,这个策略是最优的。更准确地,我们将证明:任何约会策略的成功概率都不可能超过\( \frac{u}{n}\sum_{i=u}^{n-1}\frac1i\) ,其中\( u\) 为满足\( \sum_{i=u}^{n-1}\frac1i\geq 1\) 的最大值。这个\( u\) 大约为 37%,最后成功的概率大约为 40%。
相似度: 0.090
这个题目听说是 MSRA 的面试题。
我很早之前就想过这个问题,但一直只知道一个 trivial 的答案。前两天无意中发现网上已经有高手给出了更好的方案,故记录在此。有兴趣的可以自己想一想。
在这个游戏的开头,我们设想自己要参加一个电视游戏大奖赛。规则呢,是这样。我们有 n 个人,作为一个小组来参加游戏。游戏中,主持人会给我们每人头上戴一顶帽子。帽子有黑白两种颜色,可以认为它们在我们各自头上的分布是临时随机决定的。小组中的每一个人,可以看到其他人的帽子颜色,但不知道自己的帽子颜色。每个游戏成员都被要求回答自己帽子的颜色。我们各人面前有三个按钮,可以选择「黑色」「白色」或「弃权」(也就是 pass ,不作猜测的意思)。小组成员彼此之间没有任何信息交流,他们必须各自独立地作出自己的选择,并且谁也不知道其他人的选择。如果小组成员全部选择了 pass ,也就是每个人都弃权,则他们输了;如果有小组成员作出了明确的猜测,但某个人猜错了,则结果也是输。只有当小组中有人做出猜测,并且每个做出猜测的人都猜对了,他们才能获胜,一起获得最后的大奖。
前一篇:
Alice 和 Bob 两人玩一种硬币游戏。游戏在一个\( 2\times2\) 的棋盘上进行,棋盘上每个格子上都有一枚硬币。在每一回合, Alice 可以决定选择翻转某两枚或者一枚硬币,接着 Bob 可以选择将棋盘旋转 90 , 180 或者 270 度,也可以什么都不做。
毫无疑问,所有的点火仪式中巴塞罗那的点火仪式最令人难忘。与其说是它的创意,还不如说他的刺激,征服了我们。从 70 米的远处射火箭把圣火射入火盆,想起来就觉得刺激啊:要是没射中会怎样呢?