# 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"!<;-)

```