11
$\begingroup$

Mahmoud and Zomhan play a game where they alternatively write numbers on a board. In each turn, a player takes the old number $N$ written on the board and replaces it either by the number $T$ of divisors of $n$ or by the difference $N-T$. For example if $N=22$ is written on the blackboard then $T=4$ with the divisors 1, 2, 11, 22 of $N=22$, and the next player may write $T=4$ or $N-T=18$ on the blackboard.

Mahmoud is the first player to play, and whichever player is the first player to write the number $0$ is the winner of the game. Given that the initial number on the board is $1036$, determine which player has a winning strategy.

$\endgroup$
17
$\begingroup$

A player has a winning strategy if and only if

  • They can write $0$, or
  • They can write a number where their opponent does not have a winning strategy.

If $N$ is $1$ or $2$, the player can write $0$, so they win.
If $N$ is $3$, the player must write $1$ or $2$, and then the opponent wins.
If $N$ is $4$ or $9$ (3 divisors for each), the player can write $3$ and win.
If $N$ is $6$ (4 divisors), the player must write $2$ or $4$, but the opponent wins from both.
If $N$ is $11$ (2 divisors), the player must write $2$ or $9$, but the opponent wins from both.
If $N$ is $12$ (6 divisors), the player writes $6$ and wins.
If $N$ is $1024$ (11 divisors), the player can write $11$ and win.

If $N$ is $1036$ (12 divisors),

the only options are to write $12$ or $1024$. Both of these let the opponent win. So Mahmoud does not have a winning strategy, and Zomhan does.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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