Author |
Topic: Winning strategy for the picking marbles game (Read 2758 times) |
|
wonderful
Full Member
Posts: 203
|
 |
Winning strategy for the picking marbles game
« on: Jan 19th, 2009, 3:08am » |
 Quote  Modify
|
There are three boxes of marbles. Box 1 has 30 marbles, box 2 has 37 marbles, and box 3 has 46 marbles. Two people play the following game:
Each in turn picks either 1, 2, 4, or 6 marbles in one of three boxes. The objective of the game is to force the oponent to pick up the last marble.
What is the winning startegy?
|
|
 IP Logged |
|
|
|
Noke Lieu
Uberpuzzler
pen... paper... let's go! (and bit of plastic)
Gender: 
Posts: 1884
|
|
Re: Winning strategy for the picking marbles game
« Reply #1 on: Jan 20th, 2009, 3:49pm » |
Quote Modify
|
From my first poke at it, I'd have to say "Bet $20 bucks on me losing the marble game." 
|
|
IP Logged |
a shade of wit and the art of farce.
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Winning strategy for the picking marbles game
« Reply #2 on: Jan 20th, 2009, 10:11pm » |
Quote Modify
|
Nimbers!
The strategy that comes out of that is:
For each box, take the remainder mod 8. If larger than 3, subtract 3. That is the nimber of a box.
XOR the nimbers of the boxes giving the nimber of the game.
The strategy is to make any move that brings that number back to 0.
For the starting position:
30 -> 6 -> 3
37 -> 5 -> 2
46 -> 6 -> 3
The game nimber is 2.
To win, you can take 2 from any of the 3 boxes.
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Winning strategy for the picking marbles game
« Reply #3 on: Jan 21st, 2009, 3:54am » |
Quote Modify
|
That's the strategy for normal play. Misere play is trickier.
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Winning strategy for the picking marbles game
« Reply #4 on: Jan 21st, 2009, 6:47am » |
Quote Modify
|
Right! Back to the drawing board. 
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Winning strategy for the picking marbles game
« Reply #5 on: Jan 21st, 2009, 11:26am » |
Quote Modify
|
on Jan 19th, 2009, 3:08am, wonderful wrote:| What is the winning startegy? |
|
Using a computer or cheat-sheet.
And start by taking 2 from any of the piles.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Winning strategy for the picking marbles game
« Reply #6 on: Jan 21st, 2009, 12:03pm » |
Quote Modify
|
Hey, that's exactly what I said!
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2874
|
|
Re: Winning strategy for the picking marbles game
« Reply #7 on: Jan 21st, 2009, 12:42pm » |
Quote Modify
|
As I recall, misere play differs from regular play only in the endgame...
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Winning strategy for the picking marbles game
« Reply #8 on: Jan 21st, 2009, 1:00pm » |
Quote Modify
|
on Jan 21st, 2009, 12:42pm, rmsgrey wrote:| As I recall, misere play differs from regular play only in the endgame... |
|
Well, I can say one thing (provided my program is correct), and that's that it only rarely doesn't matter which box you take an X number of marbles from.
For example if we start with
30,37,46 -> 28,37,46 -> 27,37,46
Then to win you must take either 2 from the first box, or 1 or 4 from the last. Anything else and you find yourself in a losing position.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Winning strategy for the picking marbles game
« Reply #9 on: Jan 21st, 2009, 2:29pm » |
Quote Modify
|
Yes (to rmsgrey). For standard Nim the misere strategy is the same as for normal play except that when you reach the situation where there are only 1's left, then you must take one more or one less (xor with 1) to change the parity. I am not sure whether that twist can be implemented in the 3 boxes game.
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Winning strategy for the picking marbles game
« Reply #10 on: Jan 21st, 2009, 4:17pm » |
Quote Modify
|
The following multisets of nimbers (Grundy numbers) for the boxes are losing states (i.e., states you want to leave your opponent with):
{0, 0, 1}, {0, 2, 2}, {0, 3, 3}, {0, 4, 4}, {1, 1, 1}, {1, 2, 3}
everything else is a winning state.
Note that {0,0,1} an {1,1,1} have xor 1 and are losing, while {0,0,0} and {0,1,1} have xor 0 and are winning. The rest are losing iff xor=0.
(The nimbers for stacks of 0,1,2,... marbles repeat {0, 1, 2, 0, 1, 2, 3, 4}.)
|
|
IP Logged |
|
|
|
wonderful
Full Member
Posts: 203
|
|
Re: Winning strategy for the picking marbles game
« Reply #11 on: Jan 23rd, 2009, 5:23am » |
Quote Modify
|
Thanks for your interesting discussion. However, it seems that you forget the restriction that each time the players allow to pick 1, or 2, or 4, or 6 marbles. As such, the strategy may differ from the standard nim game.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Winning strategy for the picking marbles game
« Reply #12 on: Jan 23rd, 2009, 5:47am » |
Quote Modify
|
on Jan 23rd, 2009, 5:23am, wonderful wrote:| Thanks for your interesting discussion. However, it seems that you forget the restriction that each time the players allow to pick 1, or 2, or 4, or 6 marbles. As such, the strategy may differ from the standard nim game. |
|
I don't think they forgot.
You just have to pick the right number of marbles to get from one multiset of nimbers to another.
|
| « Last Edit: Jan 23rd, 2009, 5:47am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
wonderful
Full Member
Posts: 203
|
|
Re: Winning strategy for the picking marbles game
« Reply #13 on: Jan 23rd, 2009, 6:37am » |
Quote Modify
|
Here is an example:
A, B are two players. A is in the following position: (4, 4, 0), thus, XOR of nimbers = 0. However, by picking 4 in the first box, A forces B to pick up either 1, 2, or 4 in the the second box. A is left with 3, 2, or 0. By picking 2, 1, or 0, A is the winner.
In a standard nim with no restriction, if A picked 4 in the fist box, B would just pick 3 in the second box to be the winner.
|
| « Last Edit: Jan 23rd, 2009, 6:46am by wonderful » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Winning strategy for the picking marbles game
« Reply #14 on: Jan 23rd, 2009, 7:03am » |
Quote Modify
|
on Jan 23rd, 2009, 6:37am, wonderful wrote:Here is an example:
A, B are two players. A is in the following position: (4, 4, 0), thus, XOR of nimbers = 0. |
|
Yes, but the nimber set is {1,1,0}, so it's a win for A
(Read Grimbal's post for how to calculate the nimber of a stack in this game)
Quote:| However, by picking 4 in the first box, A forces B to pick up either 1, 2, or 4 in the the second box. A is left with 3, 2, or 0. By picking 2, 1, or 0, A is the winner. |
|
Precisely as predicted.
|
| « Last Edit: Jan 23rd, 2009, 7:08am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
wonderful
Full Member
Posts: 203
|
|
Re: Winning strategy for the picking marbles game
« Reply #15 on: Jan 23rd, 2009, 7:25am » |
Quote Modify
|
on Jan 23rd, 2009, 7:03am, towr wrote:
[quote]Yes, but the nimber set is {1,1,0}, so it's a win for A |
|
There may be some miscommunication here. According to Grimbal, B should be the winner in this case since he puts A in a position s.t. XOR = 0
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Winning strategy for the picking marbles game
« Reply #16 on: Jan 23rd, 2009, 7:34am » |
Quote Modify
|
on Jan 23rd, 2009, 7:25am, wonderful wrote:| There may be some miscommunication here. According to Grimbal, B should be the winner in this case since he puts A in a position s.t. XOR = 0 |
|
You have to cleverly combine Grimbal's and Eigenray's posts.
For each box, take the number of elements modulo 8; and if that number is 3 or greater, subtract 3.
Now you have a multi-set of three nimbers.
For example, {0,4,4} goes to {0,1,1} and {30,37,46} goes to {3,2,3}
If this multi-set is (disregarding order) amongst
{0, 0, 1}, {0, 2, 2}, {0, 3, 3}, {0, 4, 4}, {1, 1, 1}, {1, 2, 3}
Then you lose. Otherwise you win by arranging it so the other player is faced with one of those positions.
Aside from {0,0,0}, {0,0,1}, {0,1,1} and {1,1,1} (i.e. the sets where all numbers are 1 or less) a state is losing iff and only if the XOR of the nimbers is 0. (For those 4 it is reversed)
I'm not sure if there is a clever way to tell how many elements you should pick from which box, but there's only 12 variations to try.
|
| « Last Edit: Jan 23rd, 2009, 7:39am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
wonderful
Full Member
Posts: 203
|
|
Re: Winning strategy for the picking marbles game
« Reply #17 on: Jan 23rd, 2009, 7:54am » |
Quote Modify
|
Quote:If this multi-set is (disregarding order) amongst
{0, 0, 1}, {0, 2, 2}, {0, 3, 3}, {0, 4, 4}, {1, 1, 1}, {1, 2, 3}
Then you lose. Otherwise you win by arranging it so the other player is faced with one of those positions. |
|
Thanks Towr for the clarification. I appreciate it. However, I actually used the {0, 4, 4} to make the point. If A was in this position, by picking 4 in the second box he won the game.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Winning strategy for the picking marbles game
« Reply #18 on: Jan 23rd, 2009, 7:57am » |
Quote Modify
|
on Jan 23rd, 2009, 7:54am, wonderful wrote:| Thanks Towr for the clarification. I appreciate it. However, I actually used the {0, 4, 4} to make the point. If A was in this position, by picking 4 in the second box he won the game. |
|
Yes, because game {0,4,4} gets nimbers {0,1,1}, and that's a winning position.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Winning strategy for the picking marbles game
« Reply #19 on: Jan 25th, 2009, 12:28pm » |
Quote Modify
|
I didn't actually think about it ... the case {0,4,4} is presented to represent (8,7,7) position.
(8,7,7)->{0,7-3=4,7-3=4}
(0,4,4)->{0,4-3=1,4-3=1},
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Winning strategy for the picking marbles game
« Reply #20 on: Jan 25th, 2009, 12:57pm » |
Quote Modify
|
on Jan 25th, 2009, 12:28pm, Hippo wrote:| I didn't actually think about it ... the case {0,4,4} is presented to represent (8,7,7) position. |
|
Indeed, and therefore {8,7,7} isn't winnable.
|
| « Last Edit: Jan 25th, 2009, 1:08pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print