What is the optimal strategy in a game where players subtract 7 or add or divide by 2?

Question

I made up a nim type game where players start with a relatively high number and then for each turn if the number is odd, the player either subtracts 7 from the number or alternately if the number is even divides by 2 or if the number is odd adds 2. The player may not choose a negative number, though. The player to reach 7 wins.

Example: if the number is 11 the player may either subtract 7 to get 4 or add 2 to get 13. If the number is 16 the player may subtract 7 to get 9 or divide by 2 to get 8. Example game:

The players start with 18

Player 1: 18/2=9 Player 2: 9+2=11 Player 1: 11-7=4 Player 2: 4/2=2 Player 1: 2/2=1 Player 2: 1+2=3 Player 1: 3+2=5 Player 2: 5+2=7

Player 2 wins.

How can we predict whether at any large number the player with the move is in a winning or losing position? Is it possible that for numbers over a certain limit the best strategy for both players will be to always add 2 to keep from losing?

Winning and losing numbers for 1-100:

1 Losing
2 Winning
3 Winning
4 Losing
5 Losing
6 Losing
7 Winning
8 Winning
9 Losing
10 Winning
11 Winning
12 Winning
13 Winning
14 Losing
15 Losing
16 Winning
17 Winning
18 Winning
19 Losing
20 Losing
21 Winning
22 Winning
23 Winning
24 Losing
25 Losing
26 Winning
27 Winning
28 Winning
29 Losing
30 Winning
31 Winning
32 Winning
33 Winning
34 Losing
35 Losing
36 Winning
37 Winning
38 Winning
39 Losing
40 Winning
41 Winning
42 Winning
43 Winning
44 Losing
45 Losing
46 Winning
47 Winning
48 Winning
49 Losing
50 Winning
51 Winning
52 Winning
53 Winning
54 Losing
55 Losing
56 Winning
57 Winning
58 Winning
59 Losing
60 Losing
61 Winning
62 Winning
63 Winning
64 Losing
65 Losing
66 Winning
67 Winning
68 Winning
69 Losing
70 Winning
71 Winning
72 Winning
73 Winning
74 Losing
75 Losing
76 Winning
77 Winning
78 Winning
79 Losing
80 Losing
81 Winning
82 Winning
83 Winning
84 Losing
85 Losing
86 Winning
87 Winning
88 Winning
89 Losing
90 Winning
91 Winning
92 Winning
93 Winning
94 Losing
95 Losing
96 Winning
97 Winning
98 Winning
99 Losing
100 Losing

Answer 1

Lemma $1.1$: A player loses if $N \in \{2,3,7,8\}$ directly before he/she has to make a move.

The proof is left as an exercise to the reader.

Lemma $1.2$: Let the starting $N$ be congruent to $0$, $1$, $4$, $5$, $6$, or $9$ (mod $10$) and suppose player A starts the game.

Then if player A follows the below strategy $N$ will always be congruent to $0$, $1$, $4$, $5$, $6$, or $9$ (mod $10$) before he/she moves and $N$ will always be congruent to $2$, $3$, $7$, or $8$ (mod $10$) after he/she moves. $$\begin{array}{c|c|c|} N \text{ % } 10 & \text{Move} \\ \hline 0 & -7 \\ \hline 1 & +2 \\ \hline 4 & \cdot \frac{1}{2} \\ \hline 5 & +2 \text{ if } N=5, -7 \text{ otherwise} \\ \hline 6 & \cdot \frac{1}{2} \\ \hline 9 & -7 \\ \hline \end{array}$$ Note that moving from $0$ to $-7$ is not a legal move. However $N$ will never be $0$ because the only non-zero numbers to reach $0$ from are $-2$ and $7$.

Proof: Let $N_k$ be the value of $N$ before a player moves and $N_{k+1}$ the value of $N$ after that player moves.

