nim with a difference

[Marc LeBrun]

 >=Antti Karttunen
 > [...]
 >  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.

OK, I *think* I understand your argument:  Since after the 2nd move you can 
only have these kinds of cycles then the case analysis can be carried out 
explicitly (as you proceed to do).

So then what is the next (3rd move) anti-diagonal 4, 40, 195, 665...?  Do 
these diagonal sequences form some family that goes

   constant 1, choose(n,2)=choose(n,n-2), stirling(n+2,n), ...?

 > However, I'm now too blind/lazy to see the clue
 > in your comment about the final positions: [being 2^(N-2)]

Well maybe in my case it's the blind blinding the sighted!  After further 
thought I'm finding some holes in my original ideas that I'll have to patch 
up (unless someone more clearheaded can explain it).

Anyway if that diagonal is simply powers of two, what's with the next diagonal

   1, 3, 11, 40, 148, 560...?

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

I think always with powers of 2, and certainly for powers of X >> N, but 
not generally, and certainly not for crowded sets like {1,2,3,4}.  I recall 
{7, 11, 13, 14} has the maximum number of 2nd and 3rd positions, but only 
three final values instead of four.

For each N, what are the smallest spreads/totals/etc that produce a maximum 
tree?

 > [object:] Minimize/maximize the final difference?  Is there a too easy 
strategy for that?

I don't know.  Just N=4 makes my head swim.  Question: using this 
objective, does the optimal strategy depend on the actual values, or can it 
always be expressed as "on move i choose the j-th largest value"?

By the way, I picked absolute difference because it commutes but doesn't 
associate (is there a name for that?).  When the set is sufficiently spread 
out the result depends only on the group theory, but as the things condense 
the geometry of the integers has an increasing effect.

"Enjoy"!