2
$\begingroup$

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?

$\endgroup$
  • $\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
  • 1
    $\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$ – Henning Makholm 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$ – Gerry Myerson Apr 24 '13 at 12:36
5
$\begingroup$

Claim 1: If there are two 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".

$\endgroup$
  • $\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

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.