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
David Gale:
... 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.
Thane Plambeck:
Case II: (Two nonempty heaps, sizes m and n). Everything is an N-position. A wiinning move [is] to take everything in one of the heaps.
Case III: (Three nonempty heaps, sizes r,s,t). Assume r <= s <= t. ... Is it hopeless to give a formula for the Case III nim equivalent?
I looked at Gale's Nim briefly on the weekend. With only three piles, emptying a pile loses quickly, and the game is similar to one in which that's illegal. In fact, GaleNIM position (r,s,t) is P if and only if NIM's (r-1,s-1,t-1) is P. Also, you might enjoy proving that GaleNIM(1,r,s,t) is P iff NIM(r,s,t) is P. -- Don Reble djr@nk.ca
Case III: (0,1+b,1+c,1+d) is a P-position iff nimsum (b, c, d) = 0. Case IV.1: (1,b,c,d) is a P-position iff nimsum (b, c, d) = 0. But case IV.2 (positions (2,b,c,d)) and the general case VI don't seem to have any such nice form. I've found P-positions (2,b,c,d) wiht 2 <= b <= 6. - Scott
David Gale writes:
Before I start here's something more in the math-fun spirit. I'm offering tw o hundred bucks ($200) for a solution of the following Nim variant. There are 4 piles, ordinary Nim rules, the only difference being that the ga me 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 play er 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. Wha t 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 po sition, 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), E T CETERA, where I don't really know what ET CETERA means. Assuming this correspondence is valid, how to reco ver 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
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Here are some distressing facts about 4 pile Nim. This is a theorem (which I once knew how to prove). For piles (a,b,c,d), hold a and b constant and define f(c) as the (unique) value of d such that (a,b,c,d) is a P position. Then f(c)-c is eventually periodic. Some of you if you have a good program might find it amusing to look at these periods even for the special case where (2,b,c,d) as you increase b. There seems to be no discernable pattern. Adries Brouwer of Eindhoven Technical University ran a program and concluded that most conjectures one might make turn out to be (eventually) false. t 01:16 AM 1/21/04 -0800, you wrote:
Case III:
(0,1+b,1+c,1+d) is a P-position iff nimsum (b, c, d) = 0.
Case IV.1:
(1,b,c,d) is a P-position iff nimsum (b, c, d) = 0.
But case IV.2 (positions (2,b,c,d)) and the general case VI don't seem to have any such nice form. I've found P-positions (2,b,c,d) wiht 2 <= b <= 6.
- Scott
David Gale writes:
Before I start here's something more in the math-fun spirit. I'm offering tw o hundred bucks ($200) for a solution of the following Nim variant. There are 4 piles, ordinary Nim rules, the only difference being that the ga me 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 play er 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. Wha t 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 po sition, 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), E T CETERA, where I don't really know what ET CETERA means. Assuming this correspondence is valid, how to reco ver 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
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Some time ago I wrote the following in response to a David Gale message. It seems (not surprisingly?) not to have been completed. For what it is worth, I belatedly send it. R. Yes, someone else is biting. I'll do anything for money. Perhaps Don or Thane or Scott will give me 10% of the takings, if they push through the rest of this. I wonder if David will pay up for a complete STRATEGY, or does he want a complete ANALYSIS ? 1 non-empty heap. P-position. nim-value 0 2 non-empty heaps, sizes a and b. N-position. STRATEGY: Take whole of either heap. ANALYSIS: nim-value [(a-1)nim(b-1)] + 1 3 non-empty heaps, sizes a, b, c. STRATEGY: Pretend that you can't see the last bean in each heap. If you're forced, or stupid enough, to take a whole heap, see `2 non-empty heaps' above. Otherwise, play ordinary Nim on the heaps that you can `see'. I.e., you aim to `finish' the game by leaving (1,1,1). ANALYSIS: P-positions are just those with (a-1)nim(b-1)nim(c-1) = 0. However the general nim-value of (a,b,c) seems to be chaotic (though, as David Gale and others have shown, the value for fixed a, b is ultimately arithmetico-periodic). Examples of P-positions: (n,n,1), {2n+2,2n+1,2) (4n+3,4n+1,3), (4n+4,4n+2,3), ... 4 non-empty heaps, sizes a, b, c, 1. STRATEGY: Play ordinary Nim on heaps a, b, c. If your opponent takes the 1-heap, then pretend as above. Note that on parity grounds (a,b,c) and (a-1,b-1,c-1) can't both be P-positions. 4 non-empty heaps, all of size 2 or more. STRATEGY: If two heaps are of equal size, equalize the other two. If two pairs of equal heaps, hope that it's your opponent's turn to play. Note that you are playing MIS`ERE Nim on the first of the two pairs to vanish. That is, if your opponent goes to 1 or 0 in a heap, then you go to 0 or 1 respectively in the previously equal heap. So, assume that all heap sizes are distinct and at least 2. If any three heaps form a three-heap P-position, take the fourth heap. E.g., (2,3,4,n) is an N-position ---> (2,3,4) The smallest non-trivial P-position comprises the Fibonacci numbers (2,3,5,8). Here are good replies to all moves from this. 1358-->1356 358-->357 2258-->2255 2158-->2157 258-->256 2348-->234 2338-->2332 2328-->2323 2318-->2311 (mis`ere!) 238-->234 2357-->357 2356-->256 2355-->2255 2354-->234 2353-->2323 2352-->2332 2351-->2311 235-->234 In general the P-positions are those for which (a-1)nim(b-1)nim(c-1)nim(d-1) = 0, with the caveat that none of the heaps is 1. On such 1-heaps we are playing mis`ere Nim.
Hi Richard, Your analysis is good until the final claim of a general case. E.g., the general case wants 3456 to be a P-position, but the already noted exception 3156 (a P-position) from the abc1 family makes 3456 an N-position. Now 3456 being an N-position means there are unique P-positions 345_, 34_6, and _456. My calculations find these P-positions to be 3457, 3486, and 9456, which all violate your general case claim. Best, - Scott
Some time ago I wrote the following in response to a David Gale message. It seems (not surprisingly?) not to have been completed. For what it is worth, I belatedly send it. R.
Yes, someone else is biting. I'll do anything for money. Perhaps Don or Thane or Scott will give me 10% of the takings, if they push through the rest of this.
I wonder if David will pay up for a complete STRATEGY, or does he want a complete ANALYSIS ?
1 non-empty heap. P-position. nim-value 0
2 non-empty heaps, sizes a and b. N-position.
STRATEGY: Take whole of either heap. ANALYSIS: nim-value [(a-1)nim(b-1)] + 1
3 non-empty heaps, sizes a, b, c.
STRATEGY: Pretend that you can't see the last bean in each heap. If you're forced, or stupid enough, to take a whole heap, see `2 non-empty heaps' above. Otherwise, play ordinary Nim on the heaps that you can `see'. I.e., you aim to `finish' the game by leaving (1,1,1).
ANALYSIS: P-positions are just those with (a-1)nim(b-1)nim(c-1) = 0. However the general nim-value of (a,b,c) seems to be chaotic (though, as David Gale and others have shown, the value for fixed a, b is ultimately arithmetico-periodic).
Examples of P-positions: (n,n,1), {2n+2,2n+1,2) (4n+3,4n+1,3), (4n+4,4n+2,3), ...
4 non-empty heaps, sizes a, b, c, 1.
STRATEGY: Play ordinary Nim on heaps a, b, c. If your opponent takes the 1-heap, then pretend as above. Note that on parity grounds (a,b,c) and (a-1,b-1,c-1) can't both be P-positions.
4 non-empty heaps, all of size 2 or more.
STRATEGY: If two heaps are of equal size, equalize the other two. If two pairs of equal heaps, hope that it's your opponent's turn to play. Note that you are playing MIS`ERE Nim on the first of the two pairs to vanish. That is, if your opponent goes to 1 or 0 in a heap, then you go to 0 or 1 respectively in the previously equal heap.
So, assume that all heap sizes are distinct and at least 2. If any three heaps form a three-heap P-position, take the fourth heap.
E.g., (2,3,4,n) is an N-position ---> (2,3,4)
The smallest non-trivial P-position comprises the Fibonacci numbers (2,3,5,8). Here are good replies to all moves from this. 1358-->1356 358-->357 2258-->2255 2158-->2157 258-->256 2348-->234 2338-->2332 2328-->2323 2318-->2311 (mis`ere!) 238-->234 2357-->357 2356-->256 2355-->2255 2354-->234 2353-->2323 2352-->2332 2351-->2311 235-->234
In general the P-positions are those for which (a-1)nim(b-1)nim(c-1)nim(d-1) = 0, with the caveat that none of the heaps is 1. On such 1-heaps we are playing mis`ere Nim.
participants (5)
-
David Gale -
Don Reble -
Richard Guy -
Scott Huddleston -
Thane Plambeck