Problem: Shakur and Tiham are playing a game. Initially, Shakur picks a positive integer not greater than $1000$. Then Tiham picks a positive integer smaller than that. Then they keep on doing this taking turns to pick progressively smaller and smaller positive integers until someone picks $1$. After that, all the numbers that have been picked so far are added up. The person picking the number $1$ wins if and only if this sum is a perfect square. Otherwise, the other player wins. If Shakur starts with the number $n$, find all values of $n$ for which he has a winning strategy.
The problem is from a national olympiad. Here is my progress in solving the problem:
I first checked the small cases.
- For $n=1$, Shakur has a winning strategy.
- For $n=2$, Tiham must pick $1$. But $3$ is not a perfect square. So, Shakur has a winning strategy in this case.
- For $n=3$, Tiham can pick $2$. Then, Shakur picks $1$. But $6$ is not a perfect square. So, Tiham wins in this case.
Then I noticed that $n$ must be $3$ less than a perfect square when $n>2$. Because Tiham can pick $2$ after Shakur picks $n$ and then Shakur must pick $1$. So, Shakur can't have a winning strategy unless $n+3$ is a perfect square.
But now I am not sure whether for all the $n$s of this form Shakur has a winning strategy.
Best Answer
Note: an earlier version of this had a fatal arithmetic error. I believe this version is correct.
As remarked by the OP, $S$ must start with something of the form $k^2-3$. We contend that this wins if $k=3$, but loses for any higher $k$.
Let us suppose that $S$ starts with $k^2-3$
Suppose $T$ responds with $t$. Then, $S$ can take $2$, forcing $T$ to choose $1$, so $S$ wins unless $k^2-3+t+2+1=k^2+t$ is a perfect square.
Now, if $k=3$, so $S$ has started with $3^2-3=6$ then it is impossible for $T$ to reach the next perfect square, so $S$ wins in this case.
What if $S$ starts with $k^2-3$ for $k>3$? Well, if $T$ has chosen $t$ with $k^2+t$ a perfect square, then $S$ can not choose $1$ or $2$. If $S$ chooses $s$ then $T$ can respond with $2$, forcing $S$ to take $1$, in which case the sum would be $k^2-3+t+s+2+1=k^2+s+t$ so $S$ has lost unless $k^2+s+t$ is again a perfect square. That is impossible for, say, $k=5$ so $22=5^2-3$ does not provide a winning strategy for $S$.
This holds for larger $k$ as well.
To see this, here is a winning strategy for $T$, given that $S$ has started with $k^2-3$ for $k>3$: $T$ chooses $t=2k+1$, noting that $k^2+2k+1=(k+1)^2 $is a perfect square. $S$ then needs an $s$ such that $(k+1)^2+s$ is a perfect square, but the least $s$ that works is $2k+3$ which is too big, so $S$ loses.
Example: $k=10$. Suppose $S$ starts with $10^2-3=97$. $T$ responds with $2k+1=21$, for a total of $97+21=118$. $S$ can not respond with $2$, but every other choice $S$ makes allows $T$ to take $2$, so $S$ loses.