First approximation based on this post.

It should be "for each integer," not "for an integer," I think. (or maybe for every integer. Either way, it doesn't make much of a difference)

Sketch by 1=2 and i (which seems too simple????): if a0 is 0 mod 3, then bounding shows that you get 3 -> 6 -> 9 -> 3 ->... If a0 is 2 mod 3, then you always increase by 3 and so its not periodic. If a0 is 1 mod 3, then we also fail. Use strong induction. Base cases of a0 =1, a0=4 work. For IS, look at guys in the interval (m^2, (m+1)^2]. Youll eventually hit the upper bound of this sequence, and so next term is m+1, which is smaller than (m-1)^2 for large enough m.

Just plain bounding and cycles. Why is the problem so case bashy?

Maybe I'm missing something, but: obviously $a_0\equiv 2\pmod{3}$ is a bust (it can't be periodic 'cause it adds and thus increases infinitely). If a term is not $2\pmod{3}$, then it will eventually reach a perfect square in the "additive phase." Consider the case with $a_0\equiv 1\pmod{3}$. From the above it suffices to consider the squares that are $1\pmod{3}$. Indeed, it is fairly straightforward to show with some bounding that the structure is "downward directed" (a.k.a. essentially decreasing), and eventually funnels into $16\to4\to 2$ if they don't end up at the square of something that's $2\pmod{3}$, which ends up adding infinitely from above. The $3\mid a_0$ case can be carried out similarly, but there are some solutions (obvious ones are $a_0\in\{3,6,9\}$) Edit: they should all funnel into the $3\to 6\to 9$ cycle for the same reasons as before. Sniped

Idea: multiples of 3 work, you can show by strong induction you eventually hit either $3,6,9$, which is gg. 2 mod 3 fails for obvious reasons. 1 mod 3 fails by strong induction - you have to hit a number that's 2 mod 3 eventually also @above, technically it doesn't always funnel into 16 --> 4 --> 2, it could funnel into some other square that has the form $(3k+2)^2$ like 25 --> 5.

@above true, this is what happens when you only worry about the most pathological cases and forget the easier ones you threw away

1 mod 3 works for negatives

Just for completeness.

It says $a_0>1$

The point why this problem is so remarkably easy seems to be the fact that, by checking the behaviour for small initial values (and what else are you going to do when confronted with such a problem?) you do not only see immediately what happens, but also pretty much why this happens. Converting these observations into a formal proof shouldn't be difficult for anyone who has seen the concept of mathematical induction (and, after all, any IMO contestant should belong to this group, right?). I shall be very much surprised if this problem does not admit a conceivably higher average score compared to the first problems in recent IMOs.

@Tintarn: Over the last few years, a lot of new countries has entered IMO. Many students of these countries have little or no training. I would guess that the intention of the jury was to offer a problem that is understandable (and solvable!) even for very un-experienced participants. (As a side-effect, this might raise the bronze cut-off by one or two points.)

Oh sure. Note that I just tried to objectively explain what makes this problem so easy (in my eyes) and made a score prediction. I didn't (and didn't intend to) criticise this at all.

Yh i think this problem is not imo level

easy for IMO1 but i like it.

It maybe too easy but I think it also means the third problem will be too difficult

You can more easily prove multiples of 3 work by first showing there exists $M$ such that $a_n < M$ for all $n$ (such an $M$ can be the least perfect square multiple of $9$ greater than $a_0$), and we are done by Pigeonhole!

Here's a slightly different solution, but with more or less the same idea. Assume that $a_0 = a$ satisfies the condition. Then obviusly there has to be an finite cycle in the sequence. We'll prove that the cycle is of the form $n,..,n^2,n,...,n^2,n,...$, where $n$ is not a full square and there isn't a full square between n and $n^2$. Now let's start at $a_0=a$ and $t^{2^{k_t}}$ is the first full square in our sequence. Soon we'll reach $t \le a$. Now as $a$ satisfies the problem $t$ has to be either a part of a cycle $t,..,t^2,t,...,t^2,t,...$ or there exists $m$ s.t. $t<m^{2^{k_m}}<t^2$. If the latter is the case obviously we soon reach $m \le t$. So we repeat this and as the sequence $a, t, m, ... $ is decreasing we must stop at one point, so this forces a cycle $n,..,n^2,n,...,n^2,n,...$, where $n$ is not a full square and there isn't a full square between n and $n^2$ Now taking look at this cycle we have that $(n-3)^2$ shouldn't appear in it, but as $(n-3)^2 < n^2$ we must have $(n-3)^2 < n$, which yields that $n\le 5$. Excluding $2,5$, as they are 2 mod 3 and $4$ as it's a full square we get that the only possible value is $n=3$ and so the cycle is $3,6,9,3,6,9,...$.Now using the construction in the previous paragraph we can conclude that this works for all numbers of form $3k$ (This is true as we're never going to reach a number 2 mod 3, which guarantees a cycle; If the number is of other form there's a possiblity we never reach a square after some time. In fact this is always true, as the only possible cycle is of the form $3,6,9,3,6,9,...$ and it can never be reached if $a \not = 3k$).