Consider the following table of congruence classes (mod $10$) of $N_{k+1}$ for each of the ten possible congruence classes (mod $10$) of $N_k$ and the two possible moves. $$\begin{array}{c|c|c|} N_k \text{ % } 10 & \text{+2} & \text{-7} & \cdot \frac{1}{2} \\ \hline 0 & - & 3 & 0, 5 \\ \hline 1 & 3 & 4 & - \\ \hline 2 & - & 5 & 1, 6 \\ \hline 3 & 5 & 6 & - \\ \hline 4 & - & 7 & 2, 7 \\ \hline 5 & 7 & 8 & - \\ \hline 6 & - & 9 & 3, 8 \\ \hline 7 & 9 & 0 & - \\ \hline 8 & - & 1 & 4, 9 \\ \hline 9 & 1 & 2 & - \\ \hline \end{array}$$ From $0$, $1$, $4$, $5$, $6$, and $9$ (mod $10$), the above strategy always results in a move such that $N_{k+1}$ is congruent to $2$, $3$, $7$, or $8$ (mod $10$).

From $2$, $3$, $7$, or $8$ (mod $10$), there is never an option to make a move such that $N_{k+1}$ is congruent to $2$, $3$, $7$, or $8$ (mod $10$).

Theorem $1.3$: Let the starting $N$ be congruent to $0$, $1$, $4$, $5$, $6$, or $9$ (mod $10$) and suppose player A starts the game.

Then if player A follows the above strategy, he/she will win the game.

Hint: So by Lemma $1.1$ and $1.2$ we know that player A will win if $N$ ever gets down to $2$, $3$, $7$, or $8$. The final piece is to show that if player A follows the strategy outlined in Lemma $1.2$, $N$ will always eventually reach $2$, $3$, $7$, or $8$. Note that the only cases in which player A will make an increase to $N$ is if $N$ is congruent to $1$ (mod $10$) or if $N$ is $5$ before he/she moves.

Answer 2

Call a number $n$ winning if $n$ is of the form $10k+b$ with $b \in \{2,3,7,8,11,16\}$, or if $n=10.4^k.(2b+1)$,
and call $n$ losing if $n$ is $1,6$ or of the form $10k+b$ with $b \in \{4,5,9\}$ or if $n = 20.4^k.(2b+1)$.

If $n$ is winning then you can move to a losing number :

if $n=10k+b$ with $b \in \{11,12,16\}$, remove $7$.
if $n=10k+b$ with $b \in \{3,7\}$, add $2$.
if $n=2$ or $n=10k+8$ or $n=10.4^k(2b+1)$, divide by $2$.

If $n$ is losing then you can only move to a winning number.

Furthermore, if you always move from a winning number to a losing number (that is, if the players don't mess up when they get told they can win), then the game will end eventually. To show this it is enough to look at the longest possible sequences of "add $2$" moves.

If $n=10k+3$, you can have $4$ "add $2$" moves in a row (or, if $k$ was $0$, you win in two moves), leading to $10k+11$ (or the losing player can choose to go to $10k-2$ or $10k+2$ and decrease the numbers earlier than he's forced to)
Adding $2$ to $10k+11$ would be handing a win to the losing player, so you're forced to remove $7$ and get to $10k+4$. And from there, the losing player can only go to $5k+2$ or $10k-3$ (if that's allowed).
So overall, either you win, or you get to one of $10k-3,10k-2,10k+2,5k+2$, all of which are smaller than the $10k+3$ we started from.

This is enough to show that the numbers will decrease overall until someone wins the game.

Answer 3

Unless the starting number is either $5$ or $14$ (or $7$ I guess?) the game will never end.

Here's why: It's easy to see that $5$ and $14$ are the only numbers from which $7$ can be reached. Therefore, as long as each player can avoid making one of these numbers, they will never lose and the game will never end.

The only reason a player would play either $5$ or $14$, then, is if these two (or one of these two) are their only options. But it's easy to check that there is no number which only allows you to play either $5$ or $14$.