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

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

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

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

这时候Alice还能取胜吗？

下面是问题解答，但强烈推荐独立思考此题，特别是的情况。

问题解答：

的简单情形，

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

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

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

这个策略可以直接推广到的情形：

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

假设为时的策略。我们来递归构造策略：

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

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

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

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

不是2的幂次时Alice没有必胜策略

考虑Alice的最后一步，如果Alice总是能够在最后一步或之前使所有硬币方向一样，假设她的最后一步是必要的（存在一种情况在最后一步才达到方向一致），假设Alice最后一步翻转的硬币是集合，翻转后使得所有硬币都朝上或者朝下。由于Bob可以将棋盘任何旋转若干个位置，这说明对任何的旋转角度，均有，其中集合。这只可能在为偶数并且为所有奇数位置或者所有偶数位置才可能达得到。

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

来自：http://zhiqiang.org/blog/posts/rotate-coin-game-solution.html

分类： 程序员数学 算法艺术