How to give a winning strategy for this game?
$begingroup$
I have the following question with me:
"Start with several piles of chips. Two players move alternately. A move consists in splitting every pile with more than one chip in two piles. The one who makes the last move wins. For what initial conditions does the first player win and what is his winning strategy"
I found this similar to Grundy's game but they haven't mentioned in the given question that the two piles are unequal. My book says that the first player wins if the largest number of chips in a pile is not equal to $2^m - 1$ for some $m$. The book further says that the required strategy for the first player is to split the piles in such a way that the one of the resulting piles should have the number of chips equal to $2^m - 1$ for some.
However, let's say I have $(6,2,1)$ to start with.
I perform the following operations $$(6,2,1) rightarrow (3,3,2,1)$$This move is made by the first player. It is quite easy to see that B wins in any case in the above situation. Thus, followig the given strategy the statement given in the book seems to be wrong. Is there any mistake with the book or is there any mistake with my interpretation? A solution with the correct conditions would also be appreciated.
Thanks in advance
combinatorial-game-theory
asked Dec 21 '18 at 15:13
saisanjeevsaisanjeev
997212
$endgroup$
add a comment |
$begingroup$
I have the following question with me:
"Start with several piles of chips. Two players move alternately. A move consists in splitting every pile with more than one chip in two piles. The one who makes the last move wins. For what initial conditions does the first player win and what is his winning strategy"
I found this similar to Grundy's game but they haven't mentioned in the given question that the two piles are unequal. My book says that the first player wins if the largest number of chips in a pile is not equal to $2^m - 1$ for some $m$. The book further says that the required strategy for the first player is to split the piles in such a way that the one of the resulting piles should have the number of chips equal to $2^m - 1$ for some.
However, let's say I have $(6,2,1)$ to start with.
I perform the following operations $$(6,2,1) rightarrow (3,3,2,1)$$This move is made by the first player. It is quite easy to see that B wins in any case in the above situation. Thus, followig the given strategy the statement given in the book seems to be wrong. Is there any mistake with the book or is there any mistake with my interpretation? A solution with the correct conditions would also be appreciated.
Thanks in advance
combinatorial-game-theory
asked Dec 21 '18 at 15:13
saisanjeevsaisanjeev
997212
$endgroup$
1
$begingroup$
The rule you quote is to split every pile greater than $1$, but in your example you did not split the $2$. Now $B$ must split both the $3$s to $2,1$ and $A$ splits the $2$s and wins.
$endgroup$
– Ross Millikan
Dec 21 '18 at 15:16
$begingroup$
But can B split all the 3s in a single move?
$endgroup$
– saisanjeev
Dec 23 '18 at 8:32
2
$begingroup$
It is your game, but the third sentence in your quoted set of rules says that a player must split every pile larger than $1$. A game where a player splits just one pile would not be interesting because it doesn't matter what you do. If there are $n$ chips in $m$ piles the game will last $n-m$ moves and the winner just depends on the parity of that number.
$endgroup$
– Ross Millikan
Dec 23 '18 at 15:07
add a comment |
$begingroup$
I have the following question with me:
"Start with several piles of chips. Two players move alternately. A move consists in splitting every pile with more than one chip in two piles. The one who makes the last move wins. For what initial conditions does the first player win and what is his winning strategy"
I found this similar to Grundy's game but they haven't mentioned in the given question that the two piles are unequal. My book says that the first player wins if the largest number of chips in a pile is not equal to $2^m - 1$ for some $m$. The book further says that the required strategy for the first player is to split the piles in such a way that the one of the resulting piles should have the number of chips equal to $2^m - 1$ for some.
However, let's say I have $(6,2,1)$ to start with.
I perform the following operations $$(6,2,1) rightarrow (3,3,2,1)$$This move is made by the first player. It is quite easy to see that B wins in any case in the above situation. Thus, followig the given strategy the statement given in the book seems to be wrong. Is there any mistake with the book or is there any mistake with my interpretation? A solution with the correct conditions would also be appreciated.
Thanks in advance
combinatorial-game-theory
asked Dec 21 '18 at 15:13
saisanjeevsaisanjeev
997212
$endgroup$
I have the following question with me:
"Start with several piles of chips. Two players move alternately. A move consists in splitting every pile with more than one chip in two piles. The one who makes the last move wins. For what initial conditions does the first player win and what is his winning strategy"
I found this similar to Grundy's game but they haven't mentioned in the given question that the two piles are unequal. My book says that the first player wins if the largest number of chips in a pile is not equal to $2^m - 1$ for some $m$. The book further says that the required strategy for the first player is to split the piles in such a way that the one of the resulting piles should have the number of chips equal to $2^m - 1$ for some.
However, let's say I have $(6,2,1)$ to start with.
I perform the following operations $$(6,2,1) rightarrow (3,3,2,1)$$This move is made by the first player. It is quite easy to see that B wins in any case in the above situation. Thus, followig the given strategy the statement given in the book seems to be wrong. Is there any mistake with the book or is there any mistake with my interpretation? A solution with the correct conditions would also be appreciated.
Thanks in advance
combinatorial-game-theory
combinatorial-game-theory
asked Dec 21 '18 at 15:13
saisanjeevsaisanjeev
997212
asked Dec 21 '18 at 15:13
saisanjeevsaisanjeev
997212
asked Dec 21 '18 at 15:13
saisanjeevsaisanjeev
997212
asked Dec 21 '18 at 15:13
saisanjeevsaisanjeev
997212
asked Dec 21 '18 at 15:13
saisanjeevsaisanjeev
997212
997212
1
$begingroup$
The rule you quote is to split every pile greater than $1$, but in your example you did not split the $2$. Now $B$ must split both the $3$s to $2,1$ and $A$ splits the $2$s and wins.
$endgroup$
– Ross Millikan
Dec 21 '18 at 15:16
$begingroup$
But can B split all the 3s in a single move?
$endgroup$
– saisanjeev
Dec 23 '18 at 8:32
2
$begingroup$
It is your game, but the third sentence in your quoted set of rules says that a player must split every pile larger than $1$. A game where a player splits just one pile would not be interesting because it doesn't matter what you do. If there are $n$ chips in $m$ piles the game will last $n-m$ moves and the winner just depends on the parity of that number.
$endgroup$
– Ross Millikan
Dec 23 '18 at 15:07
add a comment |
1
$begingroup$
The rule you quote is to split every pile greater than $1$, but in your example you did not split the $2$. Now $B$ must split both the $3$s to $2,1$ and $A$ splits the $2$s and wins.
$endgroup$
– Ross Millikan
Dec 21 '18 at 15:16
$begingroup$
But can B split all the 3s in a single move?
$endgroup$
– saisanjeev
Dec 23 '18 at 8:32
2
$begingroup$
It is your game, but the third sentence in your quoted set of rules says that a player must split every pile larger than $1$. A game where a player splits just one pile would not be interesting because it doesn't matter what you do. If there are $n$ chips in $m$ piles the game will last $n-m$ moves and the winner just depends on the parity of that number.
$endgroup$
– Ross Millikan
Dec 23 '18 at 15:07
1
1
$begingroup$
The rule you quote is to split every pile greater than $1$, but in your example you did not split the $2$. Now $B$ must split both the $3$s to $2,1$ and $A$ splits the $2$s and wins.
$endgroup$
– Ross Millikan
Dec 21 '18 at 15:16
$begingroup$
The rule you quote is to split every pile greater than $1$, but in your example you did not split the $2$. Now $B$ must split both the $3$s to $2,1$ and $A$ splits the $2$s and wins.
$endgroup$
– Ross Millikan
Dec 21 '18 at 15:16
$begingroup$
But can B split all the 3s in a single move?
$endgroup$
– saisanjeev
Dec 23 '18 at 8:32
$begingroup$
But can B split all the 3s in a single move?
$endgroup$
– saisanjeev
Dec 23 '18 at 8:32
2
2
$begingroup$
It is your game, but the third sentence in your quoted set of rules says that a player must split every pile larger than $1$. A game where a player splits just one pile would not be interesting because it doesn't matter what you do. If there are $n$ chips in $m$ piles the game will last $n-m$ moves and the winner just depends on the parity of that number.
$endgroup$
– Ross Millikan
Dec 23 '18 at 15:07
$begingroup$
It is your game, but the third sentence in your quoted set of rules says that a player must split every pile larger than $1$. A game where a player splits just one pile would not be interesting because it doesn't matter what you do. If there are $n$ chips in $m$ piles the game will last $n-m$ moves and the winner just depends on the parity of that number.
$endgroup$
– Ross Millikan
Dec 23 '18 at 15:07
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
The rule should be to leave a situation where the largest pile is $2^m-1$. You only care about the largest pile because all the others will be split to $1$ before this one. Now if the largest pile is $2^m-1$ at least one of the piles it is split into must be at least $2^{m-1}$ so you can leave $2^{m-1}-1$ and make sure all the other piles are smaller.
To contrast my strategy with the one you quote, say we start with one pile of $8$ chips. I claim the only winning move is to $7,1$, from which the first player can get to the largest pile being $3$ next move and win on the one after. Your writeup says leave a pile of $2^m-1$ so you could move to $5,3$. If I am the second player here, I move to $3,2,2,1$, you have to move to $2,1,1,1,1,1,1$ and I win by splitting the $2$.
answered Dec 21 '18 at 15:19
Ross MillikanRoss Millikan
298k23198371
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
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%2f3048590%2fhow-to-give-a-winning-strategy-for-this-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$
The rule should be to leave a situation where the largest pile is $2^m-1$. You only care about the largest pile because all the others will be split to $1$ before this one. Now if the largest pile is $2^m-1$ at least one of the piles it is split into must be at least $2^{m-1}$ so you can leave $2^{m-1}-1$ and make sure all the other piles are smaller.
To contrast my strategy with the one you quote, say we start with one pile of $8$ chips. I claim the only winning move is to $7,1$, from which the first player can get to the largest pile being $3$ next move and win on the one after. Your writeup says leave a pile of $2^m-1$ so you could move to $5,3$. If I am the second player here, I move to $3,2,2,1$, you have to move to $2,1,1,1,1,1,1$ and I win by splitting the $2$.
answered Dec 21 '18 at 15:19
Ross MillikanRoss Millikan
298k23198371
$endgroup$
add a comment |
$begingroup$
The rule should be to leave a situation where the largest pile is $2^m-1$. You only care about the largest pile because all the others will be split to $1$ before this one. Now if the largest pile is $2^m-1$ at least one of the piles it is split into must be at least $2^{m-1}$ so you can leave $2^{m-1}-1$ and make sure all the other piles are smaller.
To contrast my strategy with the one you quote, say we start with one pile of $8$ chips. I claim the only winning move is to $7,1$, from which the first player can get to the largest pile being $3$ next move and win on the one after. Your writeup says leave a pile of $2^m-1$ so you could move to $5,3$. If I am the second player here, I move to $3,2,2,1$, you have to move to $2,1,1,1,1,1,1$ and I win by splitting the $2$.
answered Dec 21 '18 at 15:19
Ross MillikanRoss Millikan
298k23198371
$endgroup$
add a comment |
$begingroup$
The rule should be to leave a situation where the largest pile is $2^m-1$. You only care about the largest pile because all the others will be split to $1$ before this one. Now if the largest pile is $2^m-1$ at least one of the piles it is split into must be at least $2^{m-1}$ so you can leave $2^{m-1}-1$ and make sure all the other piles are smaller.
To contrast my strategy with the one you quote, say we start with one pile of $8$ chips. I claim the only winning move is to $7,1$, from which the first player can get to the largest pile being $3$ next move and win on the one after. Your writeup says leave a pile of $2^m-1$ so you could move to $5,3$. If I am the second player here, I move to $3,2,2,1$, you have to move to $2,1,1,1,1,1,1$ and I win by splitting the $2$.
answered Dec 21 '18 at 15:19
Ross MillikanRoss Millikan
298k23198371
$endgroup$
The rule should be to leave a situation where the largest pile is $2^m-1$. You only care about the largest pile because all the others will be split to $1$ before this one. Now if the largest pile is $2^m-1$ at least one of the piles it is split into must be at least $2^{m-1}$ so you can leave $2^{m-1}-1$ and make sure all the other piles are smaller.
To contrast my strategy with the one you quote, say we start with one pile of $8$ chips. I claim the only winning move is to $7,1$, from which the first player can get to the largest pile being $3$ next move and win on the one after. Your writeup says leave a pile of $2^m-1$ so you could move to $5,3$. If I am the second player here, I move to $3,2,2,1$, you have to move to $2,1,1,1,1,1,1$ and I win by splitting the $2$.
answered Dec 21 '18 at 15:19
Ross MillikanRoss Millikan
298k23198371
edited Dec 24 '18 at 14:41
answered Dec 21 '18 at 15:19
Ross MillikanRoss Millikan
298k23198371
answered Dec 21 '18 at 15:19
Ross MillikanRoss Millikan
298k23198371
answered Dec 21 '18 at 15:19
Ross MillikanRoss Millikan
298k23198371
298k23198371
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%2f3048590%2fhow-to-give-a-winning-strategy-for-this-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$
The rule you quote is to split every pile greater than $1$, but in your example you did not split the $2$. Now $B$ must split both the $3$s to $2,1$ and $A$ splits the $2$s and wins.
$endgroup$
– Ross Millikan
Dec 21 '18 at 15:16
$begingroup$
But can B split all the 3s in a single move?
$endgroup$
– saisanjeev
Dec 23 '18 at 8:32
2
$begingroup$
It is your game, but the third sentence in your quoted set of rules says that a player must split every pile larger than $1$. A game where a player splits just one pile would not be interesting because it doesn't matter what you do. If there are $n$ chips in $m$ piles the game will last $n-m$ moves and the winner just depends on the parity of that number.
$endgroup$
– Ross Millikan
Dec 23 '18 at 15:07