Consider the game $A . B$.

A positive integer $N$ is written on the board. Two players take turns. On a turn, a player is allowed to either replace the number on the board with one of its divisors (different from one and the number itself), or decrease the number by one (if the resulting number remains positive). The player who cannot make a move loses. For which $N$ can the first player win, regardless of how the opponent plays?
We will call a number $N$ winning if the first player wins when starting the game from it, and losing if the second player wins. A number is winning if and only if there exists a move from it to a losing number, and losing if and only if any move from it leads to a winning number.

Using this statement, we can, by considering natural numbers sequentially, determine whether any specific number is winning or losing: the number 1 is losing, the number 2 is winning, the number 3 is losing (since the only move leads to the winning number 2), the number 4 is winning (since there is a move from it to the losing number 3), and so on:

| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | $\cdots$ |
| :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: |
| $\Pi$ | $\mathrm{B}$ | $\Pi$ | $\mathrm{B}$ | $\Pi$ | $\mathrm{B}$ | $\Pi$ | $\mathrm{B}$ | $\mathrm{B}$ | $\mathrm{B}$ | $\Pi$ | $\mathrm{B}$ | $\Pi$ | $\mathrm{B}$ | $\Pi$ | $\cdots$ |

Notice that the number 16 is losing, and therefore the prime number 17 is winning. The number 33 is winning: from it, you can move to the losing number 3. Therefore, the number 34, though composite, is losing (all three moves from it - to 2, to 17, and to 33 - lead to winning numbers).

Let's prove that 2 and 17 are the only winning prime numbers. Suppose this is not the case, and consider the next winning prime number $p$. In this case, $p-1$ is a losing even number, so among the divisors of the number $p-1$ there cannot be any winning prime numbers, that is, $p-1=2^{n} \cdot 17^{k}(n \geq 1)$. But then from it, you can either move to the number 34 or to the number 16 and win.

If a composite number $N$ has a prime divisor $p$ different from 2 and 17, then from it there is a move to the losing number $p$, that is, the number $N$ is winning. The remaining numbers are of the form $N=2^{n} \cdot 17^{k}$.

It has been shown above that 2, 4, and 8 are winning, while 16 is losing, so numbers of the form $2^{n}$ ($n>4$) are winning: from them, you can move to 16.

The number 34 is losing; therefore, numbers of the form $N=2^{n} \cdot 17^{k}(n, k>1)$ are winning: from them, you can move to 34.

The number $17^{2}=289$ is losing; therefore, numbers of the form $17^{k}(k>2)$ are winning, from them you can move to $17^{2}$.

## Answer

For $N=2, N=17$, and for all composite $N$, except $N=16, 34$, and 289.

Submit a comment