A game with coins

Another logical riddle frequently asked at the interviews.

Two players play a game that involves a table shaped as a perfect circle with finite radius R and an unlimited set of disc-like coins of radius r, all of the same size and weight. The game is played as follows: the players place coins on the table in turns, one by one. Every coin has to lie flat on the table, it can’t lie on the other coins; the face of the coin should be touching the face of the table; the coin can’t dangle from the table’s edge; it can touch previously placed coins, but they can’t be pushed from their place or dropped from the table. The first player who can’t find a place for his coin loses.

Is there a winning strategy for one of the players? If yes, what is it?

The finite radius of the table and the non-zero radius of the coin, along with the requirement of the coin being laying flat on the face of the table, promises that the game is finite. This problem is known as the circle packing in a circle problem, and it is known to be a generally NP-hard, but for large difference between r and R the approximation of the upper bound for the number of coins is N ≈ 0,9×r ²/R ²​.

There is a web site dedicated solely to solving this kind of problems.

Solution

Yes, there is a winning strategy; the player who makes the first turn always wins. He must place his first coin in the very center of the table; each next coin should be placed symmetrically from the place where the second player placed his coin, relative to the center of the table. If the second player succeeds to find a place for his coin, the strategy guarantees that at the next turn the first player will also succeed to place his one. If there is no enough place, the second player will hit the problem first.