Double or Take gameRook game on chessboardGuess my number! Pay for the answer!The subtraction gameKnight on a 5 by 5 boardDim - A Game with PebblesFace Up Poker with Alice and BobAlternate Face Up Poker with Alice and Bob (on the floor)Let's revisit this later (a two player knight's game)Rook Game on a Chessboard - Take 2Paper, pencil and a bunch of bars
How does Howard Stark know this?
Ex-manager wants to stay in touch, I don't want to
Why does a C.D.F need to be right-continuous?
How can a Lich look like a human without magic?
Renting a house to a graduate student in my department
Why is it so slow when assigning a concatenated string to a variable in python?
How to make the table in the figure in LaTeX?
Is Simic Ascendancy triggered by Awakening of Vitu-Ghazi?
Should these notes be played as a chord or one after another?
Why was this sacrifice sufficient?
Best species to breed to intelligence
How old is Captain America at the end of "Avengers: Endgame"?
Would an 8% reduction in drag outweigh the weight addition from this custom CFD-tested winglet?
Why do Thanos's punches not kill Captain America or at least cause some mortal injuries?
How to make a language evolve quickly?
Why use steam instead of just hot air?
On what legal basis did the UK remove the 'European Union' from its passport?
Why in a Ethernet LAN, a packet sniffer can obtain all packets sent over the LAN?
How can this pool heater gas line be disconnected?
Remove everything except csv file Bash Script
International Code of Ethics for order of co-authors in research papers
How do I get past a 3-year ban from overstay with VWP?
Set a camera to free fall like a Rigid Body?
What does it mean with the ask price is below the last price?
Double or Take game
Rook game on chessboardGuess my number! Pay for the answer!The subtraction gameKnight on a 5 by 5 boardDim - A Game with PebblesFace Up Poker with Alice and BobAlternate Face Up Poker with Alice and Bob (on the floor)Let's revisit this later (a two player knight's game)Rook Game on a Chessboard - Take 2Paper, pencil and a bunch of bars
$begingroup$
Double or Take is a two-player number game. Alice starts by selecting any positive integer. Bob's options are to:
- subtract a positive perfect square
- subtract a positive perfect cube, or
- double the number.
Alice then takes the result, and has the same options. Play alternates, with the winner being the first player to reach exactly zero.
What are the possible starting numbers between $1$ and $11$ that Alice could choose to be sure that she can beat Bob?
And as a bonus (it's not essential to answer this, and may be tedious with pencil and paper): can Alice be sure of beating Bob if she chooses $12$ as the starting number?
game number-theory nim
edited May 1 at 21:11
Hugh
2,34311127
asked May 1 at 15:16
MichaelMaggsMichaelMaggs
47211
$endgroup$
|
show 3 more comments
$begingroup$
Double or Take is a two-player number game. Alice starts by selecting any positive integer. Bob's options are to:
- subtract a positive perfect square
- subtract a positive perfect cube, or
- double the number.
Alice then takes the result, and has the same options. Play alternates, with the winner being the first player to reach exactly zero.
What are the possible starting numbers between $1$ and $11$ that Alice could choose to be sure that she can beat Bob?
And as a bonus (it's not essential to answer this, and may be tedious with pencil and paper): can Alice be sure of beating Bob if she chooses $12$ as the starting number?
game number-theory nim
edited May 1 at 21:11
Hugh
2,34311127
asked May 1 at 15:16
MichaelMaggsMichaelMaggs
47211
$endgroup$
$begingroup$
Source for the game: Martin Gardner in a 1970's Sci.Am. column, I think, though I'm now unable to locate it. If anyone can find the exact column I'd be very grateful.
$endgroup$
– MichaelMaggs
May 1 at 15:16
$begingroup$
"reaching zero" implies exactly zero? As in not going beyond zero to a negative integer?
$endgroup$
– BDrought
May 1 at 15:28
$begingroup$
That's right. Players are not allowed to end up with a negative number.
$endgroup$
– MichaelMaggs
May 1 at 15:30
$begingroup$
I do have the answer for 12, but as there are a lot of possible plays it would be lengthy to set them all out in full. And maybe not that interesting.
$endgroup$
– MichaelMaggs
May 1 at 15:47
$begingroup$
I'm still looking at the situation starting at 12, and you're not wrong about it being tedious with pencil and paper. How do you feel about computer-assisted solutions to this one?
$endgroup$
– Gareth McCaughan♦
May 1 at 16:21
|
show 3 more comments
$begingroup$
Double or Take is a two-player number game. Alice starts by selecting any positive integer. Bob's options are to:
- subtract a positive perfect square
- subtract a positive perfect cube, or
- double the number.
Alice then takes the result, and has the same options. Play alternates, with the winner being the first player to reach exactly zero.
What are the possible starting numbers between $1$ and $11$ that Alice could choose to be sure that she can beat Bob?
And as a bonus (it's not essential to answer this, and may be tedious with pencil and paper): can Alice be sure of beating Bob if she chooses $12$ as the starting number?
game number-theory nim
edited May 1 at 21:11
Hugh
2,34311127
asked May 1 at 15:16
MichaelMaggsMichaelMaggs
47211
$endgroup$
Double or Take is a two-player number game. Alice starts by selecting any positive integer. Bob's options are to:
- subtract a positive perfect square
- subtract a positive perfect cube, or
- double the number.
Alice then takes the result, and has the same options. Play alternates, with the winner being the first player to reach exactly zero.
What are the possible starting numbers between $1$ and $11$ that Alice could choose to be sure that she can beat Bob?
And as a bonus (it's not essential to answer this, and may be tedious with pencil and paper): can Alice be sure of beating Bob if she chooses $12$ as the starting number?
game number-theory nim
game number-theory nim
edited May 1 at 21:11
Hugh
2,34311127
asked May 1 at 15:16
MichaelMaggsMichaelMaggs
47211
edited May 1 at 21:11
Hugh
2,34311127
asked May 1 at 15:16
MichaelMaggsMichaelMaggs
47211
edited May 1 at 21:11
Hugh
2,34311127
edited May 1 at 21:11
Hugh
2,34311127
edited May 1 at 21:11
Hugh
2,34311127
2,34311127
asked May 1 at 15:16
MichaelMaggsMichaelMaggs
47211
asked May 1 at 15:16
MichaelMaggsMichaelMaggs
47211
asked May 1 at 15:16
MichaelMaggsMichaelMaggs
47211
47211
$begingroup$
Source for the game: Martin Gardner in a 1970's Sci.Am. column, I think, though I'm now unable to locate it. If anyone can find the exact column I'd be very grateful.
$endgroup$
– MichaelMaggs
May 1 at 15:16
$begingroup$
"reaching zero" implies exactly zero? As in not going beyond zero to a negative integer?
$endgroup$
– BDrought
May 1 at 15:28
$begingroup$
That's right. Players are not allowed to end up with a negative number.
$endgroup$
– MichaelMaggs
May 1 at 15:30
$begingroup$
I do have the answer for 12, but as there are a lot of possible plays it would be lengthy to set them all out in full. And maybe not that interesting.
$endgroup$
– MichaelMaggs
May 1 at 15:47
$begingroup$
I'm still looking at the situation starting at 12, and you're not wrong about it being tedious with pencil and paper. How do you feel about computer-assisted solutions to this one?
$endgroup$
– Gareth McCaughan♦
May 1 at 16:21
|
show 3 more comments
$begingroup$
Source for the game: Martin Gardner in a 1970's Sci.Am. column, I think, though I'm now unable to locate it. If anyone can find the exact column I'd be very grateful.
$endgroup$
– MichaelMaggs
May 1 at 15:16
$begingroup$
"reaching zero" implies exactly zero? As in not going beyond zero to a negative integer?
$endgroup$
– BDrought
May 1 at 15:28
$begingroup$
That's right. Players are not allowed to end up with a negative number.
$endgroup$
– MichaelMaggs
May 1 at 15:30
$begingroup$
I do have the answer for 12, but as there are a lot of possible plays it would be lengthy to set them all out in full. And maybe not that interesting.
$endgroup$
– MichaelMaggs
May 1 at 15:47
$begingroup$
I'm still looking at the situation starting at 12, and you're not wrong about it being tedious with pencil and paper. How do you feel about computer-assisted solutions to this one?
$endgroup$
– Gareth McCaughan♦
May 1 at 16:21
$begingroup$
Source for the game: Martin Gardner in a 1970's Sci.Am. column, I think, though I'm now unable to locate it. If anyone can find the exact column I'd be very grateful.
$endgroup$
– MichaelMaggs
May 1 at 15:16
$begingroup$
Source for the game: Martin Gardner in a 1970's Sci.Am. column, I think, though I'm now unable to locate it. If anyone can find the exact column I'd be very grateful.
$endgroup$
– MichaelMaggs
May 1 at 15:16
$begingroup$
"reaching zero" implies exactly zero? As in not going beyond zero to a negative integer?
$endgroup$
– BDrought
May 1 at 15:28
$begingroup$
"reaching zero" implies exactly zero? As in not going beyond zero to a negative integer?
$endgroup$
– BDrought
May 1 at 15:28
$begingroup$
That's right. Players are not allowed to end up with a negative number.
$endgroup$
– MichaelMaggs
May 1 at 15:30
$begingroup$
That's right. Players are not allowed to end up with a negative number.
$endgroup$
– MichaelMaggs
May 1 at 15:30
$begingroup$
I do have the answer for 12, but as there are a lot of possible plays it would be lengthy to set them all out in full. And maybe not that interesting.
$endgroup$
– MichaelMaggs
May 1 at 15:47
$begingroup$
I do have the answer for 12, but as there are a lot of possible plays it would be lengthy to set them all out in full. And maybe not that interesting.
$endgroup$
– MichaelMaggs
May 1 at 15:47
$begingroup$
I'm still looking at the situation starting at 12, and you're not wrong about it being tedious with pencil and paper. How do you feel about computer-assisted solutions to this one?
$endgroup$
– Gareth McCaughan♦
May 1 at 16:21
$begingroup$
I'm still looking at the situation starting at 12, and you're not wrong about it being tedious with pencil and paper. How do you feel about computer-assisted solutions to this one?
$endgroup$
– Gareth McCaughan♦
May 1 at 16:21
|
show 3 more comments
3 Answers
3
active
oldest
votes
$begingroup$
Answer to the non-bonus part:
Next-player winning positions -- i.e., ones where Bob wins if he starts -- from 1 to 11 inclusive are 1,3,4,6,8,9,10,11. Next-player losing positions are 2,5,7. So Alice (who plays second) wins if she chooses 2, 5, or 7, but not if she chooses any other number from 1 to 11.
Proof:
Call a position "winning" or "losing" according to what happens with best play to the player whose move it is. (Or "drawing" if neither player can force a win and at least one can force the game to continue for ever.) Then we find, successively:
0 is losing (whoever just moved there already won the game).
1,4,8,9 are winning (you can move to 0 from any of them).
2 is losing (you can move from there only to 1,4, both of which are winning).
3,6,10 are winning (you can move to 2 from any of them).
5 is losing (you can move from there only to 1,4,10, all of which are winning).
14 is winning (you can move to 5 from it).
7 is losing (you can move from there only to 3,6,14, all of which are winning).
11 is winning (you can move to 7 from it).
Bonus part: From 12
it turns out -- I calculated this by computer -- that the sort of reasoning above is enough to determine that all positions you can get to from 12 other than 24 are next-player wins, and all positions you can get to from 24 other than 48 are next-player wins. Now, we have $12rightarrow24rightarrow48rightarrow12$. So, if Bob loses starting from 12 in particular he must lose when he moves to 24; if Alice wins starting at 24 then it must be by moving to 48 (since all her other moves from 24 lose); if Bob loses when starting at 48 then in particular he must lose by moving to 12, i.e., Alice must win when starting from 12. But this is a contradiction since we started out by supposing that 12 is a loss for the player moving there.
Hence
Alice cannot be sure of winning if she makes Bob move first from 12. He will move to 24, Alice definitely loses if she moves to anything other than 48, and then either Bob can win by doing something other than moving back to 12 (in which case he should) or he can't (in which case he should move back to 12, and then the best Alice can do is to go around the same loop again).
answered May 1 at 15:34
Gareth McCaughan♦Gareth McCaughan
71k3179276
$endgroup$
$begingroup$
I didn’t look at this answer when composing mine below, but I came to the same conclusion as @MichaelMaggs. Sorry, Gareth!
$endgroup$
– El-Guest
May 1 at 15:40
$begingroup$
@El-Guest Not sure what you're apologizing for.
$endgroup$
– Gareth McCaughan♦
May 1 at 15:41
$begingroup$
@GarethMcCaughan for (potentially) nipping your answer.
$endgroup$
– El-Guest
May 1 at 15:45
$begingroup$
Oh! I confess it hadn't occurred to me that that was a danger; I had an essentially correct answer some time before yours, after all. But of course OP can award the checkmark on whatever basis he pleases...
$endgroup$
– Gareth McCaughan♦
May 1 at 15:50
1
$begingroup$
... I've thrown away the bits of paper on which I did some hand calculations and restarted the computer on which I did some not-hand calculations without saving the relevant stuff. I might do it again and see whether indeed the other moves from 24 can be eliminated -- I think they might be.
$endgroup$
– Gareth McCaughan♦
May 7 at 8:33
|
show 5 more comments
$begingroup$
Let’s see: I assume that all numbers must be greater than or equal to zero, otherwise the possibilities become too painful. If that was the intention, I’ll look harder.
1
Bob subtracts 1, so Alice loses.
2
Bob can’t double, because that leads to 4 and a Bob-loss; he can’t subtract 1 because that leads to 1 and a Bob-loss. Therefore 2 is a winning number for Alice.
3
Bob subtracts 1, forcing a loss for Alice as above.
4
Bob subtracts 4 and Alice loses.
5
Bob can’t subtract either 1 or 4, since Alice can win. He also can’t double, because that makes 10 — then Alice subtracts 8 forcing a Bob-loss. Therefore 5 is a winning number for Alice.
6
Bob subtracts 4, forcing a loss for Alice as 2 is left.
7
If Bob subtracts 1, Alice subtracts 4, forcing a loss for Bob. If Bob subtracts 4, Alice subtracts 1, forcing a loss for Bob. Bob therefore has to double to 14. But Bob doubling to 14 means Alice can subtract 9 to get to 5, which forces a Bob-loss. Thus 7 is a winning number for Alice.
8
Bob subtracts 8 ($2^3$) and Alice loses.
9
Bob subtracts 4, forcing a loss for Alice as 5 is left.
10
Bob subtracts 8, leading to an Alice loss.
11
Bob subtracts 4, leading to an Alice loss.
Therefore the only starting numbers that win for Alice are
2, 5, and 7.
Bonus Part: 12
Bob has to double to 24 because he can’t get to 2, 5, or 7. Then Alice can’t subtract 1, because it’ll leave Bob with 23; he can subtract 16 and win. Alice can’t subtract 9, because it’ll leave Bob with 15; he can subtract 8 and win. Alice can’t subtract 8, because it’ll leave Bob with 16; he can subtract 9 and win. Alice can’t subtract 16, because it’ll leave Bob with 8; he can subtract 1 and win. Doubling here allows Bob to subtract 36 and leave Alice with 12. It appears then that this could create a stable loop solution where neither player wins. If Alice subtracts 4, Bob is left with 20. Bob can’t subtract 4, because leaving 16 allows Alice to subtract 9 and get to 7. Bob can’t subtract 9, because leaving 11 allows Alice to subtract 4 and get to 7. Bob can’t subtract 16 because it leaves 4 for Alice. However, subtracting 8 leaves an equilibrium standoff solution. This might be optimal...?
answered May 1 at 15:39
El-GuestEl-Guest
22.6k35295
$endgroup$
$begingroup$
That's correct for the main question but not for the bonus.
$endgroup$
– MichaelMaggs
2 days ago
add a comment |
$begingroup$
TL; DR:
Bob cannot force a win on 12, but has a nonlosing strategy.
We use a notation X-> Y to indicate that a move from number X to number Y is possible, and X->Win to indicate that the current player can force a win if the current number is X. Moving to a winning move is a losing move, as then the other player can win. Similarly, we have X-> Lose.
With this, we build a partial game tree. Formatting was a bit of an adventure, so... sorry for the mess?
Base cases:
Based no Gareth's (correct) answer, we have
1->Win
2->Lose
3->Win
4->Win
5->Lose
6->Win
7->Lose
8->Win
9->Win
10->Win
11->Win
14->Win
Turn 1:
The cubes and squares less than 12 are: 1, 4, 8, 9
We can infer the moves
12->11
12->8
12->4
12->3
All losing moves, which can be disregarded (as a rational player will ignore them)
Also, 12-> 24, which we will eventually find forces the next player to lose or enter a loop.
Turn 2:
Carrying on in this fashion to build a more complete game tree,
24-> 8 (Losing)
24-> 15 (Losing- see below)
24-> 16 (Losing, next player can remove 16)
24-> 20 (Losing, see below)
24-> 23 (Losing- see below)
24-> 48 (Loops to self or 12 in 2 moves, or to 12 in 1 move)
As all these moves are losing except for 48, the active player must move to 48
Turn 3:
15-> 7 (Win- Having found a winning move, we can infer that 15 is a winning position and terminate this branch)
20-> 19 (Winning- see below)
23 -> 7 (Winning)
We can subtract 1,4,8,9,16,25,27, or 36 from 48, allowing move
48 -> 12 (Loop, changing turn parity)
48 -> 39 (Loops to 12 in 1 move)
48 -> 40 (Loops to 24 in 1 move)
48 -> 44 (Losing)
48 -> 47 (Losing)
Turn 4:
19-> 3 (Losing)
19-> 10 (Losing)
19->11 (Losing)
19-> 15 (Losing)
19 -> 18 (Losing- see below)
19 -> 38 (Losing- see below)
All moves here are losing, so moving to 19 is a Winning move.
21 -> 5 (Winning)
23 -> 7 (Winning)
32 -> 7 (Winning)
39 -> 12 (Loop, retaining player parity)
40 -> 24 (Loop, changing player parity)
44 -> 17 (Win)
47 -> 5 (Win)
Turn 5:
We can subtract 1, 4, 8, 9, 16, 25, 27, or 36 from 38, allowing move
38 -> 2 (Winning)
18-> 2 (Winning)
13-> 5 (Winning)
15-> 7 (Winning)
17-> 1 (L)
17 -> 8 (L)
17 -> 9 (L)
17 -> 13 (L)
17 -> 16 (L)
17 -> 34 (L)
Turn 6:
34-> 7 (W)
answered May 1 at 18:01
MonkMonk
6414
$endgroup$
2
$begingroup$
$48 - 19 = 29$.
$endgroup$
– noedne
May 1 at 18:07
$begingroup$
Curses, foiled by arithmatic. I'll see if I can fix this real quick.
$endgroup$
– Monk
May 1 at 18:09
add a comment |
Your Answer
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "559"
;
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: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
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%2fpuzzling.stackexchange.com%2fquestions%2f83458%2fdouble-or-take-game%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Answer to the non-bonus part:
Next-player winning positions -- i.e., ones where Bob wins if he starts -- from 1 to 11 inclusive are 1,3,4,6,8,9,10,11. Next-player losing positions are 2,5,7. So Alice (who plays second) wins if she chooses 2, 5, or 7, but not if she chooses any other number from 1 to 11.
Proof:
Call a position "winning" or "losing" according to what happens with best play to the player whose move it is. (Or "drawing" if neither player can force a win and at least one can force the game to continue for ever.) Then we find, successively:
0 is losing (whoever just moved there already won the game).
1,4,8,9 are winning (you can move to 0 from any of them).
2 is losing (you can move from there only to 1,4, both of which are winning).
3,6,10 are winning (you can move to 2 from any of them).
5 is losing (you can move from there only to 1,4,10, all of which are winning).
14 is winning (you can move to 5 from it).
7 is losing (you can move from there only to 3,6,14, all of which are winning).
11 is winning (you can move to 7 from it).
Bonus part: From 12
it turns out -- I calculated this by computer -- that the sort of reasoning above is enough to determine that all positions you can get to from 12 other than 24 are next-player wins, and all positions you can get to from 24 other than 48 are next-player wins. Now, we have $12rightarrow24rightarrow48rightarrow12$. So, if Bob loses starting from 12 in particular he must lose when he moves to 24; if Alice wins starting at 24 then it must be by moving to 48 (since all her other moves from 24 lose); if Bob loses when starting at 48 then in particular he must lose by moving to 12, i.e., Alice must win when starting from 12. But this is a contradiction since we started out by supposing that 12 is a loss for the player moving there.
Hence
Alice cannot be sure of winning if she makes Bob move first from 12. He will move to 24, Alice definitely loses if she moves to anything other than 48, and then either Bob can win by doing something other than moving back to 12 (in which case he should) or he can't (in which case he should move back to 12, and then the best Alice can do is to go around the same loop again).
answered May 1 at 15:34
Gareth McCaughan♦Gareth McCaughan
71k3179276
$endgroup$
$begingroup$
I didn’t look at this answer when composing mine below, but I came to the same conclusion as @MichaelMaggs. Sorry, Gareth!
$endgroup$
– El-Guest
May 1 at 15:40
$begingroup$
@El-Guest Not sure what you're apologizing for.
$endgroup$
– Gareth McCaughan♦
May 1 at 15:41
$begingroup$
@GarethMcCaughan for (potentially) nipping your answer.
$endgroup$
– El-Guest
May 1 at 15:45
$begingroup$
Oh! I confess it hadn't occurred to me that that was a danger; I had an essentially correct answer some time before yours, after all. But of course OP can award the checkmark on whatever basis he pleases...
$endgroup$
– Gareth McCaughan♦
May 1 at 15:50
1
$begingroup$
... I've thrown away the bits of paper on which I did some hand calculations and restarted the computer on which I did some not-hand calculations without saving the relevant stuff. I might do it again and see whether indeed the other moves from 24 can be eliminated -- I think they might be.
$endgroup$
– Gareth McCaughan♦
May 7 at 8:33
|
show 5 more comments
$begingroup$
Answer to the non-bonus part:
Next-player winning positions -- i.e., ones where Bob wins if he starts -- from 1 to 11 inclusive are 1,3,4,6,8,9,10,11. Next-player losing positions are 2,5,7. So Alice (who plays second) wins if she chooses 2, 5, or 7, but not if she chooses any other number from 1 to 11.
Proof:
Call a position "winning" or "losing" according to what happens with best play to the player whose move it is. (Or "drawing" if neither player can force a win and at least one can force the game to continue for ever.) Then we find, successively:
0 is losing (whoever just moved there already won the game).
1,4,8,9 are winning (you can move to 0 from any of them).
2 is losing (you can move from there only to 1,4, both of which are winning).
3,6,10 are winning (you can move to 2 from any of them).
5 is losing (you can move from there only to 1,4,10, all of which are winning).
14 is winning (you can move to 5 from it).
7 is losing (you can move from there only to 3,6,14, all of which are winning).
11 is winning (you can move to 7 from it).
Bonus part: From 12
it turns out -- I calculated this by computer -- that the sort of reasoning above is enough to determine that all positions you can get to from 12 other than 24 are next-player wins, and all positions you can get to from 24 other than 48 are next-player wins. Now, we have $12rightarrow24rightarrow48rightarrow12$. So, if Bob loses starting from 12 in particular he must lose when he moves to 24; if Alice wins starting at 24 then it must be by moving to 48 (since all her other moves from 24 lose); if Bob loses when starting at 48 then in particular he must lose by moving to 12, i.e., Alice must win when starting from 12. But this is a contradiction since we started out by supposing that 12 is a loss for the player moving there.
Hence
Alice cannot be sure of winning if she makes Bob move first from 12. He will move to 24, Alice definitely loses if she moves to anything other than 48, and then either Bob can win by doing something other than moving back to 12 (in which case he should) or he can't (in which case he should move back to 12, and then the best Alice can do is to go around the same loop again).
answered May 1 at 15:34
Gareth McCaughan♦Gareth McCaughan
71k3179276
$endgroup$
$begingroup$
I didn’t look at this answer when composing mine below, but I came to the same conclusion as @MichaelMaggs. Sorry, Gareth!
$endgroup$
– El-Guest
May 1 at 15:40
$begingroup$
@El-Guest Not sure what you're apologizing for.
$endgroup$
– Gareth McCaughan♦
May 1 at 15:41
$begingroup$
@GarethMcCaughan for (potentially) nipping your answer.
$endgroup$
– El-Guest
May 1 at 15:45
$begingroup$
Oh! I confess it hadn't occurred to me that that was a danger; I had an essentially correct answer some time before yours, after all. But of course OP can award the checkmark on whatever basis he pleases...
$endgroup$
– Gareth McCaughan♦
May 1 at 15:50
1
$begingroup$
... I've thrown away the bits of paper on which I did some hand calculations and restarted the computer on which I did some not-hand calculations without saving the relevant stuff. I might do it again and see whether indeed the other moves from 24 can be eliminated -- I think they might be.
$endgroup$
– Gareth McCaughan♦
May 7 at 8:33
|
show 5 more comments
$begingroup$
Answer to the non-bonus part:
Next-player winning positions -- i.e., ones where Bob wins if he starts -- from 1 to 11 inclusive are 1,3,4,6,8,9,10,11. Next-player losing positions are 2,5,7. So Alice (who plays second) wins if she chooses 2, 5, or 7, but not if she chooses any other number from 1 to 11.
Proof:
Call a position "winning" or "losing" according to what happens with best play to the player whose move it is. (Or "drawing" if neither player can force a win and at least one can force the game to continue for ever.) Then we find, successively:
0 is losing (whoever just moved there already won the game).
1,4,8,9 are winning (you can move to 0 from any of them).
2 is losing (you can move from there only to 1,4, both of which are winning).
3,6,10 are winning (you can move to 2 from any of them).
5 is losing (you can move from there only to 1,4,10, all of which are winning).
14 is winning (you can move to 5 from it).
7 is losing (you can move from there only to 3,6,14, all of which are winning).
11 is winning (you can move to 7 from it).
Bonus part: From 12
it turns out -- I calculated this by computer -- that the sort of reasoning above is enough to determine that all positions you can get to from 12 other than 24 are next-player wins, and all positions you can get to from 24 other than 48 are next-player wins. Now, we have $12rightarrow24rightarrow48rightarrow12$. So, if Bob loses starting from 12 in particular he must lose when he moves to 24; if Alice wins starting at 24 then it must be by moving to 48 (since all her other moves from 24 lose); if Bob loses when starting at 48 then in particular he must lose by moving to 12, i.e., Alice must win when starting from 12. But this is a contradiction since we started out by supposing that 12 is a loss for the player moving there.
Hence
Alice cannot be sure of winning if she makes Bob move first from 12. He will move to 24, Alice definitely loses if she moves to anything other than 48, and then either Bob can win by doing something other than moving back to 12 (in which case he should) or he can't (in which case he should move back to 12, and then the best Alice can do is to go around the same loop again).
answered May 1 at 15:34
Gareth McCaughan♦Gareth McCaughan
71k3179276
$endgroup$
Answer to the non-bonus part:
Next-player winning positions -- i.e., ones where Bob wins if he starts -- from 1 to 11 inclusive are 1,3,4,6,8,9,10,11. Next-player losing positions are 2,5,7. So Alice (who plays second) wins if she chooses 2, 5, or 7, but not if she chooses any other number from 1 to 11.
Proof:
Call a position "winning" or "losing" according to what happens with best play to the player whose move it is. (Or "drawing" if neither player can force a win and at least one can force the game to continue for ever.) Then we find, successively:
0 is losing (whoever just moved there already won the game).
1,4,8,9 are winning (you can move to 0 from any of them).
2 is losing (you can move from there only to 1,4, both of which are winning).
3,6,10 are winning (you can move to 2 from any of them).
5 is losing (you can move from there only to 1,4,10, all of which are winning).
14 is winning (you can move to 5 from it).
7 is losing (you can move from there only to 3,6,14, all of which are winning).
11 is winning (you can move to 7 from it).
Bonus part: From 12
it turns out -- I calculated this by computer -- that the sort of reasoning above is enough to determine that all positions you can get to from 12 other than 24 are next-player wins, and all positions you can get to from 24 other than 48 are next-player wins. Now, we have $12rightarrow24rightarrow48rightarrow12$. So, if Bob loses starting from 12 in particular he must lose when he moves to 24; if Alice wins starting at 24 then it must be by moving to 48 (since all her other moves from 24 lose); if Bob loses when starting at 48 then in particular he must lose by moving to 12, i.e., Alice must win when starting from 12. But this is a contradiction since we started out by supposing that 12 is a loss for the player moving there.
Hence
Alice cannot be sure of winning if she makes Bob move first from 12. He will move to 24, Alice definitely loses if she moves to anything other than 48, and then either Bob can win by doing something other than moving back to 12 (in which case he should) or he can't (in which case he should move back to 12, and then the best Alice can do is to go around the same loop again).
answered May 1 at 15:34
Gareth McCaughan♦Gareth McCaughan
71k3179276
edited 2 days ago
answered May 1 at 15:34
Gareth McCaughan♦Gareth McCaughan
71k3179276
answered May 1 at 15:34
Gareth McCaughan♦Gareth McCaughan
71k3179276
answered May 1 at 15:34
Gareth McCaughan♦Gareth McCaughan
71k3179276
71k3179276
$begingroup$
I didn’t look at this answer when composing mine below, but I came to the same conclusion as @MichaelMaggs. Sorry, Gareth!
$endgroup$
– El-Guest
May 1 at 15:40
$begingroup$
@El-Guest Not sure what you're apologizing for.
$endgroup$
– Gareth McCaughan♦
May 1 at 15:41
$begingroup$
@GarethMcCaughan for (potentially) nipping your answer.
$endgroup$
– El-Guest
May 1 at 15:45
$begingroup$
Oh! I confess it hadn't occurred to me that that was a danger; I had an essentially correct answer some time before yours, after all. But of course OP can award the checkmark on whatever basis he pleases...
$endgroup$
– Gareth McCaughan♦
May 1 at 15:50
1
$begingroup$
... I've thrown away the bits of paper on which I did some hand calculations and restarted the computer on which I did some not-hand calculations without saving the relevant stuff. I might do it again and see whether indeed the other moves from 24 can be eliminated -- I think they might be.
$endgroup$
– Gareth McCaughan♦
May 7 at 8:33
|
show 5 more comments
$begingroup$
I didn’t look at this answer when composing mine below, but I came to the same conclusion as @MichaelMaggs. Sorry, Gareth!
$endgroup$
– El-Guest
May 1 at 15:40
$begingroup$
@El-Guest Not sure what you're apologizing for.
$endgroup$
– Gareth McCaughan♦
May 1 at 15:41
$begingroup$
@GarethMcCaughan for (potentially) nipping your answer.
$endgroup$
– El-Guest
May 1 at 15:45
$begingroup$
Oh! I confess it hadn't occurred to me that that was a danger; I had an essentially correct answer some time before yours, after all. But of course OP can award the checkmark on whatever basis he pleases...
$endgroup$
– Gareth McCaughan♦
May 1 at 15:50
1
$begingroup$
... I've thrown away the bits of paper on which I did some hand calculations and restarted the computer on which I did some not-hand calculations without saving the relevant stuff. I might do it again and see whether indeed the other moves from 24 can be eliminated -- I think they might be.
$endgroup$
– Gareth McCaughan♦
May 7 at 8:33
$begingroup$
I didn’t look at this answer when composing mine below, but I came to the same conclusion as @MichaelMaggs. Sorry, Gareth!
$endgroup$
– El-Guest
May 1 at 15:40
$begingroup$
I didn’t look at this answer when composing mine below, but I came to the same conclusion as @MichaelMaggs. Sorry, Gareth!
$endgroup$
– El-Guest
May 1 at 15:40
$begingroup$
@El-Guest Not sure what you're apologizing for.
$endgroup$
– Gareth McCaughan♦
May 1 at 15:41
$begingroup$
@El-Guest Not sure what you're apologizing for.
$endgroup$
– Gareth McCaughan♦
May 1 at 15:41
$begingroup$
@GarethMcCaughan for (potentially) nipping your answer.
$endgroup$
– El-Guest
May 1 at 15:45
$begingroup$
@GarethMcCaughan for (potentially) nipping your answer.
$endgroup$
– El-Guest
May 1 at 15:45
$begingroup$
Oh! I confess it hadn't occurred to me that that was a danger; I had an essentially correct answer some time before yours, after all. But of course OP can award the checkmark on whatever basis he pleases...
$endgroup$
– Gareth McCaughan♦
May 1 at 15:50
$begingroup$
Oh! I confess it hadn't occurred to me that that was a danger; I had an essentially correct answer some time before yours, after all. But of course OP can award the checkmark on whatever basis he pleases...
$endgroup$
– Gareth McCaughan♦
May 1 at 15:50
1
1
$begingroup$
... I've thrown away the bits of paper on which I did some hand calculations and restarted the computer on which I did some not-hand calculations without saving the relevant stuff. I might do it again and see whether indeed the other moves from 24 can be eliminated -- I think they might be.
$endgroup$
– Gareth McCaughan♦
May 7 at 8:33
$begingroup$
... I've thrown away the bits of paper on which I did some hand calculations and restarted the computer on which I did some not-hand calculations without saving the relevant stuff. I might do it again and see whether indeed the other moves from 24 can be eliminated -- I think they might be.
$endgroup$
– Gareth McCaughan♦
May 7 at 8:33
|
show 5 more comments
$begingroup$
Let’s see: I assume that all numbers must be greater than or equal to zero, otherwise the possibilities become too painful. If that was the intention, I’ll look harder.
1
Bob subtracts 1, so Alice loses.
2
Bob can’t double, because that leads to 4 and a Bob-loss; he can’t subtract 1 because that leads to 1 and a Bob-loss. Therefore 2 is a winning number for Alice.
3
Bob subtracts 1, forcing a loss for Alice as above.
4
Bob subtracts 4 and Alice loses.
5
Bob can’t subtract either 1 or 4, since Alice can win. He also can’t double, because that makes 10 — then Alice subtracts 8 forcing a Bob-loss. Therefore 5 is a winning number for Alice.
6
Bob subtracts 4, forcing a loss for Alice as 2 is left.
7
If Bob subtracts 1, Alice subtracts 4, forcing a loss for Bob. If Bob subtracts 4, Alice subtracts 1, forcing a loss for Bob. Bob therefore has to double to 14. But Bob doubling to 14 means Alice can subtract 9 to get to 5, which forces a Bob-loss. Thus 7 is a winning number for Alice.
8
Bob subtracts 8 ($2^3$) and Alice loses.
9
Bob subtracts 4, forcing a loss for Alice as 5 is left.
10
Bob subtracts 8, leading to an Alice loss.
11
Bob subtracts 4, leading to an Alice loss.
Therefore the only starting numbers that win for Alice are
2, 5, and 7.
Bonus Part: 12
Bob has to double to 24 because he can’t get to 2, 5, or 7. Then Alice can’t subtract 1, because it’ll leave Bob with 23; he can subtract 16 and win. Alice can’t subtract 9, because it’ll leave Bob with 15; he can subtract 8 and win. Alice can’t subtract 8, because it’ll leave Bob with 16; he can subtract 9 and win. Alice can’t subtract 16, because it’ll leave Bob with 8; he can subtract 1 and win. Doubling here allows Bob to subtract 36 and leave Alice with 12. It appears then that this could create a stable loop solution where neither player wins. If Alice subtracts 4, Bob is left with 20. Bob can’t subtract 4, because leaving 16 allows Alice to subtract 9 and get to 7. Bob can’t subtract 9, because leaving 11 allows Alice to subtract 4 and get to 7. Bob can’t subtract 16 because it leaves 4 for Alice. However, subtracting 8 leaves an equilibrium standoff solution. This might be optimal...?
answered May 1 at 15:39
El-GuestEl-Guest
22.6k35295
$endgroup$
$begingroup$
That's correct for the main question but not for the bonus.
$endgroup$
– MichaelMaggs
2 days ago
add a comment |
$begingroup$
Let’s see: I assume that all numbers must be greater than or equal to zero, otherwise the possibilities become too painful. If that was the intention, I’ll look harder.
1
Bob subtracts 1, so Alice loses.
2
Bob can’t double, because that leads to 4 and a Bob-loss; he can’t subtract 1 because that leads to 1 and a Bob-loss. Therefore 2 is a winning number for Alice.
3
Bob subtracts 1, forcing a loss for Alice as above.
4
Bob subtracts 4 and Alice loses.
5
Bob can’t subtract either 1 or 4, since Alice can win. He also can’t double, because that makes 10 — then Alice subtracts 8 forcing a Bob-loss. Therefore 5 is a winning number for Alice.
6
Bob subtracts 4, forcing a loss for Alice as 2 is left.
7
If Bob subtracts 1, Alice subtracts 4, forcing a loss for Bob. If Bob subtracts 4, Alice subtracts 1, forcing a loss for Bob. Bob therefore has to double to 14. But Bob doubling to 14 means Alice can subtract 9 to get to 5, which forces a Bob-loss. Thus 7 is a winning number for Alice.
8
Bob subtracts 8 ($2^3$) and Alice loses.
9
Bob subtracts 4, forcing a loss for Alice as 5 is left.
10
Bob subtracts 8, leading to an Alice loss.
11
Bob subtracts 4, leading to an Alice loss.
Therefore the only starting numbers that win for Alice are
2, 5, and 7.
Bonus Part: 12
Bob has to double to 24 because he can’t get to 2, 5, or 7. Then Alice can’t subtract 1, because it’ll leave Bob with 23; he can subtract 16 and win. Alice can’t subtract 9, because it’ll leave Bob with 15; he can subtract 8 and win. Alice can’t subtract 8, because it’ll leave Bob with 16; he can subtract 9 and win. Alice can’t subtract 16, because it’ll leave Bob with 8; he can subtract 1 and win. Doubling here allows Bob to subtract 36 and leave Alice with 12. It appears then that this could create a stable loop solution where neither player wins. If Alice subtracts 4, Bob is left with 20. Bob can’t subtract 4, because leaving 16 allows Alice to subtract 9 and get to 7. Bob can’t subtract 9, because leaving 11 allows Alice to subtract 4 and get to 7. Bob can’t subtract 16 because it leaves 4 for Alice. However, subtracting 8 leaves an equilibrium standoff solution. This might be optimal...?
answered May 1 at 15:39
El-GuestEl-Guest
22.6k35295
$endgroup$
$begingroup$
That's correct for the main question but not for the bonus.
$endgroup$
– MichaelMaggs
2 days ago
add a comment |
$begingroup$
Let’s see: I assume that all numbers must be greater than or equal to zero, otherwise the possibilities become too painful. If that was the intention, I’ll look harder.
1
Bob subtracts 1, so Alice loses.
2
Bob can’t double, because that leads to 4 and a Bob-loss; he can’t subtract 1 because that leads to 1 and a Bob-loss. Therefore 2 is a winning number for Alice.
3
Bob subtracts 1, forcing a loss for Alice as above.
4
Bob subtracts 4 and Alice loses.
5
Bob can’t subtract either 1 or 4, since Alice can win. He also can’t double, because that makes 10 — then Alice subtracts 8 forcing a Bob-loss. Therefore 5 is a winning number for Alice.
6
Bob subtracts 4, forcing a loss for Alice as 2 is left.
7
If Bob subtracts 1, Alice subtracts 4, forcing a loss for Bob. If Bob subtracts 4, Alice subtracts 1, forcing a loss for Bob. Bob therefore has to double to 14. But Bob doubling to 14 means Alice can subtract 9 to get to 5, which forces a Bob-loss. Thus 7 is a winning number for Alice.
8
Bob subtracts 8 ($2^3$) and Alice loses.
9
Bob subtracts 4, forcing a loss for Alice as 5 is left.
10
Bob subtracts 8, leading to an Alice loss.
11
Bob subtracts 4, leading to an Alice loss.
Therefore the only starting numbers that win for Alice are
2, 5, and 7.
Bonus Part: 12
Bob has to double to 24 because he can’t get to 2, 5, or 7. Then Alice can’t subtract 1, because it’ll leave Bob with 23; he can subtract 16 and win. Alice can’t subtract 9, because it’ll leave Bob with 15; he can subtract 8 and win. Alice can’t subtract 8, because it’ll leave Bob with 16; he can subtract 9 and win. Alice can’t subtract 16, because it’ll leave Bob with 8; he can subtract 1 and win. Doubling here allows Bob to subtract 36 and leave Alice with 12. It appears then that this could create a stable loop solution where neither player wins. If Alice subtracts 4, Bob is left with 20. Bob can’t subtract 4, because leaving 16 allows Alice to subtract 9 and get to 7. Bob can’t subtract 9, because leaving 11 allows Alice to subtract 4 and get to 7. Bob can’t subtract 16 because it leaves 4 for Alice. However, subtracting 8 leaves an equilibrium standoff solution. This might be optimal...?
answered May 1 at 15:39
El-GuestEl-Guest
22.6k35295
$endgroup$
Let’s see: I assume that all numbers must be greater than or equal to zero, otherwise the possibilities become too painful. If that was the intention, I’ll look harder.
1
Bob subtracts 1, so Alice loses.
2
Bob can’t double, because that leads to 4 and a Bob-loss; he can’t subtract 1 because that leads to 1 and a Bob-loss. Therefore 2 is a winning number for Alice.
3
Bob subtracts 1, forcing a loss for Alice as above.
4
Bob subtracts 4 and Alice loses.
5
Bob can’t subtract either 1 or 4, since Alice can win. He also can’t double, because that makes 10 — then Alice subtracts 8 forcing a Bob-loss. Therefore 5 is a winning number for Alice.
6
Bob subtracts 4, forcing a loss for Alice as 2 is left.
7
If Bob subtracts 1, Alice subtracts 4, forcing a loss for Bob. If Bob subtracts 4, Alice subtracts 1, forcing a loss for Bob. Bob therefore has to double to 14. But Bob doubling to 14 means Alice can subtract 9 to get to 5, which forces a Bob-loss. Thus 7 is a winning number for Alice.
8
Bob subtracts 8 ($2^3$) and Alice loses.
9
Bob subtracts 4, forcing a loss for Alice as 5 is left.
10
Bob subtracts 8, leading to an Alice loss.
11
Bob subtracts 4, leading to an Alice loss.
Therefore the only starting numbers that win for Alice are
2, 5, and 7.
Bonus Part: 12
Bob has to double to 24 because he can’t get to 2, 5, or 7. Then Alice can’t subtract 1, because it’ll leave Bob with 23; he can subtract 16 and win. Alice can’t subtract 9, because it’ll leave Bob with 15; he can subtract 8 and win. Alice can’t subtract 8, because it’ll leave Bob with 16; he can subtract 9 and win. Alice can’t subtract 16, because it’ll leave Bob with 8; he can subtract 1 and win. Doubling here allows Bob to subtract 36 and leave Alice with 12. It appears then that this could create a stable loop solution where neither player wins. If Alice subtracts 4, Bob is left with 20. Bob can’t subtract 4, because leaving 16 allows Alice to subtract 9 and get to 7. Bob can’t subtract 9, because leaving 11 allows Alice to subtract 4 and get to 7. Bob can’t subtract 16 because it leaves 4 for Alice. However, subtracting 8 leaves an equilibrium standoff solution. This might be optimal...?
answered May 1 at 15:39
El-GuestEl-Guest
22.6k35295
edited May 1 at 16:33
answered May 1 at 15:39
El-GuestEl-Guest
22.6k35295
answered May 1 at 15:39
El-GuestEl-Guest
22.6k35295
answered May 1 at 15:39
El-GuestEl-Guest
22.6k35295
22.6k35295
$begingroup$
That's correct for the main question but not for the bonus.
$endgroup$
– MichaelMaggs
2 days ago
add a comment |
$begingroup$
That's correct for the main question but not for the bonus.
$endgroup$
– MichaelMaggs
2 days ago
$begingroup$
That's correct for the main question but not for the bonus.
$endgroup$
– MichaelMaggs
2 days ago
$begingroup$
That's correct for the main question but not for the bonus.
$endgroup$
– MichaelMaggs
2 days ago
add a comment |
$begingroup$
TL; DR:
Bob cannot force a win on 12, but has a nonlosing strategy.
We use a notation X-> Y to indicate that a move from number X to number Y is possible, and X->Win to indicate that the current player can force a win if the current number is X. Moving to a winning move is a losing move, as then the other player can win. Similarly, we have X-> Lose.
With this, we build a partial game tree. Formatting was a bit of an adventure, so... sorry for the mess?
Base cases:
Based no Gareth's (correct) answer, we have
1->Win
2->Lose
3->Win
4->Win
5->Lose
6->Win
7->Lose
8->Win
9->Win
10->Win
11->Win
14->Win
Turn 1:
The cubes and squares less than 12 are: 1, 4, 8, 9
We can infer the moves
12->11
12->8
12->4
12->3
All losing moves, which can be disregarded (as a rational player will ignore them)
Also, 12-> 24, which we will eventually find forces the next player to lose or enter a loop.
Turn 2:
Carrying on in this fashion to build a more complete game tree,
24-> 8 (Losing)
24-> 15 (Losing- see below)
24-> 16 (Losing, next player can remove 16)
24-> 20 (Losing, see below)
24-> 23 (Losing- see below)
24-> 48 (Loops to self or 12 in 2 moves, or to 12 in 1 move)
As all these moves are losing except for 48, the active player must move to 48
Turn 3:
15-> 7 (Win- Having found a winning move, we can infer that 15 is a winning position and terminate this branch)
20-> 19 (Winning- see below)
23 -> 7 (Winning)
We can subtract 1,4,8,9,16,25,27, or 36 from 48, allowing move
48 -> 12 (Loop, changing turn parity)
48 -> 39 (Loops to 12 in 1 move)
48 -> 40 (Loops to 24 in 1 move)
48 -> 44 (Losing)
48 -> 47 (Losing)
Turn 4:
19-> 3 (Losing)
19-> 10 (Losing)
19->11 (Losing)
19-> 15 (Losing)
19 -> 18 (Losing- see below)
19 -> 38 (Losing- see below)
All moves here are losing, so moving to 19 is a Winning move.
21 -> 5 (Winning)
23 -> 7 (Winning)
32 -> 7 (Winning)
39 -> 12 (Loop, retaining player parity)
40 -> 24 (Loop, changing player parity)
44 -> 17 (Win)
47 -> 5 (Win)
Turn 5:
We can subtract 1, 4, 8, 9, 16, 25, 27, or 36 from 38, allowing move
38 -> 2 (Winning)
18-> 2 (Winning)
13-> 5 (Winning)
15-> 7 (Winning)
17-> 1 (L)
17 -> 8 (L)
17 -> 9 (L)
17 -> 13 (L)
17 -> 16 (L)
17 -> 34 (L)
Turn 6:
34-> 7 (W)
answered May 1 at 18:01
MonkMonk
6414
$endgroup$
2
$begingroup$
$48 - 19 = 29$.
$endgroup$
– noedne
May 1 at 18:07
$begingroup$
Curses, foiled by arithmatic. I'll see if I can fix this real quick.
$endgroup$
– Monk
May 1 at 18:09
add a comment |
$begingroup$
TL; DR:
Bob cannot force a win on 12, but has a nonlosing strategy.
We use a notation X-> Y to indicate that a move from number X to number Y is possible, and X->Win to indicate that the current player can force a win if the current number is X. Moving to a winning move is a losing move, as then the other player can win. Similarly, we have X-> Lose.
With this, we build a partial game tree. Formatting was a bit of an adventure, so... sorry for the mess?
Base cases:
Based no Gareth's (correct) answer, we have
1->Win
2->Lose
3->Win
4->Win
5->Lose
6->Win
7->Lose
8->Win
9->Win
10->Win
11->Win
14->Win
Turn 1:
The cubes and squares less than 12 are: 1, 4, 8, 9
We can infer the moves
12->11
12->8
12->4
12->3
All losing moves, which can be disregarded (as a rational player will ignore them)
Also, 12-> 24, which we will eventually find forces the next player to lose or enter a loop.
Turn 2:
Carrying on in this fashion to build a more complete game tree,
24-> 8 (Losing)
24-> 15 (Losing- see below)
24-> 16 (Losing, next player can remove 16)
24-> 20 (Losing, see below)
24-> 23 (Losing- see below)
24-> 48 (Loops to self or 12 in 2 moves, or to 12 in 1 move)
As all these moves are losing except for 48, the active player must move to 48
Turn 3:
15-> 7 (Win- Having found a winning move, we can infer that 15 is a winning position and terminate this branch)
20-> 19 (Winning- see below)
23 -> 7 (Winning)
We can subtract 1,4,8,9,16,25,27, or 36 from 48, allowing move
48 -> 12 (Loop, changing turn parity)
48 -> 39 (Loops to 12 in 1 move)
48 -> 40 (Loops to 24 in 1 move)
48 -> 44 (Losing)
48 -> 47 (Losing)
Turn 4:
19-> 3 (Losing)
19-> 10 (Losing)
19->11 (Losing)
19-> 15 (Losing)
19 -> 18 (Losing- see below)
19 -> 38 (Losing- see below)
All moves here are losing, so moving to 19 is a Winning move.
21 -> 5 (Winning)
23 -> 7 (Winning)
32 -> 7 (Winning)
39 -> 12 (Loop, retaining player parity)
40 -> 24 (Loop, changing player parity)
44 -> 17 (Win)
47 -> 5 (Win)
Turn 5:
We can subtract 1, 4, 8, 9, 16, 25, 27, or 36 from 38, allowing move
38 -> 2 (Winning)
18-> 2 (Winning)
13-> 5 (Winning)
15-> 7 (Winning)
17-> 1 (L)
17 -> 8 (L)
17 -> 9 (L)
17 -> 13 (L)
17 -> 16 (L)
17 -> 34 (L)
Turn 6:
34-> 7 (W)
answered May 1 at 18:01
MonkMonk
6414
$endgroup$
2
$begingroup$
$48 - 19 = 29$.
$endgroup$
– noedne
May 1 at 18:07
$begingroup$
Curses, foiled by arithmatic. I'll see if I can fix this real quick.
$endgroup$
– Monk
May 1 at 18:09
add a comment |
$begingroup$
TL; DR:
Bob cannot force a win on 12, but has a nonlosing strategy.
We use a notation X-> Y to indicate that a move from number X to number Y is possible, and X->Win to indicate that the current player can force a win if the current number is X. Moving to a winning move is a losing move, as then the other player can win. Similarly, we have X-> Lose.
With this, we build a partial game tree. Formatting was a bit of an adventure, so... sorry for the mess?
Base cases:
Based no Gareth's (correct) answer, we have
1->Win
2->Lose
3->Win
4->Win
5->Lose
6->Win
7->Lose
8->Win
9->Win
10->Win
11->Win
14->Win
Turn 1:
The cubes and squares less than 12 are: 1, 4, 8, 9
We can infer the moves
12->11
12->8
12->4
12->3
All losing moves, which can be disregarded (as a rational player will ignore them)
Also, 12-> 24, which we will eventually find forces the next player to lose or enter a loop.
Turn 2:
Carrying on in this fashion to build a more complete game tree,
24-> 8 (Losing)
24-> 15 (Losing- see below)
24-> 16 (Losing, next player can remove 16)
24-> 20 (Losing, see below)
24-> 23 (Losing- see below)
24-> 48 (Loops to self or 12 in 2 moves, or to 12 in 1 move)
As all these moves are losing except for 48, the active player must move to 48
Turn 3:
15-> 7 (Win- Having found a winning move, we can infer that 15 is a winning position and terminate this branch)
20-> 19 (Winning- see below)
23 -> 7 (Winning)
We can subtract 1,4,8,9,16,25,27, or 36 from 48, allowing move
48 -> 12 (Loop, changing turn parity)
48 -> 39 (Loops to 12 in 1 move)
48 -> 40 (Loops to 24 in 1 move)
48 -> 44 (Losing)
48 -> 47 (Losing)
Turn 4:
19-> 3 (Losing)
19-> 10 (Losing)
19->11 (Losing)
19-> 15 (Losing)
19 -> 18 (Losing- see below)
19 -> 38 (Losing- see below)
All moves here are losing, so moving to 19 is a Winning move.
21 -> 5 (Winning)
23 -> 7 (Winning)
32 -> 7 (Winning)
39 -> 12 (Loop, retaining player parity)
40 -> 24 (Loop, changing player parity)
44 -> 17 (Win)
47 -> 5 (Win)
Turn 5:
We can subtract 1, 4, 8, 9, 16, 25, 27, or 36 from 38, allowing move
38 -> 2 (Winning)
18-> 2 (Winning)
13-> 5 (Winning)
15-> 7 (Winning)
17-> 1 (L)
17 -> 8 (L)
17 -> 9 (L)
17 -> 13 (L)
17 -> 16 (L)
17 -> 34 (L)
Turn 6:
34-> 7 (W)
answered May 1 at 18:01
MonkMonk
6414
$endgroup$
TL; DR:
Bob cannot force a win on 12, but has a nonlosing strategy.
We use a notation X-> Y to indicate that a move from number X to number Y is possible, and X->Win to indicate that the current player can force a win if the current number is X. Moving to a winning move is a losing move, as then the other player can win. Similarly, we have X-> Lose.
With this, we build a partial game tree. Formatting was a bit of an adventure, so... sorry for the mess?
Base cases:
Based no Gareth's (correct) answer, we have
1->Win
2->Lose
3->Win
4->Win
5->Lose
6->Win
7->Lose
8->Win
9->Win
10->Win
11->Win
14->Win
Turn 1:
The cubes and squares less than 12 are: 1, 4, 8, 9
We can infer the moves
12->11
12->8
12->4
12->3
All losing moves, which can be disregarded (as a rational player will ignore them)
Also, 12-> 24, which we will eventually find forces the next player to lose or enter a loop.
Turn 2:
Carrying on in this fashion to build a more complete game tree,
24-> 8 (Losing)
24-> 15 (Losing- see below)
24-> 16 (Losing, next player can remove 16)
24-> 20 (Losing, see below)
24-> 23 (Losing- see below)
24-> 48 (Loops to self or 12 in 2 moves, or to 12 in 1 move)
As all these moves are losing except for 48, the active player must move to 48
Turn 3:
15-> 7 (Win- Having found a winning move, we can infer that 15 is a winning position and terminate this branch)
20-> 19 (Winning- see below)
23 -> 7 (Winning)
We can subtract 1,4,8,9,16,25,27, or 36 from 48, allowing move
48 -> 12 (Loop, changing turn parity)
48 -> 39 (Loops to 12 in 1 move)
48 -> 40 (Loops to 24 in 1 move)
48 -> 44 (Losing)
48 -> 47 (Losing)
Turn 4:
19-> 3 (Losing)
19-> 10 (Losing)
19->11 (Losing)
19-> 15 (Losing)
19 -> 18 (Losing- see below)
19 -> 38 (Losing- see below)
All moves here are losing, so moving to 19 is a Winning move.
21 -> 5 (Winning)
23 -> 7 (Winning)
32 -> 7 (Winning)
39 -> 12 (Loop, retaining player parity)
40 -> 24 (Loop, changing player parity)
44 -> 17 (Win)
47 -> 5 (Win)
Turn 5:
We can subtract 1, 4, 8, 9, 16, 25, 27, or 36 from 38, allowing move
38 -> 2 (Winning)
18-> 2 (Winning)
13-> 5 (Winning)
15-> 7 (Winning)
17-> 1 (L)
17 -> 8 (L)
17 -> 9 (L)
17 -> 13 (L)
17 -> 16 (L)
17 -> 34 (L)
Turn 6:
34-> 7 (W)
answered May 1 at 18:01
MonkMonk
6414
edited May 1 at 19:55
answered May 1 at 18:01
MonkMonk
6414
answered May 1 at 18:01
MonkMonk
6414
answered May 1 at 18:01
MonkMonk
6414
6414
2
$begingroup$
$48 - 19 = 29$.
$endgroup$
– noedne
May 1 at 18:07
$begingroup$
Curses, foiled by arithmatic. I'll see if I can fix this real quick.
$endgroup$
– Monk
May 1 at 18:09
add a comment |
2
$begingroup$
$48 - 19 = 29$.
$endgroup$
– noedne
May 1 at 18:07
$begingroup$
Curses, foiled by arithmatic. I'll see if I can fix this real quick.
$endgroup$
– Monk
May 1 at 18:09
2
2
$begingroup$
$48 - 19 = 29$.
$endgroup$
– noedne
May 1 at 18:07
$begingroup$
$48 - 19 = 29$.
$endgroup$
– noedne
May 1 at 18:07
$begingroup$
Curses, foiled by arithmatic. I'll see if I can fix this real quick.
$endgroup$
– Monk
May 1 at 18:09
$begingroup$
Curses, foiled by arithmatic. I'll see if I can fix this real quick.
$endgroup$
– Monk
May 1 at 18:09
add a comment |
Thanks for contributing an answer to Puzzling 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%2fpuzzling.stackexchange.com%2fquestions%2f83458%2fdouble-or-take-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
$begingroup$
Source for the game: Martin Gardner in a 1970's Sci.Am. column, I think, though I'm now unable to locate it. If anyone can find the exact column I'd be very grateful.
$endgroup$
– MichaelMaggs
May 1 at 15:16
$begingroup$
"reaching zero" implies exactly zero? As in not going beyond zero to a negative integer?
$endgroup$
– BDrought
May 1 at 15:28
$begingroup$
That's right. Players are not allowed to end up with a negative number.
$endgroup$
– MichaelMaggs
May 1 at 15:30
$begingroup$
I do have the answer for 12, but as there are a lot of possible plays it would be lengthy to set them all out in full. And maybe not that interesting.
$endgroup$
– MichaelMaggs
May 1 at 15:47
$begingroup$
I'm still looking at the situation starting at 12, and you're not wrong about it being tedious with pencil and paper. How do you feel about computer-assisted solutions to this one?
$endgroup$
– Gareth McCaughan♦
May 1 at 16:21