转桌硬币：可否必胜
硬币翻转
题目详情
4 coins are placed at the corners of a rotating table and the player is blindfolded. At every turn, the player can flip as many coins as he wants, and ask the game master if the coins are all showing heads. If they are all heads, the player wins, otherwise the game master can arbitrarily rotate the table before the next turn. Is there a winning strategy for the player?
解析
有必胜策略。
关键是把硬币配置按“旋转等价类”分组，并注意到玩家每轮还可以通过“翻转全部硬币”同时检验互补配置，从而把等价类进一步合并。对 4 枚硬币，可归并为 4 类状态（全同、一个不同、相邻两个不同、交替不同）。
选取操作等价类（翻全体、翻 1 枚、翻相邻 2 枚、翻交替 2 枚）后，可构造一条确定的操作序列，把任意初始状态在有限步内驱动到“全正面”并在过程中检测成功。
例如使用（每一步都插入一次“翻全体”用于同步检测互补态）的固定序列：
即可保证最终获胜。