Case 1: $a_0\equiv 0\pmod{3}$. We have $a_m\equiv 0\pmod{3}\,\,\forall m\geq 0$. If $a_0=3$ then $a_{3m}=3\,\,\forall m\geq 0$, therefore $a_0=3$ satisfying the condition of the problem. If $a_0=3k$ for some $k>1$. We will prove that there is an index $m_0$ such that $a_{m_0}<a_0$, and therefore (by replace $a_0$ by $a_{m_0}$) $a_0$ satisfying the condition of the problem. If $a_0$ is a square then $a_1<a_0$ else $m^2<3k<(m+1)^2$ for some positive integer $m$, exactly one of $m+1$, $m+2$, $m+3$ is divisible $3$, assume that it is $m+x\,\, (x\in\{0,1,2\})$, for some $m_0$ we have $a_{m_0}=m+x\leq m+3<3k=a_0$, we're done. Case 2: $a_0\equiv 2\pmod{3}$. In this case we have $a_n=a_0+3n\,\,\forall n\geq 0$ therefore $a_0$ does not meet the condition of the problem. Case 3: $a_0\equiv 1\pmod{3}$. We have $a_m\not\equiv 0\pmod{3}\,\,\forall m\geq 0$. If $a_m\equiv 2\pmod{3}$ for some $m$ then by case 2, the sequence is unbound, therefore $a_0$ does not meet the condition of the problem. If $a_m\equiv 1\pmod{3}\,\,\forall m\geq 0$ then assume that $a_k$ is smallest in $\{a_n\}$. Similary case 1, we can find $a_l$ such that $a_l<a_k$, contradiction! Therefore $a_0$ does not meet the condition of the problem. Conclude, $a_0\equiv 0\pmod{3}$.

A simple casework problem! We claim that $a_0$ can be any multiple of 3. Case 1: $a_0 \equiv 2 \pmod{3}$. In this case all the numbers will be $2 \pmod{3}$. This means that no perfect square is possible. Hence, the the sequence will be a strictly increasing AP. Case 2: $a_0 \equiv 1 \pmod{3}$. In this case we know that there will be some perfect square in the sequence because all numbers are $ 1 \pmod{3}$. Let's define the first perfect square of the sequence to be $a_k$ which will also be $1 \pmod{3}$. So ow there are two posi $$a_{k+1} \equiv 2 \pmod{3}$$Hence, all the next terms of the sequence will be again a strictly increasing AP. Case 3: $a_0 \equiv 0 \pmod{3}$. In this case too, we know that there will be some perfect square in the sequence because all numbers are $ 0 \pmod{3}$. Let's define the first perfect square of the sequence to be $a_k = 9m^2$. So, $$a_{k+1} = 3m$$Now there are only two possible cases. Either $3m$ is in our sequence or not. If it's is our sequence then we know that the cycle will continue i.e. $$9m^2, 3m, \dots , 9m^2, 3m \dots$$ If it's not in our sequence i.e. it's smaller than $a_0$. If we continue like this then we will eventually reduce to $$9 \Rightarrow 3 \Rightarrow 6 \Rightarrow 9$$And we are done since there are infinitely many $n$ such that $a_n = 9, 3, 6$. Hence proved!

The answer is all multiples of $3$. If $a_0 \equiv 2 \pmod 3$, then there are no perfect squares in the sequence, so the sequence is an arithmetic sequence and no term will repeat. If $a_0 \equiv 1 \pmod 3$, we will use induction to prove that the sequence has a $2 \pmod 3$ term no term will appear infinitely many times. This is clearly true for $a_0 = 4$, as the sequence is $4, 2$. Now suppose the claim is true up to $4^{2^n}$. Then up to $4^{2^{n+1}}$, the sequence will reach a perfect square whose square root is either $2 \pmod 3$ or $1 \pmod 3$ and $\leq 4^{2^n}$, so the sequence will always have a $2 \pmod 3$ term. Therefore, all $a_0 \equiv 1 \pmod 3$ do not work. If $a_0 \equiv 0 \pmod 3$, then all terms of the sequence are multiples of $3$. Let $m^2$ be a perfect square in the sequence. If there are no $0 \pmod 3$ perfect squares between $m$ and $m^2$, then there is a cycle in the sequence. Otherwise, we repeat can this process with a smaller perfect square between $m$ and $m^2$. Since all terms of the sequence are positive, eventually we will find a cycle in the sequence. Therefore, all $a_0 \equiv 0 \pmod 3$ work.

