IMO 2017 · Problem 1

For each integer \(a_0>1\), define the sequence \(a_0,a_1,a_2,\ldots\) by: \[ a_{n+1}= \begin{cases} \sqrt{a_n} & \text{if }\sqrt{a_n}\text{ is an integer},\\ a_n+3 & \text{otherwise}, \end{cases} \qquad\text{for each }n\geq 0. \] Determine all values of \(a_0\) for which there is a number \(A\) such that \(a_n=A\) for infinitely many values of \(n\).

Official text of the problem. Official problem paper (PDF)

Answer

\[ \boxed{\text{All positive integers }a_0\text{ divisible by }3.} \]

Solution

All terms are integers greater than \(1\). Moreover, both operations preserve whether a term is divisible by \(3\): this is immediate for addition of \(3\), and an integer square is divisible by \(3\) if and only if its square root is divisible by \(3\).

We first establish a descent observation. Suppose a term has value \(b\), and there is an integer \(r\) such that \[ 2\leq r<b,\qquad r^2\geq b,\qquad r^2\equiv b\pmod3. \] Then a later term is smaller than \(b\). Indeed, \(r^2\) belongs to the progression \[ b,\ b+3,\ b+6,\ldots. \] The sequence follows this progression until it encounters its first perfect square \(s\), which must satisfy \(s\leq r^2\). The following term is therefore \[ \sqrt{s}\leq r<b. \]

Let \(m\) be the smallest value attained by the sequence. Such a value exists because all terms are positive integers.

Case 1: \(3\mid a_0\). Every term is divisible by \(3\), so \(m\geq3\) and \(3\mid m\). If \(m\geq6\), set \(r=m-3\). Then \(2\leq r<m\), both \(r^2\) and \(m\) are divisible by \(3\), and \[ r^2-m=(m-3)^2-m=(m-6)(m-1)+3>0. \] The descent observation gives a term smaller than \(m\), a contradiction. Hence \(m=3\), so the sequence eventually reaches the cycle \[ 3\longmapsto6\longmapsto9\longmapsto3. \] Thus \(A=3\) occurs infinitely often.

Case 2: \(3\nmid a_0\). No term is divisible by \(3\), so \(m\equiv1\) or \(2\pmod3\).

If \(m\equiv1\pmod3\), then \(m\geq4\). Set \(r=m-2\). We have \(2\leq r<m\), \[ r^2\equiv(-1)^2\equiv1\equiv m\pmod3, \] and \[ r^2-m=(m-2)^2-m=(m-1)(m-4)\geq0. \] Again, the descent observation contradicts the minimality of \(m\).

Consequently \(m\equiv2\pmod3\). Choose \(N\) with \(a_N=m\). Since every integer square is congruent to \(0\) or \(1\pmod3\), none of the numbers \(m+3k\) is a square. Induction therefore gives \[ a_{N+k}=m+3k\qquad(k\geq0). \] This tail is strictly increasing, and the preceding part is finite. Hence no value occurs infinitely often.

The required initial values are exactly the positive multiples of \(3\).

The solution was checked against the official IMO shortlist solutions.