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.
No comments:
Post a Comment