3
$\begingroup$

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.

$\endgroup$

1 Answer 1

8
$\begingroup$

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

$\endgroup$
2
  • 1
    $\begingroup$ Thanks. I figured someone had at least thought about this, because it is a pretty obvious generalization. $\endgroup$ Aug 31, 2010 at 20:07
  • 1
    $\begingroup$ 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. $\endgroup$ Aug 31, 2010 at 22:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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