Problem 1139

Here a good idea is to decompose any strictly positive integer $n$ as a square times a squarefree number: we replace each $p$-adic valuation of $n$ by the smallest even integer less than or equal to it to obtain a square denoted $a^{2}$ which divides $n$ and such that $\frac{n}{a^{2}}$ is squarefree. Moreover, this decomposition is unique: if $n=a^{2} \times b=c^{2} \times d$ with $b$ and $d$ squarefree, we have $V_{p}(d) \equiv V_{p}(n) \equiv V_{p}(b)(\bmod 2)$ for all prime $p$, so since $b$ and $d$ are squarefree, $b=d$ and $a^{2}=c^{2}$. We will now denote for all $n \geqslant 1, s f(n)$ its squarefree part.

Here, if $m>0$ is written on the board, Alice's moves can either transform $s(m)$ into 1 if $k$ is even, or leave it as $s(m)$ if $k$ is odd because $m^{k}=m \times\left(m^{(k-1) / 2}\right)^{2}$, and the number will always remain strictly positive. Therefore, Bob needs to manage to reduce the squarefree part of the number written (and keep the number strictly positive: thus after a finite number of turns, the squarefree part will be 1, and the number will be a square, allowing Bob to simply remove the number itself. For this, if $m=a^{2} b$ is written on the board, with $b$ its squarefree part and $b>1$ (otherwise Bob wins directly by removing $a^{2}$), Bob can remove $a^{2}$ and obtain $a^{2}(b-1)=a^{2} \times \frac{b-1}{s f(b-1)} s f(b-1)$ whose squarefree part is therefore $s f(b-1) \leqslant b-1<b$, which concludes.