A variation of the game of nim is played with three stacks. Two stacks are blue and one is red. Play consists of removing some positive number of counters from one stack, like normal. But the red stack cannot be touched until one of the blue stacks has been depleted.

Find a winning strategy for this nim variant. (The winner is the person to take the last counter.)

In the classic nim game, there is a strategy involving the binary representation of the numbers in each pile, making sure there are an even number of on-bits in each binary position. But when you are down to just two piles it becomes simply a matter of always presenting your opponent with two equal piles.

The last phase of the present game is like that, where one of the blue piles is exhausted and the red bile and one blue pile remain. So the person who takes the last counter from a blue pile, allowing the red pile to come into play, would want to do so only when the other blue pile contains the same number of counters as the red pile.

The first thought would be that one would want to maintain a difference of R in the heights of the two blue piles until one of them is exhausted, where R is the number of counters in the red pile.  However, if the smaller of the two blue piles contains R or more counters, the above strategy won't exactly work:

Say there are 10 counters in the red pile (R=10), and 35 in one of the blue piles and 33 in the other.  If you reduce the 33 to 25, you will have made the difference equal to R, but your opponent can then reduce the 35 to 15, now presenting you with such a situation also.  They can't both be winning moves. So there has to be a first phase preceding the other two:

Phase 1: The smaller blue pile has R or more counters.
Phase 2: The smaller blue pile has some counters left, but less than  R.
Phase 3: Only a blue and the red pile remain.

In phase 2, give your opponent a difference of R between the two blue piles. In phase 3, leave your opponent with equal-sized piles.

I haven't worked out a strategy for phase 1.

Posted by Charlie on 2009-12-04 12:41:54