prove that exactly one player has a winning strategy - version of nim game Announcing the arrival of Valued Associate #679: Cesar Manara Planned maintenance scheduled April 23, 2019 at 00:00UTC (8:00pm US/Eastern)Prove using a strategy stealing argument that player 1 has a winning strategy in the chomp gameInduction solution for game of coinsNim Variant - Strong Induction ProofHow do I prove using strong form induction a statement regarding winning strategies in this coin game?Misere nim, 2nd player winning strategy proof by inductionWho should win the game dependent on $x$ and $y$?Single Pile Nim proof by InductionConsider the following two player game. A pile of coins is places on a tableStrong induction: Game of NimMathematical Induction and Recursion
How does Python know the values already stored in its memory?
Disembodied hand growing fangs
Why weren't discrete x86 CPUs ever used in game hardware?
SF book about people trapped in a series of worlds they imagine
What's the meaning of "fortified infraction restraint"?
Can the Great Weapon Master feat's damage bonus and accuracy penalty apply to attacks from the Spiritual Weapon spell?
How would a mousetrap for use in space work?
Why is it faster to reheat something than it is to cook it?
How could we fake a moon landing now?
Performance gap between vector<bool> and array
Why wasn't DOSKEY integrated with COMMAND.COM?
Why do early math courses focus on the cross sections of a cone and not on other 3D objects?
Is grep documentation about ignoring case wrong, since it doesn't ignore case in filenames?
How do I use the new nonlinear finite element in Mathematica 12 for this equation?
Do I really need to have a message in a novel to appeal to readers?
What is the difference between globalisation and imperialism?
How does light 'choose' between wave and particle behaviour?
What is a fractional matching?
How to write the following sign?
What does it mean that physics no longer uses mechanical models to describe phenomena?
Illegal assignment from sObject to Id
Find 108 by using 3,4,6
Is it fair for a professor to grade us on the possession of past papers?
What order were files/directories outputted in dir?
prove that exactly one player has a winning strategy - version of nim game
Announcing the arrival of Valued Associate #679: Cesar Manara
Planned maintenance scheduled April 23, 2019 at 00:00UTC (8:00pm US/Eastern)Prove using a strategy stealing argument that player 1 has a winning strategy in the chomp gameInduction solution for game of coinsNim Variant - Strong Induction ProofHow do I prove using strong form induction a statement regarding winning strategies in this coin game?Misere nim, 2nd player winning strategy proof by inductionWho should win the game dependent on $x$ and $y$?Single Pile Nim proof by InductionConsider the following two player game. A pile of coins is places on a tableStrong induction: Game of NimMathematical Induction and Recursion
$begingroup$
Game Description : the game is between 2 players and start with a pile of 'n' balls and A = a1,a2,...,ak ⊆ 1,....,n .
Course of the game : each player, in his turn, picks a ∈ A
balls from the pile.
the loosing player : the player that can't play on his turn, player cant play on his turn when the number of balls in the pile is smaller from the minimum number in A.
the Task : we have to prove that to every show of the problem n,A = a1,...,ak only one one of the following happens :
1) the first player (the player play first) has a winning strategy .
2) the second player has an winning strategy.
the winning strategy of the winner is not depend on the choices of the looser.
My Idea : I have tried to prove it with complete induction, but i'm stuck in the step.
I've assumed that for every show of the game with k<n balls the assert is holds and tried to show it holds for a game with 'n' balls.
so, the first case is that the first player can choose a ∈ A balls such that the number of balls left in the pile is less then the minimum number in A and hence player 2 cant perform his turn and player 1 allways wins.
otherwise, for any number of balls a ∈ A that player 1 took from the pile, player 2 can perform his turn. in this case the induction assertion holds (because the number of balls is less then 'n' in the pile now) and player 1 or player 2 (exactly one of them) has winning strategy. i'm stuck here. I don't know how to show that for every a ∈ A that player1 picks the player with the winning strategy will be the same one. for example if player 1 picks a1=4 from A and the induction assert find that player2 is the the player that has a winning strategy, it will return the same answear when player1 chooses a2=5 from A.
Thank you very much for your help!
induction
asked Apr 1 at 18:56
LiavbaLiavba
242
$endgroup$
add a comment |
$begingroup$
Game Description : the game is between 2 players and start with a pile of 'n' balls and A = a1,a2,...,ak ⊆ 1,....,n .
Course of the game : each player, in his turn, picks a ∈ A
balls from the pile.
the loosing player : the player that can't play on his turn, player cant play on his turn when the number of balls in the pile is smaller from the minimum number in A.
the Task : we have to prove that to every show of the problem n,A = a1,...,ak only one one of the following happens :
1) the first player (the player play first) has a winning strategy .
2) the second player has an winning strategy.
the winning strategy of the winner is not depend on the choices of the looser.
My Idea : I have tried to prove it with complete induction, but i'm stuck in the step.
I've assumed that for every show of the game with k<n balls the assert is holds and tried to show it holds for a game with 'n' balls.
so, the first case is that the first player can choose a ∈ A balls such that the number of balls left in the pile is less then the minimum number in A and hence player 2 cant perform his turn and player 1 allways wins.
otherwise, for any number of balls a ∈ A that player 1 took from the pile, player 2 can perform his turn. in this case the induction assertion holds (because the number of balls is less then 'n' in the pile now) and player 1 or player 2 (exactly one of them) has winning strategy. i'm stuck here. I don't know how to show that for every a ∈ A that player1 picks the player with the winning strategy will be the same one. for example if player 1 picks a1=4 from A and the induction assert find that player2 is the the player that has a winning strategy, it will return the same answear when player1 chooses a2=5 from A.
Thank you very much for your help!
induction
asked Apr 1 at 18:56
LiavbaLiavba
242
$endgroup$
add a comment |
$begingroup$
Game Description : the game is between 2 players and start with a pile of 'n' balls and A = a1,a2,...,ak ⊆ 1,....,n .
Course of the game : each player, in his turn, picks a ∈ A
balls from the pile.
the loosing player : the player that can't play on his turn, player cant play on his turn when the number of balls in the pile is smaller from the minimum number in A.
the Task : we have to prove that to every show of the problem n,A = a1,...,ak only one one of the following happens :
1) the first player (the player play first) has a winning strategy .
2) the second player has an winning strategy.
the winning strategy of the winner is not depend on the choices of the looser.
My Idea : I have tried to prove it with complete induction, but i'm stuck in the step.
I've assumed that for every show of the game with k<n balls the assert is holds and tried to show it holds for a game with 'n' balls.
so, the first case is that the first player can choose a ∈ A balls such that the number of balls left in the pile is less then the minimum number in A and hence player 2 cant perform his turn and player 1 allways wins.
otherwise, for any number of balls a ∈ A that player 1 took from the pile, player 2 can perform his turn. in this case the induction assertion holds (because the number of balls is less then 'n' in the pile now) and player 1 or player 2 (exactly one of them) has winning strategy. i'm stuck here. I don't know how to show that for every a ∈ A that player1 picks the player with the winning strategy will be the same one. for example if player 1 picks a1=4 from A and the induction assert find that player2 is the the player that has a winning strategy, it will return the same answear when player1 chooses a2=5 from A.
Thank you very much for your help!
induction
asked Apr 1 at 18:56
LiavbaLiavba
242
$endgroup$
Game Description : the game is between 2 players and start with a pile of 'n' balls and A = a1,a2,...,ak ⊆ 1,....,n .
Course of the game : each player, in his turn, picks a ∈ A
balls from the pile.
the loosing player : the player that can't play on his turn, player cant play on his turn when the number of balls in the pile is smaller from the minimum number in A.
the Task : we have to prove that to every show of the problem n,A = a1,...,ak only one one of the following happens :
1) the first player (the player play first) has a winning strategy .
2) the second player has an winning strategy.
the winning strategy of the winner is not depend on the choices of the looser.
My Idea : I have tried to prove it with complete induction, but i'm stuck in the step.
I've assumed that for every show of the game with k<n balls the assert is holds and tried to show it holds for a game with 'n' balls.
so, the first case is that the first player can choose a ∈ A balls such that the number of balls left in the pile is less then the minimum number in A and hence player 2 cant perform his turn and player 1 allways wins.
otherwise, for any number of balls a ∈ A that player 1 took from the pile, player 2 can perform his turn. in this case the induction assertion holds (because the number of balls is less then 'n' in the pile now) and player 1 or player 2 (exactly one of them) has winning strategy. i'm stuck here. I don't know how to show that for every a ∈ A that player1 picks the player with the winning strategy will be the same one. for example if player 1 picks a1=4 from A and the induction assert find that player2 is the the player that has a winning strategy, it will return the same answear when player1 chooses a2=5 from A.
Thank you very much for your help!
induction
induction
asked Apr 1 at 18:56
LiavbaLiavba
242
asked Apr 1 at 18:56
LiavbaLiavba
242
asked Apr 1 at 18:56
LiavbaLiavba
242
asked Apr 1 at 18:56
LiavbaLiavba
242
asked Apr 1 at 18:56
LiavbaLiavba
242
242
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
The crucial point is that the game is impartial, that the options from a given position are the same for both players. That allows you to categorize each number as an $N$ position, won by the next player or a $P$ position, won by the previous player. Now $n$ is an $N$ position iff you can move to a $P$ position.
answered Apr 1 at 19:03
Ross MillikanRoss Millikan
302k24201375
$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%2f3171014%2fprove-that-exactly-one-player-has-a-winning-strategy-version-of-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$
The crucial point is that the game is impartial, that the options from a given position are the same for both players. That allows you to categorize each number as an $N$ position, won by the next player or a $P$ position, won by the previous player. Now $n$ is an $N$ position iff you can move to a $P$ position.
answered Apr 1 at 19:03
Ross MillikanRoss Millikan
302k24201375
$endgroup$
add a comment |
$begingroup$
The crucial point is that the game is impartial, that the options from a given position are the same for both players. That allows you to categorize each number as an $N$ position, won by the next player or a $P$ position, won by the previous player. Now $n$ is an $N$ position iff you can move to a $P$ position.
answered Apr 1 at 19:03
Ross MillikanRoss Millikan
302k24201375
$endgroup$
add a comment |
$begingroup$
The crucial point is that the game is impartial, that the options from a given position are the same for both players. That allows you to categorize each number as an $N$ position, won by the next player or a $P$ position, won by the previous player. Now $n$ is an $N$ position iff you can move to a $P$ position.
answered Apr 1 at 19:03
Ross MillikanRoss Millikan
302k24201375
$endgroup$
The crucial point is that the game is impartial, that the options from a given position are the same for both players. That allows you to categorize each number as an $N$ position, won by the next player or a $P$ position, won by the previous player. Now $n$ is an $N$ position iff you can move to a $P$ position.
answered Apr 1 at 19:03
Ross MillikanRoss Millikan
302k24201375
answered Apr 1 at 19:03
Ross MillikanRoss Millikan
302k24201375
answered Apr 1 at 19:03
Ross MillikanRoss Millikan
302k24201375
answered Apr 1 at 19:03
Ross MillikanRoss Millikan
302k24201375
302k24201375
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%2f3171014%2fprove-that-exactly-one-player-has-a-winning-strategy-version-of-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
