Puzzling Stack Exchange is a question and answer site for those who create, solve, and study puzzles. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|improve this question
up vote 17 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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