Problem

Source: INAMO 2023 P3 (OSN 2023)

Tags: combinatorics, Game Theory, Perfect Square, Indonesia, Indonesia MO



A natural number $n$ is written on a board. On every step, Neneng and Asep changes the number on the board with the following rule: Suppose the number on the board is $X$. Initially, Neneng chooses the sign up or down. Then, Asep will pick a positive divisor $d$ of $X$, and replace $X$ with $X+d$ if Neneng chose the sign "up" or $X-d$ if Neneng chose "down". This procedure is then repeated. Asep wins if the number on the board is a nonzero perfect square, and loses if at any point he writes zero. Prove that if $n \geq 14$, Asep can win in at most $(n-5)/4$ steps.