This Riddler puzzle is about a game involving filling up the space on a square table using coins.
Two players are seated at a square table. The first player places a coin on the table, the second places a coin on the table, and they carry on placing coins one after another, with the only condition being that the coins are not allowed to touch. The winner is the person who places the final coin on the table, meaning that he or she fills the last remaining space between the other coins.
The table has to be larger than a single coin, and all the coins placed must be identically sized. If the players play optimally, is one of the two players guaranteed to win? If so, what is the winning strategy?
Need a hint?
[Show Solution]
Use symmetry!
Here is my solution:
[Show Solution]
It’s easy to get stuck thinking that this problem has some sort of solution involving the pigeonhole principle; there is this tendency to try and subdivide the table into some sort of grid and argue that only so many coins can fit in each cell. This turns out to be very difficult since circles can be tiled in complicated ways. The solution to this problem turns out to be much much simpler.
Let’s call the players Alice (first player) and Bob (second player). Alice always wins, and the strategy is as follows: Alice places her coin in the center of the table. Then, no matter what Bob does, Alice responds by placing a coin radially opposite to the coin that Bob placed, and at an equal distance to the center. Whenever it’s Bob’s turn to play, the board is in a symmetric arrangement of coins. So for every spot Bob can place a coin, there is an identical open spot opposite it where Alice can play her response. Eventually, Bob has no space left to play and Alice wins!
Here is a simulation showing Alice (magenta) and Bob (blue) that illustrates how the game could play out assuming optimal play from Alice and random play from Bob. (board size is 10×10 and coins have a diameter of 1).
This result also holds for tables that are not square, it only has to be symmetrical under rotation of 180 degrees about the center of table.
Your proof also holds for dimensions higher than 2, for example placing spheres inside a cuboid.
The shape can be symmetrical under rotation of 180 degrees (point symmetric) so long is there’s a place at the center (or anywhere else) to have one coin (otherwise it can have holes wherever).
I think it might also permit quite a bit of skewing and have the strategy still work, but haven’t analyzed this to be sure.
Good point Mike. Another way to think of this is the first coin must not break the symmetry. If there is a hole then I think it can be shown that the second player will always win.
The (pseudo-)solution here is completely unsatisfactory.
The original formulation of the problem asserts only the identity of coins,
but says nothing about the internal symmetry of each individual coin.
Not sure what you mean by “internal symmetry”. I did assume that the coins are circular, which I think is a reasonable thing to assume about a coin… But my solution also works for non-circular coins, as long as the coins have the same rotational symmetry mentioned in the other comments, e.g. ellipses, regular polygons with an even number of sides, etc.
Feel free to suggest an alternative solution!
Rotational symmetry of coins is not necessary. As long as they are identical they can be placed with rotational symmetry from the center. Right?
That’s true for all the coins except the first one. The first coin needs rotational symmetry!
Right, sorry!