硬币游戏的答案

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

1. n=4n=4 的简单情形，

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

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

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

2. 接推广到n=2kn=2k 的情形

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

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

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

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

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

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

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

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

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

Q. E. D.