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