Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Optimal Strategy and proof for the Space Race (Riddler Classic), https://fivethirtyeight.com/features/who-will-win-the-space-race/
The player that places first is guaranteed to win, as long as he/she uses the optimal strategy.
Winning Strategy
----------------
1. First player begins by placing the first coin right right at the center of the table
2. Second player places a coin anywhere on the table
3. First player tries to mimic second player's coin in the following way:
Imagine rotating the table about the center by 180 degrees, then place the coin where the second player's coin was before the rotation.
Done correctly, this newly placed coin makes the table look identical under a 180 degrees rotation about the center.
4. If there is no more space on the table, first player wins. Otherwise go back to Step 2.
Proof
-----
Note that the table is always symmetrical about a 180-degrees rotation at the end of the first player's turn.
The second player then breaks the symmetry (and has no choice but to do this) and the first player restores it.
Now consider the last coin placed by the second player: Before the coin was placed, the table must be symmetrical under
rotation. This means if there is enough room for the second player to place a coin, there must also be a corresponding
spot for the first player.
Additional Comments
-------------------
This strategy works for tables with shapes other than squares, as long as it is symmetrical under a 180 degrees rotation the first player can always win.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment