Let be an integer. There are distinct circles on the plane such that any two circles have two distinct intersections and no three circles have a common intersection. Initially there is a coin on each of the intersection points of the circles. Starting from , players and alternately take away a coin, with the restriction that one cannot take away a coin lying on the same circle as the last coin just taken away by the opponent in the previous step. The one who cannot do so will lose. In particular, one loses when there is no coin left. For what values of does has a winning strategy?
Solution
has a winning strategy if and only if .
For , after takes away any coin, cannot take away any other coin. Therefore, does not have a winning strategy.
For , we claim that has a winning strategy. Since the total number of coins is even, it suffices to partition all the coins into pairs such that the two coins in the same pair do not lie on the same circle. Once this is done, the strategy of is to take away the coin in the same pair as the coin just taken away by . Clearly, can win as there is always a move, and the number of coins is finite.
We label the circles from to , and let and be the intersection points of circle and circle . For any , we pair up with , where all indices are taken modulo . Since , these two points do not lie on the same circle. Next, we pair up any other point with . Note that and by assumption. Therefore, these two points do not lie on the same circle. This gives a desired pairing, and so we are done.