返回题库

放硬币博弈策略

coin strategy

专题
Strategy / 策略
难度
L4

题目详情

1）圆桌放硬币：两人轮流在圆桌上放同样硬币，硬币不能互相重叠，也不能碰到桌边。不能放者输。若你可以选择先手或后手，给出必胜策略。

2）两人轮流在一张完美圆桌上放硬币，硬币不能重叠且必须完全接触桌面。不能放者输。先手是否更好？是否存在必胜策略？

3）在隔壁房间的桌上玩同样游戏：两人轮流放一枚 25 美分硬币，不能重叠；当桌上再也放不下新硬币时，最后放下硬币的人获胜。已知存在一种与桌子尺寸无关的必胜策略。

(1) 桌子是什么形状？(2) 你要先手吗？(3) 必胜策略是什么？(4) 有哪些情况该策略不奏效？

  1. Coins on a round table game: we take turns placing coins on a round table, no coins can overlap another coin or the edge of the table. If the player who can't place a coin loses and you can choose whether to play first or second, devise a winning strategy.

  2. 2 players take turns placing coins on a large perfectly round table. Coins can not overlap and all the coin surface must be in contact with the table. The first player who can't place a coin loses. Is it better to play first and is there a winning strategy?

  3. We are to play a game on a table in the next room. We each have an infinite bag of identical quarters (i.e.. American 25-cent pieces). We will take it in turns to put one quarter on the table. Quarters may not overlap on the table. When there is no room left on the table to put another quarter, the winner is the last person to put a quarter on the table. Let me tell you that there does exist a strategy for winning and that this strategy is independent of the size of the table.

  4. What is the shape of the table?

  5. Do you start?

  6. What is your strategy for winning?

  7. Is there any case where this does not work?

解析

(1)(2) 圆桌情形：选择先手。

先手第一步把硬币放在圆桌的正中心。

之后采用中心对称镜像策略：若对手在某处放下一枚硬币，你就在关于圆心的对称位置放下一枚。

由于圆桌关于圆心中心对称，且硬币大小相同、不能越界/重叠的约束在中心对称下保持不变，只要对手那步合法，你的对称应对也合法。

因此只要对手还能走，你就一定能走；最终对手先无路可走而输（或在“最后一步获胜”版本中，你能保证自己走最后一步）。

(3) 尺寸无关的必胜策略：桌面必须具有中心对称性，最典型是“圆桌”。你应先手并先占据中心，然后一直做中心对称镜像应对。

(4) 失效情况：当桌子不具备严格的中心对称性、中心点不可放置（有洞/障碍）、桌边限制不是对称的，或硬币不能被精确放在对称位置时，镜像策略可能失效。