# IMO 2017 problem #1

This clearly means that the sequence repeats itself(not necessarily from beginning, i.e from $a_0$) after a certain number of terms. So we can visualize the sequence in the following way:

After a certain number of terms, we get a perfect square, the next term becomes its square root, then after a while we get the same perfect square, the next term again is its square root, and this repeats.

Thus we see that the square root of the perfect square must follow $$n + 3k = n^2,k\in\mathbb N_0\Rightarrow k=\frac{n(n-1)}3$$
So
$$n\equiv\{0,1\}\bmod3$$ Now if $n$ is of form $3k+1$ then its square is also the same and also $a_0$

Now we will prove that this $3k+1$ form of $n$ will not do.
We can use this to show that if $n$ is of form $3k+1$ then we will get a perfect square before reaching $n^2$ and it will never repeat.

Only I have to prove that $a_0$ of form $3k$ will do. Can you do it for me?

• Is $a_0$ of form $(-3n)\forall n\in\mathbb {N}$ or $(1-3n)$? – освящение Jan 28 '18 at 14:21
• @Abhishek It is of form $3n$ – ami_ba Jan 28 '18 at 14:24
• Anyone any hint? – ami_ba Jan 28 '18 at 14:36
• The integer square root of an integer divisible by $3$ is also divisible by $3$. – Mark Bennet Jan 28 '18 at 14:44
• I know, but is this completing the proof? – ami_ba Jan 28 '18 at 14:46

Assume that $a_k = n^2 = 3t$. It's trivial to conclude that $9 \mid n^2$ and so we must have $a_k = n^2 = 9s^2$. Then we get $a_{k+1} = 3s$. Now we'll prove we'll reach a square less than $9s^2$, except when $s = 1$

If this is not the case then $\exists m \in \mathbb{N}$ s.t. $3s + 3m = 9s^2$ and $3s + 3b$ isn't a square for any $b < m$. But now obviously we'll reach $9(s-1)^2 < 9s^2$ as long as $3s \le 9(s-1)^2$, which is true for $s > 1$. Hence $s=1$ yields the unique infinitely repeating cycle $3 \to 6 \to 9 \to 3$ in this case.

Similarly you can do for the case when $a_k = (3s+1)^2$. Then you can prove that we'll reach $(3(s-1) + 1)^2$, for $s>1$, as

$$3s + 1 \le (3(s-1) + 1)^2 \iff 3s+1 \le 9s^2 - 12s + 4 \iff 0 \le 3s^2 - 5s + 1$$

and the right most inequality is trivially true for $s \ge 2$. Checking the case when $s=1$ we get that $a_k = 16$, $a_{k+1} = 4$, $a_{k+2} = 2$ and later we never obtain a square, as all subsequent terms are of the form $3t+2$

So $A = 3,6,9$

• How can the term after $4$ be $7$ when its a perfect square? – ami_ba Jan 28 '18 at 15:07
• @ami_ba Ooops, a mistake. I will fixed it now – Stefan4024 Jan 28 '18 at 15:08
• @ami_ba I fixed it now, with a better explanation – Stefan4024 Jan 28 '18 at 15:13