Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

The game of Nimble is played as follows. You have a game board consisting of a line of squares labelled by the nonnegative integers. A finite number of coins are placed on the squares, with possibly more than one coin on a square. A move consists of picking up one of the coins and placing it on a square somewhere to the left of its original position. Players alternate moves. The game ends when no moves are possible, i. e. when all the coins are on the square labelled 0. The last player to move wins.

As described, this is just Nim in disguise, where a coin in position $n$ corresponds to a pile containing $n$ coins. The winning strategy is well-known. Define the nim-sum of some positive integers as the result when they're written in binary and addition is performed without carrying. Then the only winning positions are those where the nim-sum of all the pile sizes (or coin positions) are zero.

But what is the winning strategy if we don't allow coins to be stacked? This corresponds to Nim where we don't allow two piles of the same size, but this restriction feels a lot more natural in Nimble than in Nim.

There are two reasonable terminal positions. One is to allow stacking on the square marked zero only, and say the game terminates when all the coins are at zero; the other is to not allow stacking and say the game terminates when coins are on $0, 1, \ldots, k-1$ if there are $k$ coins. Either one would be of interest.

If someone gives me an answer by Friday, I might talk about it in my class.

share|improve this question

1 Answer 1

This is Welter's game, analysed in detail in Conway's On Numbers and Games chapter 13. It gets quite complicated....

share|improve this answer
    
Thanks. I figured someone had at least thought about this, because it is a pretty obvious generalization. –  Michael Lugo Aug 31 '10 at 20:07
    
Upon skimming Chapter 13 of ONAG, I've come to the conclusion that if I talk about this in class at all, it'll be just to briefly mention that the theory of this seemingly simple variation is much more complicated. –  Michael Lugo Aug 31 '10 at 22:17

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.