14
$\begingroup$

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.

$\endgroup$

2 Answers 2

21
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ 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. $\endgroup$ Jul 8, 2014 at 19:57
  • $\begingroup$ @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. $\endgroup$
    – kaine
    Jul 8, 2014 at 20:07
  • $\begingroup$ @kaine, well, "player gets a number greater or equal than 1000, he wins". For sure it does influence on the result. $\endgroup$
    – klm123
    Jul 8, 2014 at 20:10
  • $\begingroup$ 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. $\endgroup$
    – kaine
    Jul 8, 2014 at 20:13
  • 4
    $\begingroup$ 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. $\endgroup$
    – Bobson
    Jul 8, 2014 at 21:18
10
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.