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.
Problem
Source: INAMO 2023 P3 (OSN 2023)
Tags: combinatorics, Game Theory, Perfect Square, Indonesia, Indonesia MO
Furra
29.08.2023 14:43
Solution from the proposer (me):
Let $f(n)$ be the least step that Asep need to win. Claim: $f(xy)\leq |x-y|$. Proof of claim:
Click to reveal hidden textIf $x=y$, Asep is done. Else, wlog $x>y$. Asep proceeds as follows:
If Neneng chooses up, Asep replaces $xy$ with $x(y+1)$.
If Neneng chooses down, Asep replaces $xy$ with $(x-1)y$. This move is valid since $x\geq 2$.
In each step, Asep will reduce the difference between the two numbers by exactly 1. Therefore, by applying this strategy $x-y$ times, Asep wins. This completes the proof.
We now divide the cases based on $n$ modulo $4$.
If $n=4k\geq 16$, Click to reveal hidden textwe can apply the claim directly to get \[
f(n) \leq |k-4| = \dfrac{n-16}{4} < \dfrac{n-5}{4}.
\]
If $n=4k+2 \geq 18$, Click to reveal hidden textwe first add or subtract 2 to get $4k$ or $4k+4$. Then we apply the claim. Following this strategy, we get
\[
f(n) \leq 1+ |(k+1)-4| = \dfrac{n-10}{4} < \dfrac{n-5}{4}.
\]
If $n=4k+3 \geq 19$ and Neneng's first step is "up",Click to reveal hidden textAsep changes the number to $4k+4$. Then, \[
f(n) \leq 1+|(k+1)-4| =\dfrac{n-11}{4} < \dfrac{n-5}{4}.
\]
If $n=4k+3 \geq 19$ and Neneng's first step is "down",Click to reveal hidden textAsep changes the number to $4k+2$. Then, \[
f(n) \leq 1+\dfrac{(n-1)-10}{4} =\dfrac{n-7}{4} < \dfrac{n-5}{4}.
\]
If $n=4k+1 \geq 17$ and Neneng's first step is "down",Click to reveal hidden textAsep changes the number to $4k$. Then, \[
f(n) \leq 1+|k-4| =\dfrac{n-13}{4} < \dfrac{n-5}{4}.
\]
If $n=4k+1 \geq 17$ and Neneng's first step is "up",Click to reveal hidden textAsep changes the number to $4k+2$. Then, \[
f(n) \leq 1+\dfrac{(n+1)-10}{4} =\dfrac{n-5}{4} .
\]
The remaining cases are $n=14$, where Asep can apply $14 \to 16$ or $14 \to 12 \to (9/16)$, and $n=15$, where Asep can apply $15 \to 16$ or $15 \to 12 \to (9/16)$. This completes the proof.
Remarks:
The motivation for this solution comes from $f(n(n+1))=1$ (since Asep can move to $n^2$ or $(n+1)^2$ in this case).
The casework is not heavy if one already has the claim.
By bruteforcing, one can prove that $f(17)=3$, which gives a case of inequality.
Of course, the claim's bound is not optimal. However, the claim is sufficient to prove the problem's statement.
Furthermore, the problem's bound is not optimal for large $n$; in particular, by modifying (and considering more mod cases...), there exists $C(k)$ such that $f(n)\leq (n-C(k))/k$ for all sufficiently big $n$.
Even more, my friend showed $f(n) \leq \lceil \log_2 n \rceil$ for all sufficiently big $n$, by noticing that $f(2^{k})=1$ when $k$ is odd. I will let him post his solution when he's online.
Neneng and Asep were not the characters' names in the original proposal.It was Nene and Rui, lol.
BlazingMuddy
29.08.2023 21:23
@above Hello.
I claim that Asep can win in at most $\lceil \log_2 n \rceil$ steps. This solves the problem when $n \geq 25$, but the rest can be easily bashed.
For $n = 1$ we are done, so now suppose that $n \geq 2$. First note that if $X = 2^k$, then Asep already wins if $k$ is even, and Asep needs just one more move to win if $k$ is odd. Indeed, suppose that $k$ is odd ($k \geq 1$). If Neneng chooses up, then Asep chooses $d = X = 2^k$, replacing the number on the board with $X + d = 2^{k + 1}$, which is a non-zero perfect square. If Neneng chooses down, then Asep chooses $d = 2^{k - 1}$; then the number on the board is replaced with $X - d = 2^{k - 1}$, which is also a perfect square.
For the general case, we rely on the following claim.
ClaimSuppose that the current number $X$ on the board satisfies $2^m < X < 2^{m + 1}$ for some $m \geq 1$. Then Asep can always replace $X$ (in one move) with a number $Y$ such that $2^m \leq Y \leq 2^{m + 1}$ and $\nu_2(Y) \geq \nu_2(X) + 1$.
ProofSince $2^m < X < 2^{m + 1}$, $X$ is not a power of $2$. We can write $X = 2^t c$, where $c > 1$ is an odd number and $t = \nu_2(X)$; automatically $t < m$. Now whatever Neneng does, Asep chooses $d = 2^t$. Then the new number on the board is either $X + d = 2^t (c + 1)$ or $X - d = 2^t (c - 1)$.
Since $2^m < X < 2^{m + 1}$, we have $2^{m - t} < c < 2^{m - t + 1}$. Thus $2^{m - t} \leq c \pm 1 \leq 2^{m - t + 1}$, whatever the choice of sign in the $\pm$ is. Either way, the new number $Y$ on the board satisfies $2^m \leq Y \leq 2^{m + 1}$.
Since $c$ is odd, we have $\nu_2(c \pm 1) > 1$ whatever the choice of sign in the $\pm$ is. In either case, the new number $Y$ on the board also satisfies $\nu_2(Y) = t + \nu_2(c \pm 1) \geq t + 1$. The claim is proved.
Now we move on to the general case $n \geq 2$. There exists a unique positive integer $k$ such that $2^k \leq n < 2^{k + 1}$. Again, if $n = 2^k$, we are done, so now suppose that $2^k < n < 2^{k + 1}$. Repeating the claim whenever necessary, we claim that Asep can reach the state where the number on the board is either $2^k$ or $2^{k + 1}$ in at most $k$ moves. Indeed, if not, then after $k$ moves, the number $X$ on the board will still satisfy $2^k < X < 2^{k + 1}$, say by the claim and small induction. But the claim also says that $\nu_2(X) \geq \nu_2(n) + k \geq k$ since the initial number on the board is $n$. A contradiction!
We proved that Asep can reach the state with the number on the board being a power of $2$ in at most $k = \lceil \log_2 n \rceil - 1$ moves. If that power of $2$ is not a square, as in the first paragraph, Asep needs just one more move. This proves that Asep can win in at most $\lceil \log_2 n \rceil$ moves.
I think the bound $(n - 5)/4$ is false when $n = 13$... so $n \geq 14$ is tight for the original problem.