nim with a difference

Marc LeBrun mlb at well.com
Fri Jan 18 20:26:30 CET 2002


Here's a nimic game associated with some curious sequences.

I don't know the game's object yet, but a move consists of replacing any 
two piles with their (absolute) difference.

For example, the four pile position 1248 can go to the three pile position 
247 by playing the 1 and 8 piles.

The entire move tree for 1248 is as follows.  Initially of course we have

   1248.

After the first move we have the expected choose(4,2) maximum of six 
possible positions.  In our example they are

   124 128 146 148 238 247.

Strangely, it turns out that after the second move in any four pile game we 
can have at most ELEVEN distinct positions.  Here these are

   12 14 16 18 23 25 27 36 38 45 47.

Then after the third and final move this collapses down to a maximum of 
four, here

   1 3 5 7.

It's not hard to see that for N>1 piles the maximum number of final 
positions is 2^(N-2), so we can characterize the maximum number of possible 
positions after both the first and last moves.

What about the rest of the move tree?  Here's what I think it looks like, 
with the Nth row being the N-pile game:

                    1
                1       1
             1      3       2
         1      6      11       4
      1     10     35      40       8
   1    15     85     195      148     16
1   21    175    665     1078     560    32

The next diagonal parallel to the triangular numbers are apparently the 
first Stirling numbers, but I don't find any others (or obvious derivations 
such as first differences) in the OEIS.

Can you describe this array?

(Extra credit: devise a playably interesting object for this "game"!<;-)






More information about the SeqFan mailing list