The game of coins on a round table
Statement
Two players take turns placing identical round coins on a circular table. Each coin must lie completely on the table and must not overlap the coins already placed (touching is allowed). The player who cannot place a coin loses. (A coin fits on the table.) Prove that the first player has a winning strategy.
Hint
Use the centre of the table. The first player should have a reply to every possible move of the second one.
Show solutionHide solution
Solution
Idea. A symmetry strategy: after the first move, always answer by the symmetric move.
Strategy. Let be the centre of the table and the radius of a coin. The first player puts his first coin with its centre at . Afterwards, each time the opponent places a coin with centre , the first player places a coin with centre , the reflection of in .
Invariant. Just before each move of the second player, the position is symmetric with respect to .
The reply is legal. Let the second player place a coin at (legal, so ).
- *On the table:* the table is symmetric about , so the coin at lies completely on the table.
- *No overlap with the coin at :* two coins overlap iff their centres are at distance less than . Here because the move at was legal and is occupied.
- *No overlap with the other coins:* by symmetry, if the coin at overlapped some coin , then the coin at would overlap the reflection of : impossible.
Conclusion. The first player always has a legal reply. Since the table has finite area, the game ends after finitely many moves, and the player who cannot move is the second one.
Lesson. Symmetry strategy: if the board has a central symmetry, occupy the centre and mirror every move of the opponent.