Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
add comment

3 Answers 3

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|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
add comment

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|improve this answer
    
Interesting explanation. Thanks ! –  Skydreamer Feb 1 '13 at 23:12
add comment

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

share|improve this answer
    
Thank you for the help. –  Skydreamer Feb 1 '13 at 23:00
1  
@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
add comment

Your Answer

 
discard

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.