 |
|
| Science Forum Index » Mathematics Forum » Game with coins... |
|
Page 1 of 2 Goto page 1, 2 Next |
|
| Author |
Message |
| jane... |
 Posted: Fri Nov 06, 2009 12:31 pm |
|
|
|
Guest
|
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. |
|
|
| Back to top |
|
|
|
| Achava Nakhash, the Loving Snake... |
| Posted: Fri Nov 06, 2009 4:04 pm |
|
|
|
Guest
|
On Nov 6, 2:31 pm, jane <jane1... at (no spam) rambler.ru> wrote:
[quote]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.
[/quote]
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 |
|
|
| Back to top |
|
|
|
| William Elliot... |
| Posted: Sat Nov 07, 2009 8:03 am |
|
|
|
Guest
|
On Fri, 6 Nov 2009, jane wrote:
[quote]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.[/quote] |
|
|
| Back to top |
|
|
|
| jane... |
| Posted: Sat Nov 07, 2009 8:07 am |
|
|
|
Guest
|
[quote]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.
[/quote]
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. |
|
|
| Back to top |
|
|
|
| Achava Nakhash, the Loving Snake... |
| Posted: Sun Nov 08, 2009 2:41 pm |
|
|
|
Guest
|
On Nov 7, 10:07 am, jane <jane1... at (no spam) rambler.ru> wrote:
[quote]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.
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.
[/quote]
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?
Regards,
Achava |
|
|
| Back to top |
|
|
|
| Achava Nakhash, the Loving Snake... |
| Posted: Sun Nov 08, 2009 5:22 pm |
|
|
|
Guest
|
On Nov 8, 5:45 pm, Gerry Myerson <ge... at (no spam) maths.mq.edi.ai.i2u4email>
wrote:
[quote]In article
632452372.27941.1257546711399.JavaMail.r... at (no spam) gallium.mathforum.org>,
jane <jane1... at (no spam) 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... at (no spam) maths.mq.edi.ai) (i -> u for email)
[/quote]
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.
Regards,
Achava |
|
|
| Back to top |
|
|
|
| Gerry Myerson... |
| Posted: Sun Nov 08, 2009 8:45 pm |
|
|
|
Guest
|
In article
<632452372.27941.1257546711399.JavaMail.root at (no spam) gallium.mathforum.org>,
jane <jane1806 at (no spam) rambler.ru> wrote:
[quote]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?
[/quote]
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 (gerry at (no spam) maths.mq.edi.ai) (i -> u for email) |
|
|
| Back to top |
|
|
|
| Virgil... |
| Posted: Mon Nov 09, 2009 12:20 am |
|
|
|
Guest
|
In article <gerry-0A8F9C.16350309112009 at (no spam) feeder.eternal-september.org>,
Gerry Myerson <gerry at (no spam) maths.mq.edi.ai.i2u4email> wrote:
[quote]In article
556ee733-9478-4e43-b8c4-cbcaa979b95a at (no spam) r24g2000prf.googlegroups.com>,
"Achava Nakhash, the Loving Snake" <achava at (no spam) hotmail.com> wrote:
On Nov 8, 5:45 pm, Gerry Myerson <ge... at (no spam) maths.mq.edi.ai.i2u4email
wrote:
In article
632452372.27941.1257546711399.JavaMail.r... at (no spam) gallium.mathforum.org>,
jane <jane1... at (no spam) 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... at (no spam) 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.
[/quote]
Note that if the original number of piles is odd rather than even, the
first player has a winning strategy. |
|
|
| Back to top |
|
|
|
| Gerry Myerson... |
| Posted: Mon Nov 09, 2009 12:35 am |
|
|
|
Guest
|
In article
<556ee733-9478-4e43-b8c4-cbcaa979b95a at (no spam) r24g2000prf.googlegroups.com>,
"Achava Nakhash, the Loving Snake" <achava at (no spam) hotmail.com> wrote:
[quote]On Nov 8, 5:45 pm, Gerry Myerson <ge... at (no spam) maths.mq.edi.ai.i2u4email
wrote:
In article
632452372.27941.1257546711399.JavaMail.r... at (no spam) gallium.mathforum.org>,
jane <jane1... at (no spam) 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... at (no spam) 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?
[/quote]
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 (gerry at (no spam) maths.mq.edi.ai) (i -> u for email) |
|
|
| Back to top |
|
|
|
| Achava Nakhash, the Loving Snake... |
| Posted: Mon Nov 09, 2009 12:46 am |
|
|
|
Guest
|
On Nov 8, 9:20 pm, Virgil <Vir... at (no spam) home.esc> wrote:
[quote]In article <gerry-0A8F9C.16350309112... at (no spam) feeder.eternal-september.org>,
Gerry Myerson <ge... at (no spam) maths.mq.edi.ai.i2u4email> wrote:
In article
556ee733-9478-4e43-b8c4-cbcaa979b... at (no spam) r24g2000prf.googlegroups.com>,
"Achava Nakhash, the Loving Snake" <ach... at (no spam) hotmail.com> wrote:
On Nov 8, 5:45 pm, Gerry Myerson <ge... at (no spam) maths.mq.edi.ai.i2u4email
wrote:
In article
632452372.27941.1257546711399.JavaMail.r... at (no spam) gallium.mathforum.org>,
jane <jane1... at (no spam) 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... at (no spam) 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.
[/quote]
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.
Regards,
Achava
Rea |
|
|
| Back to top |
|
|
|
| Gerry... |
| Posted: Mon Nov 09, 2009 1:38 am |
|
|
|
Guest
|
On Nov 9, 7:22 pm, Herman Jurjus <hjm... at (no spam) hetnet.nl> wrote:
[quote]Gerry Myerson wrote:
In article
632452372.27941.1257546711399.JavaMail.r... at (no spam) gallium.mathforum.org>,
jane <jane1... at (no spam) 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.
[/quote]
Yes, this is much better than what I wrote, as I overlooked
some of the subtleties.
--
GM |
|
|
| Back to top |
|
|
|
| Herman Jurjus... |
| Posted: Mon Nov 09, 2009 3:22 am |
|
|
|
Guest
|
Gerry Myerson wrote:
[quote]In article
632452372.27941.1257546711399.JavaMail.root at (no spam) gallium.mathforum.org>,
jane <jane1806 at (no spam) 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.
[/quote]
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.
--
Cheers,
Herman Jurjus |
|
|
| Back to top |
|
|
|
| Brian S... |
| Posted: Mon Nov 09, 2009 5:53 am |
|
|
|
Guest
|
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. |
|
|
| Back to top |
|
|
|
| Jim Ferry... |
| Posted: Mon Nov 09, 2009 10:58 am |
|
|
|
Guest
|
On Nov 6, 9:04 pm, "Achava Nakhash, the Loving Snake"
<ach... at (no spam) hotmail.com> wrote:
[quote]On Nov 6, 2:31 pm, jane <jane1... at (no spam) 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
[/quote]
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.)
Case 1:
1111
2222
3333
4444
5555
6666
Case 2:
1221
1331
1441
1551
1661
2112
2332
2442
2552
2662
3113
3223
3443
3553
3663
4114
4224
4334
4554
4664
5115
5225
5335
5445
5665
6116
6226
6336
6446
6556
Case 3:
1122
2233
3344
4455
5566
Case 4:
1231
1241
1251
1261
1341
1351
1361
1451
1461
1561
2342
2352
2362
2452
2462
2562
3123
3453
3463
3563
4124
4134
4234
4564
5125
5135
5145
5235
5245
5345
6126
6136
6146
6156
6236
6246
6256
6346
6356
6456
Case 5:
1132
1142
1152
1162
2133
2243
2253
2263
3144
3244
3354
3364
4155
4255
4355
4465
5166
5266
5366
5466
Case 6:
2143
2153
2163
3154
3164
3254
3264
4165
4265
4365 |
|
|
| Back to top |
|
|
|
| Herman Jurjus... |
| Posted: Mon Nov 09, 2009 11:23 am |
|
|
|
Guest
|
Brian S wrote:
[quote]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.
[/quote]
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.
--
Cheers,
Herman Jurjus |
|
|
| Back to top |
|
|
|
|
|
All times are GMT - 5 Hours
The time now is Mon Nov 30, 2009 8:07 pm
|
|