This problem holds so many cases, so I'd present shortly the main idea : If $a_{0} \equiv 0 \pmod{3}$ : We can finish immediately by strong induction of multiples of $3$ and prove it works. If $a_{0} \equiv 1 \pmod{3}$ : Again same idea to prove we'll definitely hit $a_{i} \equiv 2 \pmod{3}$ then the sequence will increasing forever The remaining case is obvious.

We claim that the answer is all $a_0=3k$. It is obvious that $a_0 \equiv 2 \mod{3}$ doesn't work since no perfect squares are $2 \mod{3}$, and every term in the sequence is $2 \mod{3}$, which means the sequence will be monotonically increasing and thus no terms will appear infinitely many times. Claim: All $3|a_0$ works. Since $x^2 \equiv 0 \mod{3} \implies x \equiv 0 \mod{3}$, we know that all elements of the sequence are divisible by $3$. Let us operate on the sequence until we must take square roots, then keep square rooting until we must take $+3$ as the next move. Call this number at $a_i=A=3t$, where $3t$ is not a perfect square. We will keep incrementing $t$ by $1$ until $3t$ becomes a perfect square, then taking square root recovers $A$. Thus $A$ appears infinitely many times. Claim: All $a_0 \equiv 1 \mod{3}$ don't work. Note that $x^2 \equiv 1 \mod{3}$ could mean $x \equiv 1, 2\mod{3}$, and if the modularity ever flips to $2 \mod{3}$ the sequence becomes monotonically increasing and we are done. So we just have to prove that eventually the modularity flips from $1$ to $2 \mod{3}$. Suppose a term $A$ does appear infinitely many times, that means the sequence should eventually be periodic. WLOG let $A=3k+1$ be the smallest element of the period. That means when we are at $a_i=3k+1$, we should eventually reach $a_j=(3k+1)^2$. However, note that $3k-1>0$ has $3k+1 \leq (3k-1)^2 < (3k+1)^2$. Since $(3k-1)^2 \equiv 1 \mod{3}$ we will always hit it first, and then the next element becomes $3k-1 \equiv 2 \mod{3}$ so the sequence cannot be eventually periodic.

The answer is all $a_0$ so that $3 \mid a_0$. Say there is some $k$ so that $a_k = (3x)^2$ for $x > 1$. Then $a_{k+1} = 3x$. Notice that $3x - 3)^2 = 9x^2 - 18x + 9 > 3x$ for all $x > 1$. Thus, $a_i$ will continuously keep on reaching smaller and smaller squares until $x = 3$. From here, we get that $a_i$ goes in a loop; $3 - 6 - 9 - 3 - \dots$, so for all $a_0$ there exists an $A$. Notice that $2$ is not a quadratic residue modulo $3$ so if at some point, $a_i$ becomes $2 \pmod{3}$, there will be no such $A$ satisfying our requirements. Say that $a_0 \equiv 1\pmod{3}$. Then, similarly, say that there is a $k$ so that $a_k = (3x + 1)^2$. Notice that $(3x-2)^2 > 3x + 1$ for all $x > 1$. However if $x = 1$ then $(3x - 2) = 1$ which is clearly not a valid number in the sequence. So it follows that $a_i$ must continously decrease until it reaches $4$. Then, taking the square root of $4$ gets $2$, which is $2\pmod{3}$ so there exists no such $A$.

I claim the answer is only the numbers divisible by $3$. Proof nothing else works: Our aim will to be show the sequence eventually hits a number that is $2$ mod $3$, at which point we are clearly done by quadratic residues (sequence just becomes adding $3$). Thus assume $a_0 \equiv 1 \mod 3$. Construct zones of the form $((3n - 1)^2, (3n + 1)^2]$. Clearly, if $a_i$ is not in such a zone, eventually we will have some $a_j = (3n + 2)^2$, at which point we fail. Now we claim that if $a_i$ is always $1$ mod $3$, it can never go up a zone and must eventually leave the zone by square root. The first part is trivial, we can never add $3$ to leave a zone since we will always just hit $(3n +1)^2$. We are also eventually forced to hit $(3n +1)^2$, at which point we go to $3n + 1$. We see $3n +1 \le (3n - 1)^2$ is always true, so we always leave the zone. Since this process of going down zones can only occur a finite amount of times, we see that at some point we must end up not in a zone, at which point we are done. Proof all multiples of $3$ work: Construct zones of the form $((3n)^2 , (3n + 3)^2 ]$, we can clearly see that we can never leave a zone by adding $3$, so we must always leave the zone by hitting a square root, and since $3n + 3 < 9n^2$ for all $n > 1$, and all numbers are in zones, we must always hit the bottom zone, at which point we are stuck there forever.

