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