# How to maximize chances to win?

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 ?

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.

• Thank you ! I discovered this game a few days ago and was pretty interested in the math behind. – Cydonia7 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*}

• Interesting explanation. Thanks ! – Cydonia7 Feb 1 '13 at 23:12

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

• @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