Double or Take game

Question

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?

Answer 1

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 $12\rightarrow24\rightarrow48\rightarrow12$. 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).

Answer 2

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...?

Answer 3

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)