
Problem I-2. All positive divisors of a positive integer $N$ are written on a blackboard. Two players $A$ and $B$ play the following game taking alternate moves. In the first move, the player A erases $N$. If the last erased number is $d$, then the next player erases either a divisor of $d$ or a multiple of $d$. The player who cannot make a move loses. Determine all numbers $N$ for which $A$ can win independently of the moves of $B$.


Solution. Let $N=p_{1}^{a_{1}} p_{2}^{a_{2}} \ldots p_{k}^{a_{k}}$ be the prime factorization of $N$. In an arbitrary move the players writes down a divisor of $N$, which we can represent as a sequence $\left(b_{1}, b_{2}, \ldots, b_{k}\right)$, where $b_{i} \leq a_{i}$ (such a sequence represents the number $p_{1}^{b_{1}} p_{2}^{b_{2}} \ldots p_{k}^{b_{k}}$ ). The rules of the game say that the sequence $\left(b_{1}, b_{2}, \ldots, b_{k}\right)$ can be followed by a sequence $\left(c_{1}, c_{2}, \ldots, c_{k}\right)$ with either $c_{i} \leq b_{i}$ for each $i$, or $a_{i} \geq c_{i} \geq b_{i}$ for each $i$ (obviously, if such a sequence is not on the sheet).

If one of the numbers $a_{i}$ is odd, then the player $B$ posses the winning strategy. Indeed, let for simplicity $a_{1}$ be odd. Then the response for the move $\left(b_{1}, b_{2}, \ldots, b_{k}\right)$ should be

$$
\left(a_{1}-b_{1}, b_{2}, \ldots, b_{k}\right)
$$

One can easily check that this is a winning strategy for $B$ : All the legal sequences split up into pairs and when $A$ writes down one sequence from a pair, player $B$ responds with the second one from the same pair ( $a_{1}-b_{1} \neq b_{1}$ because of $a_{1}$ is odd).

If all $a_{i}$ are even, then the player $A$ has a winning strategy. Let the move of player $B$ be $\left(b_{1}, b_{2}, \ldots, b_{k}\right)$, where one of $b_{i}$ is strictly less than $a_{i}\left(\left(b_{1}, b_{2}, \ldots, b_{k}\right) \neq\left(a_{1}, a_{2}, \ldots, a_{k}\right)\right.$, as it was the first move of $A$ ). Let $j$ be the smallest index such that $b_{j}<a_{j}$. Then the response of $A$ can be

$$
\left.\left(b_{1}, b_{2}, \ldots, b_{j-1}, a_{j}-b_{j}-1, b_{j+1}, \ldots, b_{k}\right) \quad \text { (symmetric reflection of } b_{j}\right)
$$

Again, all legal sequences (except for $\left.\left(a_{1}, a_{2}, \ldots, a_{k}\right)\right)$ split up into pairs and when $B$ writes down one sequence from a pair, player $A$ can respond with the second one $\left(a_{j}-b_{j}-1 \neq b_{j}\right.$ because of $a_{j}$ is even).

Obviously the condition "all $a_{i}$ are even" means that " $N$ is a square". For $N \in[2000,2100]$ it is possible only for $N=2025$. The answer for the alternative question is $2010^{1005}$.
