Finding the winning strategy of a variation of the Nim game
$begingroup$
Here is a variant of the Nim game which I could not find out the winning strategy, the game rule is like this:
The games starts with 16 stones arranged as follow:
o (first pile)
ooo (second pile)
ooooo (third pile)
ooooooo (fourth pile)
Rules
1.Two players take turns to take away stones.
2.Each time you can at most take away all stones in the same pile , and you must at least take away one stone.
3.The player who takes away the last stone loses.
4.If one pile is split into two piles, you have to take away them in at least two turns.
For instance the third and fourth stones in the third pile was taken: (x represents the taken stones)
o
ooo
ooxxo
ooooooo
Then you are not allowed to take away all stones in the third pile in one turn. You have to take away all of them in at least two turns since it has been split into two piles:
First turn: oo xxo
Second turn: xxxx o
And for pattern like oxxoxoo, you have to take away all of them in at least 3 turns, etc.
The first three rules are similar to the classic NIM game(I know the winning strategy in the classic one), however the last rule makes it not applicable. My question is who has the winning strategy in this game, and what is the winning strategy?
game-theory combinatorial-game-theory
asked Dec 20 '18 at 14:20
Learning MathematicsLearning Mathematics
767
$endgroup$
add a comment |
$begingroup$
Here is a variant of the Nim game which I could not find out the winning strategy, the game rule is like this:
The games starts with 16 stones arranged as follow:
o (first pile)
ooo (second pile)
ooooo (third pile)
ooooooo (fourth pile)
Rules
1.Two players take turns to take away stones.
2.Each time you can at most take away all stones in the same pile , and you must at least take away one stone.
3.The player who takes away the last stone loses.
4.If one pile is split into two piles, you have to take away them in at least two turns.
For instance the third and fourth stones in the third pile was taken: (x represents the taken stones)
o
ooo
ooxxo
ooooooo
Then you are not allowed to take away all stones in the third pile in one turn. You have to take away all of them in at least two turns since it has been split into two piles:
First turn: oo xxo
Second turn: xxxx o
And for pattern like oxxoxoo, you have to take away all of them in at least 3 turns, etc.
The first three rules are similar to the classic NIM game(I know the winning strategy in the classic one), however the last rule makes it not applicable. My question is who has the winning strategy in this game, and what is the winning strategy?
game-theory combinatorial-game-theory
asked Dec 20 '18 at 14:20
Learning MathematicsLearning Mathematics
767
$endgroup$
1
$begingroup$
Do you know the Sprague Grundy theorem? That's all but crucial for this problem. If you already know it, what are your thoughts/where did you get stuck? If you don't, where did you encounter thos problem (e.g. in a programming class where you just have to write a program to make the winning moves?)?
$endgroup$
– Mark S.
Dec 20 '18 at 17:04
$begingroup$
There's also a chance you know the theorem without the name, so did you learn about applying "nimbers" or "grundy values" to games other than nim?
$endgroup$
– Mark S.
Dec 20 '18 at 17:06
$begingroup$
I haven't learnt that yet. My classmates played this game with me, but both of us dont know the winning strategy. I would take a look of the theorem today
$endgroup$
– Learning Mathematics
Dec 20 '18 at 23:47
$begingroup$
You can learn about this stuff with things from this list of resources
$endgroup$
– Mark S.
Dec 20 '18 at 23:50
$begingroup$
One more thing: have you tried playing it like Nim against, say, a random opponent, to see what you learn?
$endgroup$
– Mark S.
Dec 21 '18 at 3:15
add a comment |
$begingroup$
Here is a variant of the Nim game which I could not find out the winning strategy, the game rule is like this:
The games starts with 16 stones arranged as follow:
o (first pile)
ooo (second pile)
ooooo (third pile)
ooooooo (fourth pile)
Rules
1.Two players take turns to take away stones.
2.Each time you can at most take away all stones in the same pile , and you must at least take away one stone.
3.The player who takes away the last stone loses.
4.If one pile is split into two piles, you have to take away them in at least two turns.
For instance the third and fourth stones in the third pile was taken: (x represents the taken stones)
o
ooo
ooxxo
ooooooo
Then you are not allowed to take away all stones in the third pile in one turn. You have to take away all of them in at least two turns since it has been split into two piles:
First turn: oo xxo
Second turn: xxxx o
And for pattern like oxxoxoo, you have to take away all of them in at least 3 turns, etc.
The first three rules are similar to the classic NIM game(I know the winning strategy in the classic one), however the last rule makes it not applicable. My question is who has the winning strategy in this game, and what is the winning strategy?
game-theory combinatorial-game-theory
asked Dec 20 '18 at 14:20
Learning MathematicsLearning Mathematics
767
$endgroup$
Here is a variant of the Nim game which I could not find out the winning strategy, the game rule is like this:
The games starts with 16 stones arranged as follow:
o (first pile)
ooo (second pile)
ooooo (third pile)
ooooooo (fourth pile)
Rules
1.Two players take turns to take away stones.
2.Each time you can at most take away all stones in the same pile , and you must at least take away one stone.
3.The player who takes away the last stone loses.
4.If one pile is split into two piles, you have to take away them in at least two turns.
For instance the third and fourth stones in the third pile was taken: (x represents the taken stones)
o
ooo
ooxxo
ooooooo
Then you are not allowed to take away all stones in the third pile in one turn. You have to take away all of them in at least two turns since it has been split into two piles:
First turn: oo xxo
Second turn: xxxx o
And for pattern like oxxoxoo, you have to take away all of them in at least 3 turns, etc.
The first three rules are similar to the classic NIM game(I know the winning strategy in the classic one), however the last rule makes it not applicable. My question is who has the winning strategy in this game, and what is the winning strategy?
game-theory combinatorial-game-theory
game-theory combinatorial-game-theory
asked Dec 20 '18 at 14:20
Learning MathematicsLearning Mathematics
767
asked Dec 20 '18 at 14:20
Learning MathematicsLearning Mathematics
767
asked Dec 20 '18 at 14:20
Learning MathematicsLearning Mathematics
767
asked Dec 20 '18 at 14:20
Learning MathematicsLearning Mathematics
767
asked Dec 20 '18 at 14:20
Learning MathematicsLearning Mathematics
767
767
1
$begingroup$
Do you know the Sprague Grundy theorem? That's all but crucial for this problem. If you already know it, what are your thoughts/where did you get stuck? If you don't, where did you encounter thos problem (e.g. in a programming class where you just have to write a program to make the winning moves?)?
$endgroup$
– Mark S.
Dec 20 '18 at 17:04
$begingroup$
There's also a chance you know the theorem without the name, so did you learn about applying "nimbers" or "grundy values" to games other than nim?
$endgroup$
– Mark S.
Dec 20 '18 at 17:06
$begingroup$
I haven't learnt that yet. My classmates played this game with me, but both of us dont know the winning strategy. I would take a look of the theorem today
$endgroup$
– Learning Mathematics
Dec 20 '18 at 23:47
$begingroup$
You can learn about this stuff with things from this list of resources
$endgroup$
– Mark S.
Dec 20 '18 at 23:50
$begingroup$
One more thing: have you tried playing it like Nim against, say, a random opponent, to see what you learn?
$endgroup$
– Mark S.
Dec 21 '18 at 3:15
add a comment |
1
$begingroup$
Do you know the Sprague Grundy theorem? That's all but crucial for this problem. If you already know it, what are your thoughts/where did you get stuck? If you don't, where did you encounter thos problem (e.g. in a programming class where you just have to write a program to make the winning moves?)?
$endgroup$
– Mark S.
Dec 20 '18 at 17:04
$begingroup$
There's also a chance you know the theorem without the name, so did you learn about applying "nimbers" or "grundy values" to games other than nim?
$endgroup$
– Mark S.
Dec 20 '18 at 17:06
$begingroup$
I haven't learnt that yet. My classmates played this game with me, but both of us dont know the winning strategy. I would take a look of the theorem today
$endgroup$
– Learning Mathematics
Dec 20 '18 at 23:47
$begingroup$
You can learn about this stuff with things from this list of resources
$endgroup$
– Mark S.
Dec 20 '18 at 23:50
$begingroup$
One more thing: have you tried playing it like Nim against, say, a random opponent, to see what you learn?
$endgroup$
– Mark S.
Dec 21 '18 at 3:15
1
1
$begingroup$
Do you know the Sprague Grundy theorem? That's all but crucial for this problem. If you already know it, what are your thoughts/where did you get stuck? If you don't, where did you encounter thos problem (e.g. in a programming class where you just have to write a program to make the winning moves?)?
$endgroup$
– Mark S.
Dec 20 '18 at 17:04
$begingroup$
Do you know the Sprague Grundy theorem? That's all but crucial for this problem. If you already know it, what are your thoughts/where did you get stuck? If you don't, where did you encounter thos problem (e.g. in a programming class where you just have to write a program to make the winning moves?)?
$endgroup$
– Mark S.
Dec 20 '18 at 17:04
$begingroup$
There's also a chance you know the theorem without the name, so did you learn about applying "nimbers" or "grundy values" to games other than nim?
$endgroup$
– Mark S.
Dec 20 '18 at 17:06
$begingroup$
There's also a chance you know the theorem without the name, so did you learn about applying "nimbers" or "grundy values" to games other than nim?
$endgroup$
– Mark S.
Dec 20 '18 at 17:06
$begingroup$
I haven't learnt that yet. My classmates played this game with me, but both of us dont know the winning strategy. I would take a look of the theorem today
$endgroup$
– Learning Mathematics
Dec 20 '18 at 23:47
$begingroup$
I haven't learnt that yet. My classmates played this game with me, but both of us dont know the winning strategy. I would take a look of the theorem today
$endgroup$
– Learning Mathematics
Dec 20 '18 at 23:47
$begingroup$
You can learn about this stuff with things from this list of resources
$endgroup$
– Mark S.
Dec 20 '18 at 23:50
$begingroup$
You can learn about this stuff with things from this list of resources
$endgroup$
– Mark S.
Dec 20 '18 at 23:50
$begingroup$
One more thing: have you tried playing it like Nim against, say, a random opponent, to see what you learn?
$endgroup$
– Mark S.
Dec 21 '18 at 3:15
$begingroup$
One more thing: have you tried playing it like Nim against, say, a random opponent, to see what you learn?
$endgroup$
– Mark S.
Dec 21 '18 at 3:15
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Since you say you know the winning strategy in classical Nim, I presume you are familiar with the nim-sum $oplus$. If you play this position in classical Nim without the fourth rule, it is lost for the first player to move, as $1 oplus 3 oplus 5 oplus 7 = 0$.
With the fourth rule, you get additional moves: If you have a stack with $x+y+k$ stones, you can remove $k$ stones and leave two piles with $x$ and $y$ stones. The resulting Nim value of these two piles are $x oplus y$.
However, it is easy to show that $x oplus y leq x+y$. That means whenever you split a pile into two (or more!) piles, you can instead remove stones from the same pile without splitting it to get the same nim-value.
For instead, if you split the pile with 3 stones into two piles like this: oxo, the two piles have nim-value $1 oplus 1 = 0$. So you get the same nim-value if you take all three stones to remove the entire pile.
So the answers are: 1) In this game, the first player to move loses. 2) The winning strategy is exactly the same as in classical Nim, and you never have to split any piles. If your opponent does so, you always have an answer.
answered Dec 29 '18 at 11:53
JAskgaardJAskgaard
1467
$endgroup$
add a comment |
Your Answer
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3047583%2ffinding-the-winning-strategy-of-a-variation-of-the-nim-game%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Since you say you know the winning strategy in classical Nim, I presume you are familiar with the nim-sum $oplus$. If you play this position in classical Nim without the fourth rule, it is lost for the first player to move, as $1 oplus 3 oplus 5 oplus 7 = 0$.
With the fourth rule, you get additional moves: If you have a stack with $x+y+k$ stones, you can remove $k$ stones and leave two piles with $x$ and $y$ stones. The resulting Nim value of these two piles are $x oplus y$.
However, it is easy to show that $x oplus y leq x+y$. That means whenever you split a pile into two (or more!) piles, you can instead remove stones from the same pile without splitting it to get the same nim-value.
For instead, if you split the pile with 3 stones into two piles like this: oxo, the two piles have nim-value $1 oplus 1 = 0$. So you get the same nim-value if you take all three stones to remove the entire pile.
So the answers are: 1) In this game, the first player to move loses. 2) The winning strategy is exactly the same as in classical Nim, and you never have to split any piles. If your opponent does so, you always have an answer.
answered Dec 29 '18 at 11:53
JAskgaardJAskgaard
1467
$endgroup$
add a comment |
$begingroup$
Since you say you know the winning strategy in classical Nim, I presume you are familiar with the nim-sum $oplus$. If you play this position in classical Nim without the fourth rule, it is lost for the first player to move, as $1 oplus 3 oplus 5 oplus 7 = 0$.
With the fourth rule, you get additional moves: If you have a stack with $x+y+k$ stones, you can remove $k$ stones and leave two piles with $x$ and $y$ stones. The resulting Nim value of these two piles are $x oplus y$.
However, it is easy to show that $x oplus y leq x+y$. That means whenever you split a pile into two (or more!) piles, you can instead remove stones from the same pile without splitting it to get the same nim-value.
For instead, if you split the pile with 3 stones into two piles like this: oxo, the two piles have nim-value $1 oplus 1 = 0$. So you get the same nim-value if you take all three stones to remove the entire pile.
So the answers are: 1) In this game, the first player to move loses. 2) The winning strategy is exactly the same as in classical Nim, and you never have to split any piles. If your opponent does so, you always have an answer.
answered Dec 29 '18 at 11:53
JAskgaardJAskgaard
1467
$endgroup$
add a comment |
$begingroup$
Since you say you know the winning strategy in classical Nim, I presume you are familiar with the nim-sum $oplus$. If you play this position in classical Nim without the fourth rule, it is lost for the first player to move, as $1 oplus 3 oplus 5 oplus 7 = 0$.
With the fourth rule, you get additional moves: If you have a stack with $x+y+k$ stones, you can remove $k$ stones and leave two piles with $x$ and $y$ stones. The resulting Nim value of these two piles are $x oplus y$.
However, it is easy to show that $x oplus y leq x+y$. That means whenever you split a pile into two (or more!) piles, you can instead remove stones from the same pile without splitting it to get the same nim-value.
For instead, if you split the pile with 3 stones into two piles like this: oxo, the two piles have nim-value $1 oplus 1 = 0$. So you get the same nim-value if you take all three stones to remove the entire pile.
So the answers are: 1) In this game, the first player to move loses. 2) The winning strategy is exactly the same as in classical Nim, and you never have to split any piles. If your opponent does so, you always have an answer.
answered Dec 29 '18 at 11:53
JAskgaardJAskgaard
1467
$endgroup$
Since you say you know the winning strategy in classical Nim, I presume you are familiar with the nim-sum $oplus$. If you play this position in classical Nim without the fourth rule, it is lost for the first player to move, as $1 oplus 3 oplus 5 oplus 7 = 0$.
With the fourth rule, you get additional moves: If you have a stack with $x+y+k$ stones, you can remove $k$ stones and leave two piles with $x$ and $y$ stones. The resulting Nim value of these two piles are $x oplus y$.
However, it is easy to show that $x oplus y leq x+y$. That means whenever you split a pile into two (or more!) piles, you can instead remove stones from the same pile without splitting it to get the same nim-value.
For instead, if you split the pile with 3 stones into two piles like this: oxo, the two piles have nim-value $1 oplus 1 = 0$. So you get the same nim-value if you take all three stones to remove the entire pile.
So the answers are: 1) In this game, the first player to move loses. 2) The winning strategy is exactly the same as in classical Nim, and you never have to split any piles. If your opponent does so, you always have an answer.
answered Dec 29 '18 at 11:53
JAskgaardJAskgaard
1467
answered Dec 29 '18 at 11:53
JAskgaardJAskgaard
1467
answered Dec 29 '18 at 11:53
JAskgaardJAskgaard
1467
answered Dec 29 '18 at 11:53
JAskgaardJAskgaard
1467
1467
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3047583%2ffinding-the-winning-strategy-of-a-variation-of-the-nim-game%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
$begingroup$
Do you know the Sprague Grundy theorem? That's all but crucial for this problem. If you already know it, what are your thoughts/where did you get stuck? If you don't, where did you encounter thos problem (e.g. in a programming class where you just have to write a program to make the winning moves?)?
$endgroup$
– Mark S.
Dec 20 '18 at 17:04
$begingroup$
There's also a chance you know the theorem without the name, so did you learn about applying "nimbers" or "grundy values" to games other than nim?
$endgroup$
– Mark S.
Dec 20 '18 at 17:06
$begingroup$
I haven't learnt that yet. My classmates played this game with me, but both of us dont know the winning strategy. I would take a look of the theorem today
$endgroup$
– Learning Mathematics
Dec 20 '18 at 23:47
$begingroup$
You can learn about this stuff with things from this list of resources
$endgroup$
– Mark S.
Dec 20 '18 at 23:50
$begingroup$
One more thing: have you tried playing it like Nim against, say, a random opponent, to see what you learn?
$endgroup$
– Mark S.
Dec 21 '18 at 3:15