[math-fun] variation on nim
My 10-year-old son introduced me to the following variation on nim. Instead of allowing the players to take any number of counters from a pile on a turn, the counters in each pile are arranged linearly, and then you can only remove A CONTIGUOUS BLOCK of counters. Here contiguous means no empty spaces, too. I am also talking about normal play, not misere play here, so that the person who takes the last block and empties the piles, wins. I don't know a general strategy for this game. Does anyone know if it has been studied? In the particular case he plays with his friend, the initial configuration looks like: Pile 1: 1 Pile 2: 2 3 Pile 3: 4 5 6 Pile 4: 7 8 9 10 where I have numbered the counters for clarity. Pile 1 has 1 counter, on the first line. Pile 2 has 2 counters, on the second line (2 and 3), etc. So on a move you could take counters 8 and 9, leaving 7 and 10, and then on the next move the next player could take 7 or 10 but not both, since there are empty spaces left between them. It turns out that in this particular case of 10 counters there is a forced win for the 1st player, who can take either 7 8 9 10 or 8 9 on his first move. Any info about this variation? Best, Jeff Shallit
My 10-year-old son introduced me to the following variation on nim. Instead of allowing the players to take any number of counters from a pile on a turn, the counters in each pile are arranged linearly, and then you can only remove A CONTIGUOUS BLOCK of counters. Here contiguous means no empty spaces, too. I am also talking about normal play, not misere play here, so that the person who takes the last block and empties the piles, wins.
I don't know a general strategy for this game. Does anyone know if it has been studied?
this game is equivalent to nim, having the same winning positions, though it has additional winning moves. the proof is fairly easy, relying on the fact that the nim sum of two nimbers is never more than the sum of the corresponding numbers. (much) more info can be found from "winning ways" by berlekamp, conway, and guy. erich
See Winning Ways, p.114. The game is in fact one of the many disguises for Nim. You can state it as `play Nim with heaps in the usual way, but you're also allowed to split a heap when you take from it'. In Guy-Smith code it's the game .77777... In your example the ` heaps' are 1, 2, 3, 4 with nim-values (no surprise) 1, 2, 3, 4. The (only) winning moves must operate on the 4-heap -- either take the whole heap, leaving the P-position (1,2,3) or split it into two equal heaps, here possible in only one way, leaving (1,2,3,1,1). Let's do a more complicated example, say heaps (rows) of 9, 11, 14, 15 which we'll write in binary as 9 = 1 0 0 1 11 = 1 0 1 1 14 = 1 1 1 0 15 = 1 1 1 1 nim-sum 0 0 1 1 = 3 so it's an N-position and the next player should change the nim-value (i.e. the actual size in this case, since we are playing Nim in disguise) of a heap by 3. In ordinary Nim (and in the variant) we can win by taking 3 beans from the 11 or 15 heap, or 1 bean from the 14 heap. In the variant this translates into taking beans from the end of the row. Are there any other good moves? Not from the 11 heap, cos that has to go down to 8, but the 15 has to go to 12 which is also 8 + 4 or 9 + 5 (note that it's nim-addition here) so you can take 3 beans from the interior of the row to leave 8 & 4 or 4 & 8 or 1 bean to leave 9 & 5 or 5 & 9. 14 has to be reduced to 13 (14 \pm 13 = 3 in Nim) which is 8 + 5 or 9 + 4 so there are six different places in the row of 14 from which to take 1 bean & win & confuse your opponent about what strategy you're using. On Wed, 3 Jan 2007, Jeffrey Shallit wrote:
My 10-year-old son introduced me to the following variation on nim. Instead of allowing the players to take any number of counters from a pile on a turn, the counters in each pile are arranged linearly, and then you can only remove A CONTIGUOUS BLOCK of counters. Here contiguous means no empty spaces, too. I am also talking about normal play, not misere play here, so that the person who takes the last block and empties the piles, wins.
I don't know a general strategy for this game. Does anyone know if it has been studied?
In the particular case he plays with his friend, the initial configuration looks like:
Pile 1: 1 Pile 2: 2 3 Pile 3: 4 5 6 Pile 4: 7 8 9 10
where I have numbered the counters for clarity. Pile 1 has 1 counter, on the first line. Pile 2 has 2 counters, on the second line (2 and 3), etc. So on a move you could take counters 8 and 9, leaving 7 and 10, and then on the next move the next player could take 7 or 10 but not both, since there are empty spaces left between them.
It turns out that in this particular case of 10 counters there is a forced win for the 1st player, who can take either 7 8 9 10 or 8 9 on his first move.
Any info about this variation?
Best, Jeff Shallit
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Since RKG didn't say it, let me give the three-line explanation of why the option to split piles doesn't matter: In regular nim, you may change a pile of size n to one of size m for any m<n. Here you may also split it into piles of size m1, m2 with m1+m2 < n (regular addition), but these two piles are equivalent (by induction) to one pile of size m1 (+) m2 (nim-addition), which is also <n. Every move in the new game is therefore equivalent to one that was already available; you can win by simply playing nim and ignore the fact that the other player may occasionally make a move you hadn't known existed. --Michael Kleber -- It is very dark and after 2000. If you continue you are likely to be eaten by a bleen.
I'll pitch in one more detail, which is that this game is tame in misere play. This means that the misere nim strategy, which says follow the normal play strategy unless its recommended move leads to a position with heaps of size one only, carries over to this variant in misere play. Which gives me a lame excuse to mention an open algebraic problem in misere nim variants. Suppose misere nim is played with the restrictions that #1) 4k beans can never be removed from a heap, and #2) 4k+3 can be removed only if it is the whole heap Is the misere indistinguishability quotient of this game isomorphic to the following commutative monoid Q with 226 elements and the following presentation? Q = <a,b,c,d,e,f,g,h,i,j | a^2=1,b^3=b,b^2c=c,c^4=ac^3,b^2d=d,d^2=b^2,b^2e=e,c^3e=ac^2e, cde=bce,ce^2=ae^2,de^2=be^2,e^3=abe^2,b^2f=f,cf=c^2,ef=ac^2e,f^2=ac^3, b^2g=g,c^2g=ac^3d,eg=bc^2e,fg=c^3d,g^3=dg^2,b^2h=h,c^2h=be^2,eh=ae^2,fh=abe^2, g^2h=dgh,h^2=e^2,b^2i=i,c^3i=be^2,c^2ei=e^2,e^2i=abe^2,cgi=abch,hi=abfi,c^2i^2=abc^2i, ei^2=abei,fi^2=abfi,g^2i^2=e^2,i^3=abi^2,b^2j=j,cj=ci,ej=ei,fj=fi,g^2j=abgh,hj=abfi,ij=i^2,j^2=i^2>; See http://arxiv.org/abs/math.CO/0609825, section 3.6 for more Happy new year Thane On 1/3/07, Michael Kleber <michael.kleber@gmail.com> wrote:
Since RKG didn't say it, let me give the three-line explanation of why the option to split piles doesn't matter:
In regular nim, you may change a pile of size n to one of size m for any m<n. Here you may also split it into piles of size m1, m2 with m1+m2 < n (regular addition), but these two piles are equivalent (by induction) to one pile of size m1 (+) m2 (nim-addition), which is also <n. Every move in the new game is therefore equivalent to one that was already available; you can win by simply playing nim and ignore the fact that the other player may occasionally make a move you hadn't known existed.
--Michael Kleber
-- It is very dark and after 2000. If you continue you are likely to be eaten by a bleen.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Thane Plambeck tplambeck@gmail.com http://www.plambeck.org/ehome.htm
participants (5)
-
Erich Friedman -
Jeffrey Shallit -
Michael Kleber -
Richard Guy -
Thane Plambeck