A two player game: Player who gets to 1000 or more first, wins

Question

This is from the current weekly math challenge from the newspaper Le Monde.

Alice and Bob play the following game, in turn:

A number between $1$ and $10$ is written on a blackboard.

At each of their turns, they choose one of these actions:

• multiply the current number by $3$

• multiply the current number by $4$

• add $1$ to the current number.

Alice begins.

If after playing, a player gets a number greater or equal than $1000$, he wins.

Given the initial number, who has a winning strategy ?

For example: the initial number is $2$.

Multiplying by $4$, Alice makes it $8$.

Then Bob adds $1$ and gets $9$.

And so on.

Answer 1

I suppose that both players plays optimally.

Since both players think similarly the win does not depend on player but on current number. Some numbers are clearly a wining ones and some are losing ones. Let's call first W-numbers (if a player gets one before his\her turn he will win), and others L-numbers. Let's find type of each number starting from biggest.

1. If a player gets (after a move of the opponent) a number 250 or bigger he multiplies by 4 and wins. So numbers $n \ge 250$ are W-numbers.
2. If a player gets 249 he will lose next turn. 249 is L-number.
3. If a player gets a number $249 > n > 83$ he will never multiply it, otherwise he will lose, so he will add 1. Since 249 is L-number, then all odd numbers $250 > n > 83$ are L-numbers and all even $250 > n > 83$ are W-numbers.
4. If a player gets an odd number $250/3 > n > 83/3$ he will multiply by 3 and get a L-number. So all odd numbers $83 >= n > 27$ are W-numbers.
5. If a player gets an even number $83 > n > 27$ he can't add 1, he can't multiply by 3 or 4 will multiply by 4 - in any case he will get a W-number for opponent and lose. So even numbers $83 >= n > 27$ are L-numbers.
6. If a player gets an even number $83/3 >= n > 27/3$ he will multiply by 3 or 4 and get L-number for his opponent. So even numbers $26 >= n > 9$ are W-numbers.
7. If a player gets an number $83/4 >= n > 27/4$ he will multiply by 4 and get L-number for his opponent. So numbers $20 >= n > 7$ are W-numbers.
8. If a player gets an odd number $25 > n > 20$ he can't add 1, multiply by 4 or 3 - he will lose. So $23$ and $21$ are L-numbers.
9. $7$ is clearly a W-number, since a player can make $21$ from it.
10. If a player get a number $26/4 >= n > 7/3$ from he can't multiply by 4 or 3 he will lose, so he forced to add 1. So $6$, $4$ are L-numbers and $5$,$3$ are W-numbers.
11. If a player get 2 or 1 he can get L-number (6 or 4) for the opponent. $1$ and $2$ are W-numbers.

Summarising:
If initial number is $4$ or $6$ then the second player wins, otherwise the first player wins.

Answer 2

Note this answer only works if reaching 1000 does not warrent a win. This was the original question but since it was changed to "greater than or equal to 1000" is a win it is incorrect.

Lets look at this for any $N$

if $N>250$ player one can multiply by $4$ and win instantly so label all of those $F$.

If $251>N>82$ it will depend on if $N$ is even or odd. Both players will just add one to prevent the other getting a $250+$. If $N$ is even it is $S$ while if it is odd it is $F$.

If $83>N>63$ then if $N$ is even it is $F$ while if it is odd it is $S$. The reversal happens because when $N=82$ then $3N=246$ which is less than $250$ but even so by the previous paragraph the player awarded that will lose. Simular strategys arrise by multiplying any $N$ by $3$.

If $63>N>20$ then the first player always wins because he can multiply by $4$ to yield a $N>83$ which is even which means he wins.

If $21>N>7$ it is alternating again as if $N$ is even it is $S$ while if it is odd it is $F$. This is because multiplying makes the other player win so they can only add.

For all $N$ between $1$ and $10$ besides $1,8,10$, the first player can force the number into a region which is an $S$ by making sure it is even and between $20$ and $7$. If he cannot, the second player can force a win. This means if $N=1,8,10$ then the second player wins. If $N=2,3,4,5,6,7,9$ then the first player wins.