A journalist, named Zoe, unfortunately (for her) interviews one of the presidential candidates. The candidate refuses to let Zoe to end the interview, and goes on and on about the candidate’s plans how to solve all the problems in the world. In the end, the candidate offers Zoe a game. If she wins the game she can leave.
The game board is made out of 2×2 coins:
At each round, Zoe can decide to flip one or two coins, by specifying which coins she is flipping (for example, flip the left bottom coin and the right top coin), next the candidate goes and rotates the board by either 90,180,270, or 0 degrees. (Of course, rotation by 0 degrees is just keeping the coins in their current configuration.)
The game is over when all the four coins are either all heads or all tails. To make things interesting, Zoe does not see the board, and does not know the starting configuration.
Describe an algorithm that Zoe can deploy, so that she always win. How many rounds are required by your algorithm?
From: Sariel's blog
中文翻译：
Alice和Bob两人玩一种硬币游戏。游戏在一个2×2的棋盘上进行，棋盘上每个格子上都有一枚硬币。在每一回合，Alice可以决定选择翻转某两枚或者一枚硬币，接着Bob可以选择将棋盘旋转90，180或者270度，也可以什么都不做。
游戏轮流进行直到棋盘上所有硬币都正面朝上或者反面朝上，Alice获得胜利。
如果Alice在游戏过程中无法看到棋盘上的银币，也不知道游戏刚开始的状态，甚至不知道Bob每回合是否旋转了棋盘，那么Alice有策略能够获得胜利么？他的最优策略是什么？
解法：
这个题目其实挺简单的，关键是考虑问题的思路，思路正确的话，最多七步可以解决问题。注意不考虑初始状态所有四枚硬币都朝上或朝下的情形。
初始状态不外乎下面四种：
（1） （2） （3） （4）
然而，（1）和（4）是上下对称状态，实际属于一种状态。这样就只有（1）、（2）、（3）三种初始状态了。
我们的目标是，经过数次翻转硬币的操作，使得所有的状态都能达到全上或者全下的情形，对于中途达到目的的情况就可以弃之不考虑了，说明我们运气好，提前完成了任务。
第一步：任一对角线翻转（这里的翻转指的是上面的每个硬币都翻个个，下同）
这一步做完后，便出现如下情形：
状态（1）不变，因为它要么变成对称，要么旋转角度。
状态（2）也不变，只是旋转了一下角度而已。
状态（3）直接变成全上或全下了，OK，属于提前完成任务，丢弃。
第二步：任一条边翻转
长话短说，状态（1）依然不变，因为除了变角度就是变成对称。
状态（2）分两种情况。一种是直接胜利，丢弃。另一种是变成状态（3）。
第三步：任一对角线翻转
状态（1）仍然不变，状态（3）直接走向胜利。
第四步：任一个硬币翻转
这一步的目的是让状态（1）变成状态（2）或者状态（3）。这样，后续的步骤就和前面一样了。
第五步：任一对角线翻转
第六步：任一条边翻转
第七步：任一对角线翻转
如果还不明白，可以看这个流程图。
到 此，这个2×2的问题是解决了。可是，题目的作者又提出了新的难度：推广这个游戏。共有n枚硬币，分别放在一个正n边形棋盘的顶点上。每回合Alice可 以翻转任何一些硬币，Bob则可任意以n种不同的方式(旋转360/n的倍数角度)之一旋转棋盘。游戏一直到所有硬币正面朝上或者反面朝上，Alice获 得胜利。
这个推广我暂时还不会做，大家一起思考一下吧。感觉上好像要用到自动机理论。
No comments:
Post a Comment