硬币游戏的答案

作者:, 发表于

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


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.


上一篇:硬币游戏2008年7月27日
Alice和Bob两人玩一种硬币游戏。游戏在一个$$2\times2$$的棋盘上进行,棋盘上每个格子上都有一枚硬币。在每一回合,Alice可以决定选择翻转某两枚或者一

下一篇:绿皮书里的智力面试题2009年3月25日
题目来源:《A practical Guide to quantitative finance interviews》,解答和书上的可能不一样。


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