We claim that only $a_{0}= 3k, k \in \mathbb{Z}^{+}$ will work CLAIM 1: If $3 \mid a_{0}$, then $\{a_{i}\}_{i\ge 0}$ is eventually periodic: PROOF: Note that $\{a_{i}\}_{i\ge 0}$ will remain constant modulo $3$. For any $3k$ achieved in the sequence, let $3(a-1)^2<k< 3a^2$. Observe that after some time, $3(3a^2)$ is achieved, and the next value will be $3a<3k$. Hence, the sequence will ultimately reach $3 \cdot 1=3$, after which the sequence will become $3,6,9,3,6,9…$. CLAIM 2: If $1 <a_{0} \equiv 1 (\mod 3)$, then $\{a_{i}\}_{i\ge 0}$ will eventually reach a number $m \equiv 2(\mod 3)$, after which, the sequence is monotonically increasing. PROOF: Let $r=k^2$ be the first perfect square in the sequence. Consider $a$, the smallest positive integer not divisible by $3$ such that $k^2<a^4$. Note that the next value in the sequence will be $k<a^2$. Observe that $a^2$ is the smallest perfect square greater that $k$ not divisible by $3$. Therefore, the sequence will again eventually reach $a^2$, and therefore $a$ (since $a^2 \equiv 1 (\mod 3)$). If $a \equiv 2(\mod 3)$, then we are done. If not, then this process will keep occurring. At some point, it wil reach $4$, which is the smallest integer $\equiv 1 (\mod 3)$. After reaching $4$, it will reach $2$, and we are done. Finally, note that if $a_{0} \equiv 2 (\mod 3)$, then $\{a_{i}\}_{i\ge 0}$ is monotonically increasing since no square can leave a remainder of $2$ upon division by $3$.

Too simple?!?!?! Clearly all $a_0 \equiv 0 \pmod 3$ work. Meanwhile, if $a_0 \equiv 2 \pmod 3$ the sequence will be strictly increasing as there are no perfect squares that are $2 \pmod 3.$ Now, we show by induction that $a_0 \equiv 1 \pmod 3$ doesn't work. The base cases, $a_0=1, 4, 7$ are trivial. Now, suppose that the proposition for $a_0 \leq 3k+1$ holds. Then for $a_0 = 3k+4,$ if the least perfect square congruent to $a_0$ is the same as that of $a_0-3,$ then we are done. Otherwise, if it is of the form $(3m+2)^2,$ we are clearly done. However, if it is of the form $(3m+1)^2,$ we are done too by the strong inductive hypothesis. Therefore $a_0=3k$ is the only solution.

The answer is only $\boxed{\text{multiples of 3}}$. All $a_0 \equiv 2 \pmod{3}$ do not work because of quadratic residues and the resulting unbounded increase. All $a_0 \equiv 0 \pmod{3}$ clearly work as whenever we hit a perfect square the sequence decreases leading to a cycle. The main claim is that all $a_0 \equiv 1 \pmod{3}$ do not work which follows from strong induction. $a_0=4$ does not work by observation. If the next highest perfect square is of the form $(3n+2)^2, n \in \mathbb{Z}$ then the conclusion follows by the logic in the second sentence. Otherwise it is of the form $(3n+1)^2, n \in \mathbb{Z}$ which fails again from induction so we are done.

wait why is this problem so bashy? my sol was just to case on a0 mod 3 (similar to e.g. post #4) and some bounding gives easy gg Since all perfect squares are either $0$ or $1$ modulo $3$, if we have $a_n\equiv2\pmod3$ for some index $n$, then $a_0$ fails. Hence all $a_0$ satisfying $a_0\equiv2\pmod3$ fail. We show that all $a_0$ with $a_0\equiv1\pmod3$ fail as well. By induction, suppose that all elements of $\{1,4,\dots,3k-2\}$ fail. If $3k-2$ is not a perfect square, then having $a_0=3k-2$ gives $a_1=3k+1$, so having $a_0=3k+1$ will fail too. If $3k-2$ is a perfect square, having $a_0=3k+1$ will eventually yield some $a_j$ such that $a_j\le\sqrt{3k-2}+2<3k+1$ for $k>0$ and $a_0=3k+1$ will likewise fail by inductive hypothesis. Note that $A=3$ works if $a_0\equiv0\pmod3$. Indeed, all elements of our sequence will be divisible by $3$. If $9b^2\le a_i<9(b+1)^2$ and $b>1$ for some $i$, then $a_j=3(b+1)<9b^2\le a_i$ for some $j>i$. Hence our sequence will continually exhibit smaller elements until $b=0$, at which point it will cycle between $3$, $6$, and $9$. $\blacksquare$

if \(a_0 \equiv 2 \pmod {3}\) then all \(a_i \equiv 2 \pmod {3}\) so none of them can be a perfect square and it makes every one of them different. if \(a_0 \equiv 0 \pmod{3}\) then we can always find a number \(k\) such that \(n + 3k = 9t^2\) for some \(t\) and thats when the cycle begins when the smallest number of that type is reached. if\(a_0 \equiv 1 \pmod {3}\) then we can always get to \(2 \pmod{3}\) by that sequence and its quite easy to prove, this sequence fails for \(1\) and \(4\) then induction to finish

If $a_0 \equiv 0 \pmod 3$: Note that, every term in the sequence is divisible by $3$. Let $m$ denote the minimum term in the sequence. If $m \ge 6$, then: note that: $(m-3)^2 \ge m$. Thus, there exists some $k$ such that: $(m-3)^2 \ge k^2 \ge m$. Thus: we would have $k \le m-3 < m$ in the sequence, contradiction. Thus: $m=3$ and the sequence $3 \to 6 \to 9 \to 3 \cdots$ repeats. If $a_0 \equiv 1 \pmod 3$: Let $m$ denote the minimum term in the sequence. If $m \equiv 2 \pmod 3$, we are done as $2 \pmod 3$ is not a QR, which implies the sequence gets unbounded and increases monotonously (after some point). If $m \equiv 1 \pmod 3$, then we have $m \ge 4$. Then: $(m-2)^2 \ge m$. Therefore, there exists some integer $k$ such that: $(m-2)^2 \ge k^2 \ge m$. Therefore: $k \le m-2 < m$ exists in the sequence, which leads to contradiction. Thus we must have: $m \equiv 2 \pmod 3$ and we are done with no such value of $a_0$. If $a_0 \equiv 2 \pmod 3$: Evidently, $2 \pmod 3$ is not a QR, which implies the sequence gets unbounded and increases monotonously (after some point). Thus, we are done with $3|a_0$ or any value of $a_0 = 3k$ works, where $k \in \mathbb N$.

didn't expected to use strong induction on this problem Note that $k^2\equiv 0,1\pmod{3}$ for all $k\in\mathbb{N}$. If $a_0\equiv 2\pmod{2}$, then the sequence becomes $a_0,a_0+3,a_0+6,\dots$ and eventually $\{a_n\}$ will be an unbounded sequence, which doesn't meet the problem desire. If $a_0\equiv 0\pmod{3}$, we divide into two cases. First case when $a_0$ is a quadratic number clearly works since $\{a_n\}$ is literally bounded by $a_0$, so by doing infinite terms of the sequence, we'll eventually ended up having a number $A$ such that $a_n=A$ for infinitely many values of $n$. Now if $a_0$ isn't a quadratic form, then we can assure that we will have a quadratic number $a_p=a_0+3p$ for some $p\in\mathbb{N}$, so we're done by using the similar argument as the previous case. Now we come up with the case when $a_0\equiv 1\pmod{3}$. The idea is quite simple; we use strong induction. Base case when $a_0=4$ (quadratic) and $a_0=7$ (not quadratic) are done just by checking them. Assume that for the induction hypothesis, we have $a_0=k$ doesn't works for some $k\in\mathbb{N}$. Note that we can have $k$ and $k+3$ are both quadratic numbers iff $k=1$, which clearly opposing the problem condition ($a_0>1$). So we'll basically divide into three cases from now on. If none of $k$ and $k+3$ are quadratic numbers, then we're done by our induction hypothesis. The similar argument applies for when $k+3$ is a quadratic number. Now for the case when $k$ is quadratic, let $k=t^2$ for some $t\in\mathbb{N}$. Then the sequence becomes $t^2,t,\dots$. Now we have $\{a_n\}$ is bounded by $k=t^2$, so by noticing that $t<t^2=k$ (since $t^2=k\ne 1$ and $t\in\mathbb{N}$) we're done by the induction hypothesis. Overall, all $a_0$ such that $3\mid a_0$ work as solutions. $\blacksquare$