There are 10 piles of coins (possibly with different amount of coins). Each of the two players can take arbitrary number of coins either from the leftmost or from the rightmost pile of coins. The one who cannot make a move loses. Is there a winning strategy for some of the player in this game?
On Nov 6, 2:31 pm, jane <jane1...@rambler.ru> wrote:
> There are 10 piles of coins (possibly with different amount of coins). Each of the two players can take arbitrary number of coins either from the leftmost or from the rightmost pile of coins. The one who cannot make a move loses. > Is there a winning strategy for some of the player in this game?
> Thanks in advance. > jane.
Yes.
All right, that is probabaly not the answer you were looking for. I am not going to give you the answer, but I will give you a technique for working out the winning strategy for many such games. I learned this from a class with Elwyn Berlekamp around 1974, and I do not know any references, but the key phrase is Sprague-Grundy number.
Every position is assigned a number which is a positive integer. The empty position, in which the player to move loses, is assigned 0. To find the number for any position, you look at every position that can be generated from the given position. Since this is an inductive, recursive sort of procedure, all of these child positions already have numbers. The current position is assigned the least integer that hasn't already been assigned to one of the child positions. Thus if the numbers of the child positions do not include 0, the given position is assigned 0. If they are, say, 0, 1, 3, 6, 7, then the given position is assigned 2.
It is easy to see that the second player to move has a winning stategy if and only if the Sprague-Grundy number of the position is 0. Figure out which positions have number 0. The strategy is then to always move so that the resulting position has SG number 0.
On Fri, 6 Nov 2009, jane wrote: > There are 10 piles of coins (possibly with different amount of coins). > Each of the two players can take arbitrary number of coins either from > the leftmost or from the rightmost pile of coins. The one who cannot > make a move loses. Is there a winning strategy for some of the player in > this game?
Likely as it appears to be a variant of Nim, which does have such.
> > There are 10 piles of coins (possibly with > different amount of coins). > > Each of the two players can take arbitrary number > of coins either from > > the leftmost or from the rightmost pile of coins. > The one who cannot > > make a move loses. Is there a winning strategy for > some of the player in > > this game?
> Likely as it appears to be a variant of Nim, which > does have such.
Yes, i also noticed that it looks similar to the game of Nim. However i don't see how to construct the table of losing and winning positions in this case. In the game of Nim there is a neat and clear strategy/answer who wins and how. However here i didn't manage to find one, that's why i am asking it here.
If somebody sees one, i would be grateful. Thanks.
> > > There are 10 piles of coins (possibly with > > different amount of coins). > > > Each of the two players can take arbitrary number > > of coins either from > > > the leftmost or from the rightmost pile of coins. > > The one who cannot > > > make a move loses. Is there a winning strategy for > > some of the player in > > > this game?
> > Likely as it appears to be a variant of Nim, which > > does have such.
> Yes, i also noticed that it looks similar to the game of Nim. However i don't see how to construct the table of losing and winning positions in this case. In the game of Nim there is a neat and clear strategy/answer who wins and how. However here i didn't manage to find one, that's why i am asking it here.
> If somebody sees one, i would be grateful. > Thanks.
Jane,
My earlier post gives an algorithm for determining which are the winning positions for any number of stacks and any number of coins. If you can program a computer, it will be an easy matter to program the Sprague-Grundy numbers for all 10-tuples (a_1. ..., a_10) where each is, say, less than 10, but certainly including 0. Keeping track of which pile is leftmost and which is rightmost makes things a little more interesting, but only a little bit. The positions whose S-G number is 0 are the winning positions for the second player, and the ones whose S-G number is larger than 0 are winning positions for the first player. Then you can hopefully pick out some sort of simple pattern. I have used this technique on many a agame, and sometimes it works like a charm. Sometimes I still can't read the pattern.
I don't have time right now to do this, but it isn't that difficult if you can both program and get your hands on a computer to use.
I am now interested in the answer as well. Any takers for the old S-G trick anywhere in this group?
In article <632452372.27941.1257546711399.JavaMail.r...@gallium.mathforum.org>,
jane <jane1...@rambler.ru> wrote: > There are 10 piles of coins (possibly with different amount of coins). Each > of the two players can take arbitrary number of coins either from the > leftmost or from the rightmost pile of coins. The one who cannot make a move > loses. > Is there a winning strategy for some of the player in this game?
You can solve this by first asking what happens if there's only 1 pile; then, what happens if there are exactly 2 piles; then, what if there are exactly 3 piles, etc.
The 2 pile case is the most important one. The 2nd player can mimic the 1st but in the other pile and win. The rest follows from that.
-- Gerry Myerson (ge...@maths.mq.edi.ai) (i -> u for email)
> In article > <632452372.27941.1257546711399.JavaMail.r...@gallium.mathforum.org>,
> jane <jane1...@rambler.ru> wrote: > > There are 10 piles of coins (possibly with different amount of coins). Each > > of the two players can take arbitrary number of coins either from the > > leftmost or from the rightmost pile of coins. The one who cannot make a move > > loses. > > Is there a winning strategy for some of the player in this game?
> You can solve this by first asking what happens > if there's only 1 pile; then, what happens if there are > exactly 2 piles; then, what if there are exactly 3 piles, > etc.
> The 2 pile case is the most important one. The 2nd player > can mimic the 1st but in the other pile and win. The rest > follows from that.
> -- > Gerry Myerson (ge...@maths.mq.edi.ai) (i -> u for email)
Suppose the leftmost pile has 1 coin and the rightmost pile has 9 coins. The first player removes 1 coin from the rightmost pile. How does the second player mimic that?
I must see that I missed that only the outside piles can be removed from. This makes the analysis I described in detail in my first post rather easier that I thought, so perhaps I will get to it.
> On Nov 8, 5:45 pm, Gerry Myerson <ge...@maths.mq.edi.ai.i2u4email> > wrote: > > In article > > <632452372.27941.1257546711399.JavaMail.r...@gallium.mathforum.org>,
> > jane <jane1...@rambler.ru> wrote: > > > There are 10 piles of coins (possibly with different amount of coins). > > > Each > > > of the two players can take arbitrary number of coins either from the > > > leftmost or from the rightmost pile of coins. The one who cannot make a > > > move > > > loses. > > > Is there a winning strategy for some of the player in this game?
> > You can solve this by first asking what happens > > if there's only 1 pile; then, what happens if there are > > exactly 2 piles; then, what if there are exactly 3 piles, > > etc.
> > The 2 pile case is the most important one. The 2nd player > > can mimic the 1st but in the other pile and win. The rest > > follows from that.
> > -- > > Gerry Myerson (ge...@maths.mq.edi.ai) (i -> u for email)
> Suppose the leftmost pile has 1 coin and the rightmost pile has 9 > coins. The first player removes 1 coin from the rightmost pile. How > does the second player mimic that?
Perhaps "mimic" wasn't the best word; she acts so as to make the two piles have the same number of coins. In this case, she removes 7 coins from the rightmost pile, leaving both outside piles with 1 coin.
-- Gerry Myerson (ge...@maths.mq.edi.ai) (i -> u for email)
> In article > <556ee733-9478-4e43-b8c4-cbcaa979b...@r24g2000prf.googlegroups.com>, > "Achava Nakhash, the Loving Snake" <ach...@hotmail.com> wrote:
> > On Nov 8, 5:45 pm, Gerry Myerson <ge...@maths.mq.edi.ai.i2u4email> > > wrote: > > > In article > > > <632452372.27941.1257546711399.JavaMail.r...@gallium.mathforum.org>,
> > > jane <jane1...@rambler.ru> wrote: > > > > There are 10 piles of coins (possibly with different amount of coins). > > > > Each > > > > of the two players can take arbitrary number of coins either from the > > > > leftmost or from the rightmost pile of coins. The one who cannot make a > > > > move > > > > loses. > > > > Is there a winning strategy for some of the player in this game?
> > > You can solve this by first asking what happens > > > if there's only 1 pile; then, what happens if there are > > > exactly 2 piles; then, what if there are exactly 3 piles, > > > etc.
> > > The 2 pile case is the most important one. The 2nd player > > > can mimic the 1st but in the other pile and win. The rest > > > follows from that.
> > > -- > > > Gerry Myerson (ge...@maths.mq.edi.ai) (i -> u for email)
> > Suppose the leftmost pile has 1 coin and the rightmost pile has 9 > > coins. The first player removes 1 coin from the rightmost pile. How > > does the second player mimic that?
> Perhaps "mimic" wasn't the best word; she acts so as to make > the two piles have the same number of coins. In this case, she > removes 7 coins from the rightmost pile, leaving both outside > piles with 1 coin.
Note that if the original number of piles is odd rather than even, the first player has a winning strategy.
Gerry Myerson wrote: > In article > <632452372.27941.1257546711399.JavaMail.r...@gallium.mathforum.org>, > jane <jane1...@rambler.ru> wrote:
>> There are 10 piles of coins (possibly with different amount of coins). Each >> of the two players can take arbitrary number of coins either from the >> leftmost or from the rightmost pile of coins. The one who cannot make a move >> loses. >> Is there a winning strategy for some of the player in this game?
> You can solve this by first asking what happens > if there's only 1 pile; then, what happens if there are > exactly 2 piles; then, what if there are exactly 3 piles, > etc.
> The 2 pile case is the most important one. The 2nd player > can mimic the 1st but in the other pile and win. The rest > follows from that.
Perhaps a bit clearer: The 2 pile Nym game has two variants: 1) the player who takes the last coin wins 2) the player who takes the last coin loses Once you know the winning strategy for both variants, the solution for your game becomes easy.
Hints: Variant 1): make sure that n=m after your move. Variant 2): if n,m >= 2, then make sure that n=m after your move; if n = 1, remove the other pile.
> In article <gerry-0A8F9C.16350309112...@feeder.eternal-september.org>, > Gerry Myerson <ge...@maths.mq.edi.ai.i2u4email> wrote:
> > In article > > <556ee733-9478-4e43-b8c4-cbcaa979b...@r24g2000prf.googlegroups.com>, > > "Achava Nakhash, the Loving Snake" <ach...@hotmail.com> wrote:
> > > On Nov 8, 5:45 pm, Gerry Myerson <ge...@maths.mq.edi.ai.i2u4email> > > > wrote: > > > > In article > > > > <632452372.27941.1257546711399.JavaMail.r...@gallium.mathforum.org>,
> > > > jane <jane1...@rambler.ru> wrote: > > > > > There are 10 piles of coins (possibly with different amount of coins). > > > > > Each > > > > > of the two players can take arbitrary number of coins either from the > > > > > leftmost or from the rightmost pile of coins. The one who cannot make a > > > > > move > > > > > loses. > > > > > Is there a winning strategy for some of the player in this game?
> > > > You can solve this by first asking what happens > > > > if there's only 1 pile; then, what happens if there are > > > > exactly 2 piles; then, what if there are exactly 3 piles, > > > > etc.
> > > > The 2 pile case is the most important one. The 2nd player > > > > can mimic the 1st but in the other pile and win. The rest > > > > follows from that.
> > > > -- > > > > Gerry Myerson (ge...@maths.mq.edi.ai) (i -> u for email)
> > > Suppose the leftmost pile has 1 coin and the rightmost pile has 9 > > > coins. The first player removes 1 coin from the rightmost pile. How > > > does the second player mimic that?
> > Perhaps "mimic" wasn't the best word; she acts so as to make > > the two piles have the same number of coins. In this case, she > > removes 7 coins from the rightmost pile, leaving both outside > > piles with 1 coin.
> Note that if the original number of piles is odd rather than even, the > first player has a winning strategy.
Gerry, I see your point, and of course that is right for the 2 pile game which is just Nim, but even 3 piles is unclear to me, although I doubt it it would be too hard to figure out given the 2 pile soluton.
Virgil, I simply don't get the winning strategy for the first player if the number of piles is odd. I can see a promising approach to the 3 pile game, and perhaps it is that it is 2:44AM here and I should be asleep in bed instead of on my feet, but I would appreciate a few details about the winning strategy you have in mind.
> Gerry Myerson wrote: > > In article > > <632452372.27941.1257546711399.JavaMail.r...@gallium.mathforum.org>, > > jane <jane1...@rambler.ru> wrote:
> >> There are 10 piles of coins (possibly with different amount of coins). Each > >> of the two players can take arbitrary number of coins either from the > >> leftmost or from the rightmost pile of coins. The one who cannot make a move > >> loses. > >> Is there a winning strategy for some of the player in this game?
> > You can solve this by first asking what happens > > if there's only 1 pile; then, what happens if there are > > exactly 2 piles; then, what if there are exactly 3 piles, > > etc.
> > The 2 pile case is the most important one. The 2nd player > > can mimic the 1st but in the other pile and win. The rest > > follows from that.
> Perhaps a bit clearer: > The 2 pile Nym game has two variants: > 1) the player who takes the last coin wins > 2) the player who takes the last coin loses > Once you know the winning strategy for both variants, the solution for > your game becomes easy.
> Hints: > Variant 1): make sure that n=m after your move. > Variant 2): if n,m >= 2, then make sure that n=m after your move; > if n = 1, remove the other pile.
Yes, this is much better than what I wrote, as I overlooked some of the subtleties. -- GM
This is a really interesing variant. Consider the games {1,2,2} and {2,1,2}. In ordinary nim these are the same game and the first player has a win by removing the pile with one coin. But in this variant, the middle pile cannot be touched, and these are two distinct games. {1,2,2} is still a win for player 1, but with the one coin pile on the inside, {2,1,2} is a win for player 2. No matter what player 1 does, player 2 can force {1,1}, a win for him.
In general {x,y,x} with y>x is a win for player 2, {x,x,x} is a win for player 1. {y,x,y} with y>x is trickier. If a player reduces either outside pile to exactly x, he will lose, but otherwise looks trickier to evaluate.
Take the game {3,2,3}, so far the only move which player 1 can make and not lose is to reduce 3 to 1: {3,2,1}. Then player 2 wants to avoid {1,2,1}, {2,2,1}, {0,2,1}, and {3,2,0}. But those are his available moves, so he will lose.
I don't know how {4,2,4} might play out, the increase from 3 to 4 leaves some room between the sizes of the outside piles and the center pile.
Brian S wrote: > This is a really interesing variant. Consider the games {1,2,2} and > {2,1,2}. In ordinary nim these are the same game and the first player > has a win by removing the pile with one coin. But in this variant, > the middle pile cannot be touched, and these are two distinct games. > {1,2,2} is still a win for player 1, but with the one coin pile on the > inside, {2,1,2} is a win for player 2. No matter what player 1 does, > player 2 can force {1,1}, a win for him.
> In general {x,y,x} with y>x is a win for player 2, {x,x,x} is a win > for player 1. {y,x,y} with y>x is trickier. If a player reduces > either outside pile to exactly x, he will lose, but otherwise looks > trickier to evaluate.
> Take the game {3,2,3}, so far the only move which player 1 can make > and not lose is to reduce 3 to 1: {3,2,1}. Then player 2 wants to > avoid {1,2,1}, {2,2,1}, {0,2,1}, and {3,2,0}. But those are his > available moves, so he will lose.
> I don't know how {4,2,4} might play out, the increase from 3 to 4 > leaves some room between the sizes of the outside piles and the center > pile.
The game {4,2,4} is lost for the starting player, as is easy to see.
The game is basically a sequence of 2-pile Nim games, played one after another (first with the outer two piles, then with the two piles 'just inwards these', etc. (If the number of piles is odd, there remains only one pile in the end, but this is equivalent to a game with two piles containing 0 and n.)
Next you note that in a 2-pile Nim game, there is a strategy to take the last coin yourself, and another one to force the other player to take the last coin. So, in a sequence, you can manipulate who starts the next 2-pile-Nim-game, so to speak.
For example, in a game with piles p1, ..., p7, you first determine whether the game with p2, ..., p6 is won by the starting player or by the other, and when playing the p1,p7 Nim game, you manipulate the right player into the starting position of the p2, ..., p6 game.
The winning conditions are easy to understand, but perhaps a bit tedious to write down. But, as Gerry said, once you understand the 2-pile Nim game, you know everything there is to know.
> On Nov 8, 9:20 pm, Virgil <Vir...@home.esc> wrote: >> In article <gerry-0A8F9C.16350309112...@feeder.eternal-september.org>, >> Gerry Myerson <ge...@maths.mq.edi.ai.i2u4email> wrote:
>>> In article >>> <556ee733-9478-4e43-b8c4-cbcaa979b...@r24g2000prf.googlegroups.com>, >>> "Achava Nakhash, the Loving Snake" <ach...@hotmail.com> wrote: >>>> On Nov 8, 5:45 pm, Gerry Myerson <ge...@maths.mq.edi.ai.i2u4email> >>>> wrote: >>>>> In article >>>>> <632452372.27941.1257546711399.JavaMail.r...@gallium.mathforum.org>, >>>>> jane <jane1...@rambler.ru> wrote: >>>>>> There are 10 piles of coins (possibly with different amount of coins). >>>>>> Each >>>>>> of the two players can take arbitrary number of coins either from the >>>>>> leftmost or from the rightmost pile of coins. The one who cannot make a >>>>>> move >>>>>> loses. >>>>>> Is there a winning strategy for some of the player in this game? >>>>> You can solve this by first asking what happens >>>>> if there's only 1 pile; then, what happens if there are >>>>> exactly 2 piles; then, what if there are exactly 3 piles, >>>>> etc. >>>>> The 2 pile case is the most important one. The 2nd player >>>>> can mimic the 1st but in the other pile and win. The rest >>>>> follows from that. >>>>> -- >>>>> Gerry Myerson (ge...@maths.mq.edi.ai) (i -> u for email) >>>> Suppose the leftmost pile has 1 coin and the rightmost pile has 9 >>>> coins. The first player removes 1 coin from the rightmost pile. How >>>> does the second player mimic that? >>> Perhaps "mimic" wasn't the best word; she acts so as to make >>> the two piles have the same number of coins. In this case, she >>> removes 7 coins from the rightmost pile, leaving both outside >>> piles with 1 coin. >> Note that if the original number of piles is odd rather than even, the >> first player has a winning strategy.
> Gerry, I see your point, and of course that is right for the 2 pile > game which is just Nim, but even 3 piles is unclear to me, although I > doubt it it would be too hard to figure out given the 2 pile soluton.
It escapes me what Virgil had in mind; the game with piles [3, 7, 3] is lost to the starting player.
Herman Jurjus wrote: > Brian S wrote: >> This is a really interesing variant. Consider the games {1,2,2} and >> {2,1,2}. In ordinary nim these are the same game and the first player >> has a win by removing the pile with one coin. But in this variant, >> the middle pile cannot be touched, and these are two distinct games. >> {1,2,2} is still a win for player 1, but with the one coin pile on the >> inside, {2,1,2} is a win for player 2. No matter what player 1 does, >> player 2 can force {1,1}, a win for him.
>> In general {x,y,x} with y>x is a win for player 2, {x,x,x} is a win >> for player 1. {y,x,y} with y>x is trickier. If a player reduces >> either outside pile to exactly x, he will lose, but otherwise looks >> trickier to evaluate.
>> Take the game {3,2,3}, so far the only move which player 1 can make >> and not lose is to reduce 3 to 1: {3,2,1}. Then player 2 wants to >> avoid {1,2,1}, {2,2,1}, {0,2,1}, and {3,2,0}. But those are his >> available moves, so he will lose.
>> I don't know how {4,2,4} might play out, the increase from 3 to 4 >> leaves some room between the sizes of the outside piles and the center >> pile.
> The game {4,2,4} is lost for the starting player, as is easy to see.
> The game is basically a sequence of 2-pile Nim games, played one after > another...
No, this is not true, sorry. For example, in the {4, 2, 5} game, if the first player removes all 4 coins from the first pile, then the second player is not forced to take coins away from the pile with 5 coins, but can now also take coins from the pile with 2 coins.
<ach...@hotmail.com> wrote: > On Nov 6, 2:31 pm, jane <jane1...@rambler.ru> wrote:
> > There are 10 piles of coins (possibly with different amount of coins). Each of the two players can take arbitrary number of coins either from the leftmost or from the rightmost pile of coins. The one who cannot make a move loses. > > Is there a winning strategy for some of the player in this game?
> > Thanks in advance. > > jane.
> Yes.
> All right, that is probabaly not the answer you were looking for. I > am not going to give you the answer, but I will give you a technique > for working out the winning strategy for many such games. I learned > this from a class with Elwyn Berlekamp around 1974, and I do not know > any references, but the key phrase is Sprague-Grundy number.
> Every position is assigned a number which is a positive integer. The > empty position, in which the player to move loses, is assigned 0. To > find the number for any position, you look at every position that can > be generated from the given position. Since this is an inductive, > recursive sort of procedure, all of these child positions already > have numbers. The current position is assigned the least integer that > hasn't already been assigned to one of the child positions. Thus if > the numbers of the child positions do not include 0, the given > position is assigned 0. If they are, say, 0, 1, 3, 6, 7, then the > given position is assigned 2.
> It is easy to see that the second player to move has a winning stategy > if and only if the Sprague-Grundy number of the position is 0. Figure > out which positions have number 0. The strategy is then to always > move so that the resulting position has SG number 0.
> Good luck!
> Regards, > Achava
I coded up this S-G trick in the expectation that a simple pattern would emerge for positions with S-G number 0 (i.e., those that lose for whoever has to play).
For the case of two and three piles, the losing positions may be written xx and xyx, respectively, where different variables are understood to take different values.
For four piles, the situation is more complicated. Here are the six losing cases:
1) xxxx 2) xyyx 3) xxyy with |x-y| = 1 4) xyzx with y,z < x, or y,z > x 5) xxyz or zyxx with y < z = x-1 or y > z = x+1 6) xyzw with (y < x < w < z or y > x > w > z) and |x-w| = 1
For example, when up to six coins are allowed in each pile, here is a list of the positions with S-G number 0 (where each string is put into canonical form by selecting it or its reverse, whichever is smaller). You can verify that these strings are exactly the subset of all possible strings which fall into one of the above six cases. (I've also checked this for a maximum of k coins for k = 4 to 13.)
> On Nov 6, 9:04 pm, "Achava Nakhash, the Loving Snake"
> <ach...@hotmail.com> wrote: > > On Nov 6, 2:31 pm, jane <jane1...@rambler.ru> wrote:
> > > There are 10 piles of coins (possibly with different amount of coins). Each of the two players can take arbitrary number of coins either from the leftmost or from the rightmost pile of coins. The one who cannot make a move loses. > > > Is there a winning strategy for some of the player in this game?
> > > Thanks in advance. > > > jane.
> > Yes.
> > All right, that is probabaly not the answer you were looking for. I > > am not going to give you the answer, but I will give you a technique > > for working out the winning strategy for many such games. I learned > > this from a class with Elwyn Berlekamp around 1974, and I do not know > > any references, but the key phrase is Sprague-Grundy number.
> > Every position is assigned a number which is a positive integer. The > > empty position, in which the player to move loses, is assigned 0. To > > find the number for any position, you look at every position that can > > be generated from the given position. Since this is an inductive, > > recursive sort of procedure, all of these child positions already > > have numbers. The current position is assigned the least integer that > > hasn't already been assigned to one of the child positions. Thus if > > the numbers of the child positions do not include 0, the given > > position is assigned 0. If they are, say, 0, 1, 3, 6, 7, then the > > given position is assigned 2.
> > It is easy to see that the second player to move has a winning stategy > > if and only if the Sprague-Grundy number of the position is 0. Figure > > out which positions have number 0. The strategy is then to always > > move so that the resulting position has SG number 0.
> > Good luck!
> > Regards, > > Achava
> I coded up this S-G trick in the expectation that a simple pattern > would emerge for positions with S-G number 0 (i.e., those that lose > for whoever has to play).
> For the case of two and three piles, the losing positions may be > written xx and xyx, respectively, where different variables are > understood to take different values.
> For four piles, the situation is more complicated. Here are the > six losing cases:
> 1) xxxx > 2) xyyx > 3) xxyy with |x-y| = 1 > 4) xyzx with y,z < x, or y,z > x > 5) xxyz or zyxx with y < z = x-1 or y > z = x+1 > 6) xyzw with (y < x < w < z or y > x > w > z) and |x-w| = 1
I was unable to do anything useful with the S-G number itself, as opposed to just computing whether positions were winning (S-G number non-zero) or losing (S-G number zero).
Here are some more observations about losing positions -- all conjectures based on numerical experimentation:
a) In the four-pile case, the above characterization of losing positions can be simplified to the following. Let the position be denoted abcd (with a,b,c,d any positive integers). Then abcd is a losing position iff
(|d-a| = 0 and sgn(b-a) = sgn(c-a)) or (|d-a| = 1 and sgn(b-a) != sgn(c-b) = sgn(d-a) != sgn(d-c))
Here sgn(x) = -1 if x < 0, 0 if x = 0, and 1 if x > 0. |d-a| = 1 case looks a little complicated, but all it says is that if a < d, then a >= b < c >= d, and if a > d, we reverse these inequalities (a <= b > c <= d).
b) Numerical experimentation shows that a (necessary, but not sufficient) property of losing positions is that the difference in the number of coins in their end piles is 0 or 1.
c) If we consider the k^n cases of n piles with 1 to k coins in each, then the number of these cases which are losing is (k^n + (-1)^n k)/(k + 1). For n >= 4, we may subdivide the losing positions into cases with end piles differing by 0 or 1 coin. As k -> infinity the 0 case outnumbers the 1 case by 2:1 for any n >= 4. For finite k, the exact counts seem to be
((2k+1)k^n-(-1)^n k^2((n-2)k^2-k-n))/(3k(k+1)) with diff = 0, (k-1)(k^n+(-1)^n k^2((n-2)k -3+n))/(3k(k+1)) with diff = 1,
> <ach...@hotmail.com> wrote: > > On Nov 6, 2:31 pm, jane <jane1...@rambler.ru> wrote:
> > > There are 10 piles of coins (possibly with different amount of coins). Each of the two players can take arbitrary number of coins either from the leftmost or from the rightmost pile of coins. The one who cannot make a move loses. > > > Is there a winning strategy for some of the player in this game?
> > > Thanks in advance. > > > jane.
>> I coded up this S-G trick in the expectation that a simple pattern > would emerge for positions with S-G number 0 (i.e., those that lose > for whoever has to play).
> For the case of two and three piles, the losing positions may be > written xx and xyx, respectively, where different variables are > understood to take different values.
I am delighted that someone has taken my suggestion and coded up the SG-number algorithm for this very interesting game. I was getting interested enough to do it myself, but lack of time and energy got in my way as usual. I used to be able to do this kind of thing after hours at work, but haven't been able to do that for a while, and my compiler seems to have vanished from my home PC. I never believed those who regarded this game a sequence of 2-pile Nim games, and that opinion seems to have been retracted.
You probably know this, but your work gives a perfect strategy for both players. If the game has 3 piles and you are in a losing position, make any move, as you will lose against perfect play anyway. If you are not in a losing position, there is always a move that transitions to a losing position (that is immediate from the definintion of the SG-number) and then it is a losing position for your opponent.
For 3 piles, starting with (1,1,1) you have no choicee of moves at any point. You just win. Otherwise we have xyz with x != z. If x = y, remove all of the z pile. Then play symmetically, keeping the 2 piles equal in length. Similarly if y = z remove the entire x pile and then play symeetircall. Otherwise, play so as to make the two outer piles equal in size. Notice that it is not possible at this point to have all three piles the same size. If at any point your opponent removes the last coin from either of the outer piles, your remaining moves are always to equalize to the size of the two remaining piles.
> For four piles, the situation is more complicated. Here are the > six losing cases:
> 1) xxxx > 2) xyyx > 3) xxyy with |x-y| = 1 > 4) xyzx with y,z < x, or y,z > x > 5) xxyz or zyxx with y < z = x-1 or y > z = x+1 > 6) xyzw with (y < x < w < z or y > x > w > z) and |x-w| = 1
For 4 piles, the situation is obviously more complicated to describe, but still very easy to implement.
You implied that no simple pattern has emerged. You have certainly presented a reasonably simple pattern, at least for 3 and 4 piles. I suspect that the solution for 5 piles will be the hint required to work out the general game. You don't actually need all of the S-G numbers to work out the perfect strategy. You just need to know which ones are 0 and which ones aren't. In the class during which I learned this stuff, we were asked to prove that the well-known strategy for Nim actually was a perfect strategy, and also to figure out, with proofs, the strategy for several interesting variations of Nim. I didn't have a lot of trouble doing this, as I recall, and it wouldn't surprise me overly if something similar could be done here once the pattern was somewhat clear, as you have made it.
One thing I forgot to mention is that if a game consists of subgames that are independent, which is to say that moves in one of them don't depend in any way upon moves done in the others (not the case here, also), then the S-G number of a postion is the "Nim sum" of the numbers of the subpositions. The Nim sum of a and b, which I will write a & b, mostly because I have to come up with some symbol, is the sum without carries of the binary representations of a and b considered again as the binary representation of the a number. Clearly a & a = 0 for all a (we need non-negative a and b for this definition), 4 & 5 = 1, 3 + 7 = 3, etc. Nim itself consists of independent columns, so the S-G number of a Nim position is just the Nim sum of the size of each column (this adddition is obviously associative). Armed with this theorem, working out the perfect strategy for Nim is a triviality.
I am actually motiviated to find my CD's for the C++ compiler I got in 1999 or thereabouts. If I can find it I will probably do a little work on this game, myself.
On Nov 7, 9:04 am, "Achava Nakhash, the Loving Snake"
<ach...@hotmail.com> wrote: > On Nov 6, 2:31 pm, jane <jane1...@rambler.ru> wrote:
> > There are 10 piles of coins (possibly with different amount of coins). > > Each of the two players can take arbitrary number of coins either from the leftmost > > or from the rightmost pile of coins. The one who cannot make a move loses. > > Is there a winning strategy for some of the player in this game?
I want to make three comments, each unrelated to the other questions, and pose a question.
> ... the key phrase is Sprague-Grundy number. > [discussion snipped]
Comment 1. The Loving Snake's algorithm works, but works even when all non-zero "Sprague-Grundy" numbers are replaced with 1! In other words you just need a win/loss bit, not a "Sprague-Grundy" number. The more elaborate procedure is used, I think, to simplify a game expressed as a sum of games, but I don't see an easy way to express jane's game in that fashion.
Comment 2. With, say 10 piles of 10 coins each, the obvious way to define a computer database of prior results would be as a 10x10x10x10x10x10x10x10x10x10 array. Unfortunately that would be too large even on many modern machines. Fortunately the rules prevent most such coin arrangements from arising, so a much smaller *sparse* array would suffice.
I solved a similar game and placed the source code on my website http://james.fabpedigree.com/wnim.htm To solve jane's game it will probably be best to code from scratch, but you still may be amused to examine my program. I think it deserves some "Worst of [something]" prize, even though it was *not* intended as an Obfuscated C submission!
> > Is there a winning strategy for some of the player in this game?
Comment 3.
As Achava points out, since there are only finitely many moves at a turn, and the game terminates after finite moves, and draws are impossible, *yes* there certainly *is* a winning strategy for one player or the other!
Since this is sci.math, one wonders what the answer would be for games with the finitude restrictions were removed. This is discussed somewhat at http://en.wikipedia.org/wiki/Axiom_of_determinacy with the curious (but relatively easy to prove) result that certain games that *seem* like they *should* have winning strategies lack such strategies *if* the Axiom of Choice is true.
Question. The Axiom of Choice seems to lead to "unbelievable" paradoxical results: this one from game theory, and the Banach-Tarski Theorem. What do mathematicians think of this? Is the Axiom of Choice "false" after all, or would most mathematicians consider it silly to pose such a question?
> On Nov 7, 9:04 am, "Achava Nakhash, the Loving Snake"
> <ach...@hotmail.com> wrote: > > On Nov 6, 2:31 pm, jane <jane1...@rambler.ru> wrote:
> > > There are 10 piles of coins (possibly with different amount of coins). > > > Each of the two players can take arbitrary number of coins either from the leftmost > > > or from the rightmost pile of coins. The one who cannot make a move loses. > > > Is there a winning strategy for some of the player in this game?
> I want to make three comments, each unrelated to the other questions, > and pose a question.
> > ... the key phrase is Sprague-Grundy number. > > [discussion snipped]
> Comment 1. The Loving Snake's algorithm works, but works even when > all non-zero > "Sprague-Grundy" numbers are replaced with 1! In other words you just > need a win/loss bit, not a "Sprague-Grundy" number. The more > elaborate > procedure is used, I think, to simplify a game expressed as a sum of > games, > but I don't see an easy way to express jane's game in that fashion.
It is true that determining the winning strategy from the Sprague- Grundy numbers requires only knowning whether they are 1 or 0. I say that implicitly when describing the 3-pile game in terms of winning and losing positions. The Sprague-Grundy number is calculated in a recursive fashion, and I believe that you are correct in saying that you really don't need the number to determine the winning and losing positions. You simply need to know whether the child positions are winning and losing positions, which is to say the S-G number is either greater than 0 or equal to 0. It is, as you say, also useful to simplify games that decompose into sums of games. That being said, I suspect that it is also useful in understanding the structure of the game, but I haven't thought about these issues in many, many years.
> Comment 2. With, say 10 piles of 10 coins each, the obvious way > to define a computer database of prior results would be as a > 10x10x10x10x10x10x10x10x10x10 array. Unfortunately that would be > too large even on many modern machines. Fortunately the rules > prevent most such coin arrangements from arising, so a much > smaller *sparse* array would suffice.
> I solved a similar game and placed the source code on my website > http://james.fabpedigree.com/wnim.htm > To solve jane's game it will probably be best to code from scratch, > but you still may be amused to examine my program. I think > it deserves some "Worst of [something]" prize, even though > it was *not* intended as an Obfuscated C submission!
Yes, the 10-pile game is probably problematic for solution on a computer, even as good as they are. I think that the better approach in this case is probably to use the computer to solve the 5 and maybe 6-pile game. Then try to prove the likely generalizations.
> > > Is there a winning strategy for some of the player in this game?
> Comment 3.
> As Achava points out, since there are only finitely many moves at > a turn, and the game terminates after finite moves, and draws are > impossible, *yes* there certainly *is* a winning strategy for > one player or the other!
> Since this is sci.math, one wonders what the answer would be > for games with the finitude restrictions were removed. > This is discussed somewhat at > http://en.wikipedia.org/wiki/Axiom_of_determinacy > with the curious (but relatively easy to prove) result that > certain games that *seem* like they *should* have winning > strategies lack such strategies *if* the Axiom of Choice > is true.
> Question. The Axiom of Choice seems to lead to "unbelievable" > paradoxical results: this one from game theory, and > the Banach-Tarski Theorem. What do mathematicians think > of this? Is the Axiom of Choice "false" after all, or > would most mathematicians consider it silly to pose such a > question?
> James Dow Allen
I can only speak with complete accuracy for one mathematician, myself back in the days when I was a mathematician. I used to talk about these with my friends who were also undergraduate math majors and those with whom I went to graduate school. My friends and I regarded the axiom of choice as obviously true. We read that some people found the well-ordering theorem, particulary the well-ordering of the reals, paradoxical and Zorn's lemma too complicated to have any reasonable intuition about. I did not find the well-ordering of the reals to be any problem at all. It is true, of course, that the natural ordering on the reals is not a well-ordering, but so what? Consider simply as a large bunch of elements, why shouldn't they be well-ordered. Everyone I talked to thought that the Banach-Tarski paradox was cool, not that it was a problem. It violates our sense of volume - even our sense of measure, but since the shape is decomoposed into non- measurable sets, the problem with the intuition goes away in a way that I find totally nonproblematical.
On Nov 11, 7:11 pm, "Achava Nakhash, the Loving Snake"
<ach...@hotmail.com> wrote: > You implied that no simple pattern has emerged. You have certainly > presented a reasonably simple pattern, at least for 3 and 4 piles. I > suspect that the solution for 5 piles will be the hint required to > work out the general game.
Okay, the patterns of losing positions for 0 through 5 piles are given below. Here's how to interpret the notation:
1) The pattern xyzzy, for example, means piles of x, y, z, z, and then y coins, with x, y, and z all unequal, or the *reverse* of this (e.g., both 32442 and 24423 fit the pattern xyzzy).
2) It is implicitly assumed that the difference between the first and last pile is at most 1. This makes no difference to patterns beginning and ending in x, of course, but for xyzzy, 24334 would *not* fit the pattern due to this implicit restriction.
3) Additional restrictions are given using notation such as [y,x,z,w], which means that either y < x < z < w or w < z < x < y. The logical operations Not (denoted ~) and Or (denoted ||) are also used. E.g., "xyzzy, ~[y,x,z]" would match 32112, but not 32442.
Here, then, is a complete specification of the positions that lose for whoever must play next, for up to 5 piles. The non-trivial cases (4 and 5 piles) were cut and pasted (with minor cosmetic edits) from the program that checked their validity, so transcription error is not an issue. This program computed the S-G number (well, whether it is 0 or not, actually) for all positions with at most k coins per pile and verified that those and only those positions specified by the patterns below have S-G number 0. This check was conducted for 4 piles of up to 24 coins each and 5 piles of up to 12 coins each.
0 piles: all 1 pile: none 2 piles: xx 3 piles: xyx
On Nov 6, 5:31 pm, jane <jane1...@rambler.ru> wrote:
> There are 10 piles of coins (possibly with different amount of coins). Each of the two players can take arbitrary number of coins either from the leftmost or from the rightmost pile of coins. The one who cannot make a move loses. > Is there a winning strategy for some of the player in this game?
> On Nov 6, 5:31 pm, jane <jane1...@rambler.ru> wrote:
> > There are 10 piles of coins (possibly with different amount of coins). Each of the two players can take arbitrary number of coins either from the leftmost or from the rightmost pile of coins. The one who cannot make a move loses. > > Is there a winning strategy for some of the player in this game?
> The algorithm for winning play is simple, although > Lorraine the forklift driver apparently requires a > visual aid to execute it.
Here is a description of Lorraine's algorithm for determining if a position is "in P" (i.e., it wins for the previous player, but loses for the next player). I've put it in my own words, and I don't rely on Lorraine's diagram.
-----
A position with n >= 0 piles with equal numbers of coins is in P if and only if n is even.
The remaining cases have at least two different pile sizes occurring. Tentatively call an end "low" (or "high") if it is lower (or higher) than the next different pile: e.g., in the position 4451131222, the left end looks "low" (4 < 5) and the right end "high" (2 > 1). However, if the number of same piles at an end is odd, we flip our decision: the left end stays low (there are an even number of 4's), but the right end flips from high to low (yes, it's *odd* to flip, but there are an *odd* number of 2's).
The position is in P if and only if the "ascents" agree. These are the (signed) differences between the ends. One ascent uses the values "high" = 1 and "low" = 0. The other uses the actual numbers of coins in the end piles. In the case 4451131222 the ascents are
"low" - "low" = 0 - 0 = 0, and 2 - 4 = -2,
so 4451131222 is not in P.
-----
Note 1: because the "high"/"low" version of ascent can only take the values -1, 0, and 1, it is necessary for the end piles to differ by at most 1 to be in P.
Note 2: I've used the convention "right end minus left end". Left minus right is fine too, but both ascents must use the same convention, of course.
Note 3: So, to win this game, determine if your position is in P. If not, great! Find a move that puts it in P. For 4451131222, the winning move is to take one from the left end: 3451131222 (low/high -> flip/flip -> high/low, low-high = -1 = 2-3)
Here is a Mathematica implementation:
(* Determines whether a list of positive integers is a losing position for the next player *)
lQ[p_] := Module[{s = Split[p], x, a, b, y, ex, ey}, If[Length[s] <= 1, EvenQ[Length[p]], {x, a, b, y} = s[[{1, 2, -2, -1}, 1]]; ex = If[Xor[x < a, OddQ[Length[s[[ 1]]]]], 0, 1]; ey = If[Xor[y < b, OddQ[Length[s[[-1]]]]], 0, 1]; y - x == ey - ex]];
Here's some auxiliary code to compute moves:
(* Returns list of some next positions: taking some of a pile to leave a difference between end piles of at most 1, or taking all of a pile *)
Jim Ferry wrote: > On Nov 13, 12:31 am, Jim Ferry <corkleb...@hotmail.com> wrote: >> On Nov 6, 5:31 pm, jane <jane1...@rambler.ru> wrote:
>>> There are 10 piles of coins (possibly with different amount of coins). Each of the two players can take arbitrary number of coins either from the leftmost or from the rightmost pile of coins. The one who cannot make a move loses. >>> Is there a winning strategy for some of the player in this game? >>> Thanks in advance. >>> jane. >> The solution to this problem is given in >> M. Albert and R. Nowakowski, The Game of End-Nim, Electr. J. Comb., >> 2001 >> which is freely available here:http://www.emis.de/journals/EJC/Volume_8/PDF/v8i2r1.pdf
>> The algorithm for winning play is simple, although >> Lorraine the forklift driver apparently requires a >> visual aid to execute it.
|
