nim with a difference

[Antti Karttunen]

Marc LeBrun wrote:

> 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,

Yes, isn't this quite clear? (Even I understand this ;-)
You mean the sequence:
http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A000914

 2,11,35,85,175,322,546,870,1320,1925,2717,3731,5005,6580,

s(n+2,n), that is the number of  n+2 letter permutations with n cycles.
So only cycles that can occur are 1-, 2- and 3-cycles.
 From two cycles there is an obvious mapping
from {(a b) = (b a)} to {| a - b | = | b - a |}, and with 3-cycles
we have only two distinct cycles (a b c) and (b a c).
Now, let's assume WLOG that a > b > c, and we have these
cases:

   | | a - b | - c | = | | a - c | - b |
= | | b - a | - c | = | | c - a | - b |

and the other set with two members
(with value guaranteed to be distinct
from the value occurring in the first set)

  | | b - c | - a | = | | c - b | - a |


However, I'm now too blind/lazy to see the clue
in your comment about the final positions:

>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.

And on what set these maximums are attained? Only with powers of 2 or
with any distinct set of integers?


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

Minimize/maximize the final difference? Is there a too easy strategy for that?


Terveisin,

Antti Karttunen