Problem 21: Stuck in a Loop (IMO 2017 P1)
The problem statement has been provided in the references. I will go through it here too but in a different way.
Let us say that you are escaping a pursuer on a 1-D “lattice”/space where each step takes you 3 distance units ahead. You can only take an integer number of steps and you start running from a point that has an integer coordinate (i.e. > 1). If you kept walking normally, you would wander off and never return back (you are faster than the pursuer). As usual, the game isn’t simple and if you are unlucky you step on a point that has a perfect square coordinate, you must go back to the point that is the square root of the coordinate. The pursuer tells you that you’re bound to eventually get caught and you’re just wasting your strength ! Why is this true?
Solution
The problem can be formally written as follows -
For a starting point \(a_{0}>1\), define the sequence \(a_{0}, a_{1}, a_{2}, \ldots\) by: \(a_{n+1}=\left\{\begin{array}{ll} \sqrt{a_{n}} & \text { if } \sqrt{a_{n}} \text { is an integer, } \\ a_{n}+3 & \text { otherwise, } \end{array} \quad \text { for each } n \geqslant 0 .\right.\)
where the sequence \(a_{0}, a_{1}, a_{2}, \ldots, a_{n}\) is the sequence of coordinates through which you passed after n-steps.
Before we start drawing, let us note one important thing - Any perfect square is either \(\equiv 1 \mod 3\) or \(\equiv 0 \mod 3\).
Any seqence of steps that keep repeating in a loop would evidently lead you to get caught by the pursuer. This can happen if the loop contains an integer \(n\) and since it must end back at \(n\) (since it is a loop), the pre-final term in the loop should be \(n + 3m\) form some \(m\) (where \(m\) represents the number of steps in the loop) such that \(n + 3m = n^2\).
For the last equality to be true \(n^2 - n\) must be divisible by 3. This implies that \(n\) should be either \(\equiv 1 \mod 3\) or \(\equiv 0 \mod 3\). In fact, it can be quickly checked that if \(n \equiv 2 \mod 3\) then, we would not have a loop! This leads us to the conclusion that if you tread upon a lattice point with a coordinate that is \(\equiv 2 \mod 3\), you will eventually escape.
If \(n\) is \(\equiv 1 \mod 3\) then \(n + 3m\) is also \(\equiv 1 \mod 3\) for any \(m\). Earlier, we noted that perfect square can be \(\equiv 1 \mod 3\). Therefore, it is possible that for some \(m < \frac{n^2 - n}{3}\), \(n + 3m\) is a perfect square. In fact, it is easy to see that for \(n > 4\) and \(n \equiv 1 \mod 3\),
\[m = \frac{n^2 - n - 4(n-1)}{3} < \frac{n^2-n}{3}\] \[n + 3m = n^2 - 4n + 4 = (n-2)^2\]So, if you encounter a point that is \(\equiv 1 \mod 3\) you’d eventually stumble upon a perfect square that is smaller than \(n^2\) and you’ll have to go back to \(\sqrt (n-2)^2 = n - 2\). Now, if \(n \equiv 1 \mod 3\) then, \(n - 2 \equiv -1 \mod 3\) or \(n-2 \equiv 2 \mod 3\). Recalling the conclusion derived two paragraphs earlier, we can safely say that if somewhere along your path the coordinate is \(\equiv 1 \mod 3\), you can still escape ! (Because you will eventually land on a point that is \(\equiv 2 \mod 3\))
Finally, it is easy to see that if you start at a point that is \(\equiv 0 \mod 3\) (like n = 3), you will always pass through a point since each step you take preserves the property that your the coordinate of your location is divisible by 3. Also, perfect squares that are divisible by 3 will have square roots that are also divisible by 3.
Note - I have attached a plot showing the \(y = x + 3\), \(y = \sqrt{x}\) and \(y = x\) lines. The path constructed on the plot shows the simplest possible loop that starts at \(x = 3\).
Conclusion
The final conclusion is that your fate was sealed when you started running. The pursuer knows that you were unlucky and you started running at a coordinate that is \(\equiv 0 \mod 3\).