David Gale writes:
> Before I start here's something more in the math-fun spirit. I'm offering two hundred bucks ($200) for a solution of the following
Nim variant.
> There are 4 piles, ordinary Nim rules, the only difference being that the game ends when three of the four piles are empty.
OK---I'll bite, if no one else will.
Case I: (Single non-empty heap)
Answer: *0 (the game is already over) everything is a P position, ie 2nd player to move wins.
Case II: (Two nonempty heaps, sizes m and n).
Everything is an N-position. A wiinning move to take everything in one of the heaps.
For extra credit (but not for the $200), after a few minutes of noodling I got
the nim heap equivalent is BitXor[m-1,n-1] +1.
Case III: (Three nonempty heaps, sizes r,s,t). Assume r <= s <= t.
Every move involving taking a whole heap leads to a (Case II) N position. What are the three heap P positions?
1,1,1 is a P position for example. Then 1,1,t for other t>1 is always an N position, since there's a move to 1,1,1.
It looks like the P positions are in one-to-one correspondence with every pair (a,b) = (s-r, t-s) with a, b nonnegative.
Ie, the P position (1,1,1) corresponds to the choice (a,b) = (0,0), and (for example), the P position (2,3,4) corresponds to
the choice (1,1), (and for another example), (4,6,7) corresponds to (2,1), ET CETERA, where I don't really
know what ET CETERA means. Assuming this correspondence is valid, how to recover r from a and b? This should
be achievable---but not after two glasses of chianti. Is it hopeless to give a formula for the Case III nim equivalent?
Case IV: (Four nonempty heaps).
Hmmm....
Thane Plambeck
650 321 4884 office
650 323 4928 fax
http://www.plambeck.org
