Source

I got this problem from Rustan Leino, who got it from Amit Rao.

I solved it and wrote up my solution.

Problem

Two players are playing a game. The game board is a circular table. The players have access to an ample supply of equal-sized circular coins. The players alternate turns, with each turn adding a single coin to the table. The coins are not allowed to overlap. Once a coin is placed on the table, it is not allowed to be moved. The player who has no place to put his next coin loses. Develop a winning strategy for the player who starts. (The table is large enough to accommodate at least one coin.)

Solution
Reveal

On your first turn, place a coin in the center of the table. On each subsequent turn, place a coin symmetrically opposite to the position where your opponent just placed his coin.

To prove the strategy always works, we'll first prove the following statement by induction: whenever your turn starts, it's legal to place a coin according to the strategy above, and whenever your opponent's turn starts, the set of points covered by placed coins is rotationally symmetric about the table's center.

The base cases are turns 1 and 2. The statement is clearly true on these two turns.

For the inductive step, suppose turn $n$ just started and the statement was true for all earlier turns. There are two cases to consider: $n$ is odd and $n$ is even.

If $n$ is odd, then it's your turn. Looking back to the beginning of turn $n-1$, that turn was even, so by the inductive hypothesis the coins formed a set of points rotationally symmetric about the table's center. This means that if any space was empty of coins then the space rotationally opposite it was also empty of coins. The opponent was required, during turn $n-1$, to place his coin on a fully empty space, so the space rotationally opposite it must also have been empty. He can't have placed his coin overlapping the center of the table, because your first coin was already there, so his coin can't have overlapped its own symmetric reflection. Thus, he must have left the space rotationally opposite his coin blank, and you can play there on turn $n$.

If $n$ is even, then it's your opponent's turn. Looking back to the beginning of turn $n-2$, that turn was even, so by the inductive hypothesis the coins formed a set of points rotationally symmetric about the table's center. By the inductive hypothesis, on turn $n-1$ you were able to place a coin rotationally opposite your opponent's coin, so between the two of you two coins were added that preserved rotational symmetry. Thus, the statement is true for turn $n$ as well.

The number of turns must be finite, since it's bounded by the ratio between the table's area and a coin's area. So, eventually someone must not be able to make a legal move. We've proven that it's always possible for you to make a legal move, so it must be your opponent who eventually cannot. Thus, you must win. $\Box$