9
$\begingroup$

There are $13$ coins arranged in a circular fashion.
Andrew and Bill play a game with these rules:

  • Andrew starts the game
  • A player can remove $1$ or $2$ adjacent coins from the circle during his turn.
  • The one who removes the last coin wins.

Assuming that both players are smart and play optimally, who wins?

An example is shown below:

enter image description here

The brown coin cannot be taken with the yellow or orange coins as it is not adjacent anymore. Similarly, one or both of the orange coins can be taken, but not with a yellow coin or the brown coin.

This puzzle is NOT the 20 coins on the table!

Improve this question
$\endgroup$
4
  • $\begingroup$ I personally would suggest you remove the reference to the previous puzzle... it seems to be confusing to other users. $\endgroup$
    – kaine
    Commented Apr 17, 2015 at 20:49
  • $\begingroup$ @leoll2 I have just added the phase "Either player can choose to make the first move.", see if it applies thanks $\endgroup$
    – Alex
    Commented Apr 17, 2015 at 21:05
  • 1
    $\begingroup$ I don't understand "Either player can choose to make the first move." What if they both want to, or neither wants to? $\endgroup$
    – xnor
    Commented Apr 17, 2015 at 21:12
  • $\begingroup$ @xnor That edit was made by another user, and was later removed because in conflict with the original puzzle. $\endgroup$
    – leoll2
    Commented Apr 18, 2015 at 13:31

4 Answers 4

Reset to default
9
$\begingroup$

https://math.stackexchange.com/questions/371420/logic-coin-game

The answer is mostly taken from the Math.SE site as linked above.

If the game has two separate piles of the same size, the player to move loses as the other player can mirror his moves.

If there is a single chain left the player to move can make there be two same size piles and, therefore, force a win. If the chain length is odd, he removes the middle coin. If it is even, he removes the middle two coins.

If there is a cyclic ring, the first player's move will make a chain as just described.

By this the second player will always win for a size 13 circle.

Improve this answer
$\endgroup$
2
  • $\begingroup$ This proof seems to hold for any circle with more that 2 coins in it.... though I have no idea how you could even make a circle with 2 coins in it.... $\endgroup$
    – kaine
    Commented Apr 17, 2015 at 20:53
  • 1
    $\begingroup$ Just use non-circular coins: fleur-de-coin.com/images/articles/poland10zloty.jpg $\endgroup$
    – Joel Rondeau
    Commented Apr 17, 2015 at 21:12
1
$\begingroup$

The first person to act loses for any number $3\le n+3$. (With the trivial exception of a 1-coin or 2-coin circle, where the first person simply takes all the coins on the first turn.)

The first player has two choices: take one coin, or take two coins. In perfect play, the second player will always take the opposite number (or the same number in even-numbered coin starts), directly across the circle, dividing the remaining coins into two equal groups.

At this point, there are two identical sets:

$\{C_1C_2C_3\ldots C_n\},\{C_1C_2C_3\ldots C_n\}$

Wherever the first player next takes coins, the second player mirrors the move exactly in the other set. For every $1\le m\le n$ (or pair of consecutive $1\le m_1\lt m_2\le n$), there is always the matching $m$ (or $m_1m_2$) in the other set.

Because of the symmetry, the second player always has coins to take, hence the second player will take the last coin and win.

Improve this answer
$\endgroup$
0
$\begingroup$

I will talk about the chain case, i.e. all coins lie in a row. In the circle case, the first move breaks it into a chain.

This is then the octal game with signature $0.77$, also known as Kayles.

The nimber of this game is known to be eventually periodic, with a period of $12$: $$4, 1, 2, 8, 1, 4, 7, 2, 1, 8, 2, 7.$$

So the only losing position for Kayles is to start with zero coins. Therefore in the chain version, the first player wins if and only if the chain contains $1$ or $2$ coins.

Improve this answer
$\endgroup$
-1
$\begingroup$

Originally I said A(ndrew) won, by using a theory of how many coins are remaining to determine where (and how many) to take, but that was wrong.

If you take 1 coin, then 1 coin is taken 2 down, you're left with 10+1 coins.

I was considering doing something with groups of 6 (after taking 1) but then they merge, so that is an issue, especially if 2 coins are taken from the middle of the remainder.

If 1+1 coins are taken from "opposite" ends, we'd have a 5+6 chain. The 5 chain, the first player can win, the 6 chain, the 1st as well. At that point, player B would win.

If 1+2 coins are taken from the opposite ends, we'd have a 5+5 chain. In both chains, the first player can win. However, if the first player wins in both chains, player B wins. However, each player can also lose their 5 chain, making them the winner of the other. But if mirrored plays are done, then player B wins.

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ Maybe you forgot the "adiacent" condition. $\endgroup$
    – leoll2
    Commented Apr 17, 2015 at 20:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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