Alice 和 Bob 两人玩一种硬币游戏。游戏在一个$ 2\times2$ 的棋盘上进行,棋盘上每个格子上都有一枚硬币。在每一回合, Alice 可以决定选择翻转某两枚或者一枚硬币,接着 Bob 可以选择将棋盘旋转 90 , 180 或者 270 度,也可以什么都不做。
游戏轮流进行直到棋盘上所有硬币都正面朝上或者反面朝上, Alice 获得胜利。
如果 Alice 在游戏过程中无法看到棋盘上的银币,也不知道游戏刚开始的状态,甚至不知道 Bob 每回合是否旋转了棋盘,那么 Alice 有策略能够获得胜利么?他的最优策略是什么?
接下来我们推广这个游戏。共有$ n$ 枚硬币,分别放在一个正$ n$ 边形棋盘的顶点上。每回合 Alice 可以翻转任何一些银币, Bob 则可任意以$ n$ 种不同的方式(旋转$ 360/n$ 的倍数角度)之一旋转棋盘。游戏一直到所有硬币正面朝上或者反面朝上, Alice 获得胜利。
这时候 Alice 还能取胜吗?
解答在此,但强烈推荐独立思考此题,特别是$ n=4$ 的情况。
via Sariel』s blog
Q. E. D.