MathDB
A Game with Limited Steps

Source: INAMO 2023 P3 (OSN 2023)

August 29, 2023
combinatoricsGame TheoryPerfect SquareIndonesiaIndonesia MO

Problem Statement

A natural number nn 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 XX. Initially, Neneng chooses the sign up or down. Then, Asep will pick a positive divisor dd of XX, and replace XX with X+dX+d if Neneng chose the sign "up" or X−dX-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≥14n \geq 14, Asep can win in at most (n−5)/4(n-5)/4 steps.
Back to ProblemsView on AoPS