Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let's say I have $n$ stacks of coins such as the $i$-th stack contains $c_i$ coins at the beginning of a game.

The game is simple. The players have to take any number of coins from one stack (and only one) during their turn.

The person taking the last coin loses the game.

Is there a good strategy to win or is the game too prone to randomness ?

share|cite|improve this question
up vote 4 down vote accepted

This is the misère version of Nim; it is very well studied, and the winning strategies for both the regular and the misère versions are described (and their correctness proved) in the linked article.

share|cite|improve this answer
Thank you ! I discovered this game a few days ago and was pretty interested in the math behind. – Skydreamer Feb 1 '13 at 23:00
@Skydreamer: You’re welcome. If you dig around on the Web, you’ll find all kinds of information on it. – Brian M. Scott Feb 1 '13 at 23:14

This is an example of nim. I would recommend Conway's On Numbers And Games (ISBN: 1568811276) if you want a terrific read on the subject and much, much more.

I'll present the typical strategy, though I won't prove it (and I would post this as a comment, but I'm afraid I'm not allowed...):

Suppose we have a stack of $3$, one of $6$ and one of $7$. We now wish to find the value of this position. We do this by first converting the sizes of the stacks to binary ($011, 110$ and $111$), and then add them without carrying:

\begin{align*} &011 \\ &110 \\ +&111 \\ -&-- \\ &010 \end{align*}

So the value of our position is $2$. Now, to find a winning move, we add $2$ to one stack at a time, in the same manner as before. In doing so we get $001, 100$ and $101$, respectively. Pick any one of those alternatives that are legal (meaning they reduce the size of the given stack. In this case all of them are) and you'll be giving your opponent a position of value $0$, meaning it's a losing position.

For example, $001, 110$ and $111$, or $1, 6$ and $7$:

\begin{align*} &001 \\ &110 \\ +&111 \\ -&-- \\ &000 \end{align*}

share|cite|improve this answer
Interesting explanation. Thanks ! – Skydreamer Feb 1 '13 at 23:12

This is the game of Nim. There is no randomness and the strategy is well studied.

share|cite|improve this answer
Thank you for the help. – Skydreamer Feb 1 '13 at 23:00
@Skydreamer: For a detailed description, Winning Ways Volume 1 by Berlekamp, Conway, and Guy will take you through it. All games that have perfect information and the same moves available to each player from a given position are equivalent to a single Nim heap. They show how to figure out the size for many such games. – Ross Millikan Feb 1 '13 at 23:09

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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