# A two-player game

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.

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.

• The more usual terms in nim-like games are P positions (won by the Previous player) and N positions (won by the Next player). An N position is a W-number. You are also assuming that $1000$ wins, which I think is not clear from the problem. Good analysis. – Ross Millikan Jul 8 '14 at 19:57
• @klm123 I got a different number... I think it is because I assume that 1000 is not a win... you need to be greater than 1000. In your terms 250 is an L and 249 in statement 3 is a W. – kaine Jul 8 '14 at 20:07
• @kaine, well, "player gets a number greater or equal than 1000, he wins". For sure it does influence on the result. – klm123 Jul 8 '14 at 20:10
• That was editted six minutes ago, 2 minutes after I posted my answer. Your answer now seems to be the correct one due to the change. – kaine Jul 8 '14 at 20:13
• I find it fascinating that 1000 not being winning makes such a difference, but since that converts 250 from a winning number to a losing one, with all the appropriate trickledown effects, it makes sense. – Bobson Jul 8 '14 at 21:18

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.