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