5
$\begingroup$

this is a variation of the coin pile removing game that I have seen in various places online. In this case the properties are as such:

There are n stacks of coins all potentially different sizes. Starting with Player A, the players A and B take turns removing either one or all the coins from one of the stacks. The person left with no turn possible loses. How would I go about solving this problem?

$\endgroup$
7
  • 1
    $\begingroup$ You start looking for $P$ (won by the previous player) and $N$(won by the next player) positions. An $N$ position is one that can move to a $P$ position. A $P$ position is one that can only move to $N$ positions. Start with small positions and build up, looking for a pattern. You could read about Nim and the Sprague-Grundy theorem. As a perfect information impartial game, it is Nim in disguise in that every position can be equated to a Nim-stack. Finding the correspondence can be hard. $\endgroup$
    – Ross Millikan
    Commented Nov 11, 2016 at 16:54
  • $\begingroup$ I'm still a little confused would you be able to clarify these examples? So would any single pile be an N position? Following up, if you have two piles of one coin each, that would be a P position? Then, with two piles of equal size, that would be a P position? Again, as more followup, would just xor-ing the size of the piles and checking for them to equal zero fail? $\endgroup$
    – Bob Marley
    Commented Nov 11, 2016 at 17:09
  • $\begingroup$ Well, xor-ing just fails in the case of 3 piles with 3 coins each $\endgroup$
    – Bob Marley
    Commented Nov 11, 2016 at 17:15
  • $\begingroup$ Yes, a single pile is N because you can take it all and two equal piles are P because the second player can mirror the first. XORing fails because 1+n is P if n is odd because anybody who takes the 1 loses, so both players take a coin at a time from the large stack. You get down to 1+1, which is P. $\endgroup$
    – Ross Millikan
    Commented Nov 11, 2016 at 17:16
  • $\begingroup$ If you can find a collection of piles that is P, you can ignore it. A player who is winning in the rest can only move in that collection when his opponent does and keep that collection P. Your 3+3+3 example works this way. Two of the piles make a P position, the third is N, so the whole thing is N. This shows any position that is a+a+b is N-just take the b pile. $\endgroup$
    – Ross Millikan
    Commented Nov 11, 2016 at 17:20

2 Answers 2

Reset to default
2
$\begingroup$

This game is similar to Nim and can be solved using the Sprague-Grundy theorem.

We can calculate the Nim-values of the stacks in your game by looking at the choices available and finding the minimal excluded element, or mex.

Let $v(n)$ be the Nim-value of a stack of size $n$. Then:

  • A pile of size $1$ can only be reduced to $0$; $v(1) = mex(\{0\})=*$.
  • A pile of size $2$ can be reduced to $0$ or $1$; $v(2) = mex(\{0,v(1)\})=*2$.
  • A pile of size $3$ can be reduced to $0$ or $2$; $v(3) = mex(\{0,v(2)\})=*$.
  • A pile of size $4$ can be reduced to $0$ or $3$; $v(4) = mex(\{0,v(3)\})=*2$.
  • $\ldots$

In short, we can look at each pile as being either empty, even, or odd.

$\endgroup$
13
  • $\begingroup$ It's a variant of nim since you may take just one coin or a whole pile. Does the wikipedia page discuss that variant? If not, you'd have to construct the Sprague-Grundy function yourself. $\endgroup$
    – Ethan Bolker
    Commented Nov 11, 2016 at 16:56
  • $\begingroup$ @Théophile I am still a little confused regarding your statement. Do you mean a pile of size 1 or that we have 1 pile, 2 piles, 3 piles, and so on? $\endgroup$
    – Bob Marley
    Commented Nov 11, 2016 at 19:11
  • $\begingroup$ @BobMarley This is all looking at individual piles. So a pile of size $4$, say, has the value $*2$. If you have multiple piles, you can analyze the game by adding the nimbers associated with them. For example, if there are three piles with sizes $4,5$, and $6$, then the value of the whole is $*2 + * + *2 = *$. This is a win for the next player to move (who wins by taking one stone from the middle pile, or that entire pile). $\endgroup$
    – Théophile
    Commented Nov 11, 2016 at 20:29
  • $\begingroup$ @Théophile: taking one stone from the 5 in 4+5+6 loses. That leaves 4+4+6 and I take all of the 6 to win. A winning position is one that has an even number of even piles and an even number of odd piles. Once you find the odd piles are * and the even ones are *2 the usual Nim addition or XOR rules apply. $\endgroup$
    – Ross Millikan
    Commented Nov 11, 2016 at 20:41
  • $\begingroup$ Wait, so the solution is as simple as assigning * or *2 to each of the piles and applying xor 1 xor 2 to all the resulting values? And doesn't player 1 automatically win 4,5,6 with best play? $\endgroup$
    – Bob Marley
    Commented Nov 11, 2016 at 21:08
1
$\begingroup$

Prompted by Théophile's answer, we can make a direct statement of how to play the game. We claim the $P$ positions, won by the previous player, are those that have an even number of piles with an even number of stones and an even number of piles that have an odd number of stones, and the $N$ positions are the rest. To prove this we need to show that the terminal position is $P$, that all moves from $P$ positions result in $N$ positions, and that every $N$ position has at least one move to a $P$ position. The terminal position has no piles, so has an even number of piles of each parity. From a $P$ position, any move will leave an odd number of piles of the parity moved in. If the move leaves stones in the pile moved in, it will also leave an odd number of piles of the other parity, but we don't need that. If there are an odd number of piles of one parity and an even number of the other, take an entire pile of the parity with an odd number of piles and this will leave a $P$ position. If there are an odd number of piles of each parity, take one stone from a pile with an even number of stones and this will leave a $P$ position. This shows the $N$ and $P$ positions are as claimed and gives a specific move where there is a winning one (the $N$ positions).

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .