2 people are playing a game with coins. First, 10 coins are put in a circular form. Then, the players take turns removing 1 coin or 2 coins that are together at each turn. The player who takes the last coin wins. Who has a winning strategy here if both players play optimally? How about if there are 11 coins. Is it possible to generalize for more than 11 coins?

  • $\begingroup$ Start small. If there is only one coin, then who wins? What about if there are two coins? And three coins? You should see a pattern emerge for each $3$ extra coins. $\endgroup$
    – TMM
    Apr 24 '13 at 12:18
  • $\begingroup$ Thanks! If there is only 1 coin, then clearly the first player wins as he would just get that coin. If there are 2 coins, then the first one wins as he would just get the 2 coins. If there are 3 coins, then the second player wins as no matter what the first player gets, he would win by getting the remaining coins, as they are both connected to each other. However, I think that it would be difficult to generalize to more than 3 coins. IF there are 4 coins, the 2nd player will win. If there are 5 coins, then the first player will win. However, it would be too difficult for 6 coins or more. $\endgroup$
    – pseudo2013
    Apr 24 '13 at 12:27
  • $\begingroup$ If there are 6 coins, then the first player would just get 2 coins. Following the pattern, the ones who win is 1st, 1st, 2nd, 2nd, 1st, 1st, .... I think that for 10 coins, the 1st player will win, and for 11 coins, the 2nd player will win. However, I could not prove it. Could someone help me prove it? $\endgroup$
    – pseudo2013
    Apr 24 '13 at 12:30
  • 2
    $\begingroup$ It doesn't seem to be quite as simple as that, because of the requirement that the two coins removed must be next to each other, so sometimes you won't be able to remove two coins even if there are plenty of coins left. $\endgroup$ Apr 24 '13 at 12:35
  • 1
    $\begingroup$ I think this is a version of a game called "kayles", and you might find something by searching for that term. $\endgroup$ Apr 24 '13 at 12:36

Claim 1: If there are two contiguous groups of coins left of equal size, then the player to move loses.

Proof: If the player makes a certain move in one group, the other player can mimick the same move in the other group. At some point the first player will eliminate one of the groups, at which point the second player can also remove the other group, winning the game.

Claim 2: If there is one (non-cyclic) chain left of any length, then the player to move always wins.

Proof: If there is an even number of coins in the chain, you remove the middle $2$ coins, and Claim 1 then proves the result. Similarly, if there is an odd number of coins, you remove the middle coin, and use Claim 1 to finish the proof.

Claim 3: If there is one cyclic chain left of any length $\geq 3$, then the player to move always loses.

Proof: Removing any number of coins from anywhere in the cycle always leaves a non-cyclic chain of a certain length, allowing the next player to win by Claim 2.

So I think the final answer is that the player to move always loses, unless there are only $1$ or $2$ coins in a "circle".

  • $\begingroup$ I think that this resolves the problem already... Thanks for everyone's help! This problem got resolved in around an hour!!! $\endgroup$
    – pseudo2013
    Apr 24 '13 at 13:55
  • $\begingroup$ @Thomas What is the edit about? The groups in Claim 1 are not aligned, but are explicitly assumed to be disconnected, with a gap of any size between them. Maybe I'm misunderstanding the meaning of "contiguous" here but it seems to me your edit does not really make the answer better. $\endgroup$
    – TMM
    Jul 7 at 1:19
  • $\begingroup$ Wel, they don’t allow $0110110$ to be treated as the same as $011110$ where $1$ is a coin, and $0$ is a gap, so it requires more than just the groups having the same number of elements. All you needed, though, was two strings of the same length with no gaps (the coins in each string are contiguous.) You can certainly get more cases of equivalence where this is true, but this was all that you needed for the rest of the argument, and you needed something more than that the coins in the two groups had the same number. Not sure my edit improved things, however. @TMM $\endgroup$ Jul 7 at 1:41
  • $\begingroup$ Ah, I see. Yes, within each group the coins must be contiguous for Claim 1. (After one move by each player from such a position, the two groups could now be four groups though, but the argument shows that any starting position with two connected chains of equal length is a win for the second player.) $\endgroup$
    – TMM
    Jul 7 at 1:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.