N-Quarters in a circle, remove either one each turn, or two tangent coins each turn. Whoever takes the last quarter loses.

100 Views Asked by At

There are N quarters arranged in a circle so that each quarter is tangent to the two adjacent quarters. At each turn, a player removes either one quarter anywhere in the circle or two quarters that are tangent to each other. The player who takes the last quarter loses.

I'm trying to figure out for what values of 'n' is makes going 1st better and what value of 'n' makes going second better.

For one coin, obviously going second is a win. For two coins, going first is a win. For three coins, going first is a win. For four coins, going second is a win. For five coins, going first is a win.

I don't see a pattern out of these. This problem comes from a Boston University Number Theory camp.

All help appreciated.

For 6 coins, going first is a win.

1

There are 1 best solutions below

5
On BEST ANSWER

After the first move, this game is isomorphic to a game of misère Kayles. Kayles is played with a line of quarters instead of a circle, and the legal moves are removing any quarter or any pair of adjacent quarters. The word "misère" means that the player who removes the last quarter loses, while in "normal" Kayles, the player who takes the last quarter wins.

Normal play Kayles is quite simple; the first player wins for a row of quarters with any nonzero length, by dividing the row in half and using a mirror strategy. Misère Kayles was solved by Seifert and Conway (https://doi.org/10.1007/BF01253778). The solution is described in section $5$ of Daisies, Kayles, and the Sibert-Conway decomposition in misère octal games (https://doi.org/10.1016/0304-3975(92)90343-E). The misère play outcome is usually equal to the normal play outcome, and that paper describes the full list of exceptional positions where the misère outcome is opposite the normal outcome. In particular, the only $n$ for which a row of $n$ is a second player win in misère Kayles are the following: $$ 1,4,9,12,20 $$ Therefore, for the misère game of $n$ quarters in a circle, the game is always a second player win, unless the first player can produce a row with one of the exceptional lengths above, which which is possible iff it exceeds those numbers by $1$ or $2$. That is, the only $n$ for which the first player wins with $n$ quarters in a circle are: $$ 2,3,\; 5,6,\; 10,11,\;13,14,\; 21,22 $$ This agrees with what you have found so far.

However, the winning strategy for misere Kayles is not simple, and certainly not something you would expect an undergraduate to be able to find over the course of a summer.