# nim with a difference

Marc LeBrun mlb at well.com
Tue Jan 22 09:33:52 CET 2002

``` >=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

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

```