Saudi Arabian IMO Booklet

Let us analyze the sequence $a_i$ defined by $a_1=m$ and $a_{i+1}=a_i+\lfloor \sqrt{a_i}\rfloor$.

Suppose at some step $a_k$ is a perfect square, say $a_k=n^2$ for some integer $n\ge 1$. Then: $$a_{k+1}=a_k+\lfloor \sqrt{a_k}\rfloor =n^2+\lfloor n\rfloor =n^2+n=n(n+1)$$

Now, consider the next terms: $$a_{k+2}=a_{k+1}+\lfloor \sqrt{a_{k+1}}\rfloor$$ But $a_{k+1}=n(n+1)$, and $\sqrt{n(n+1)}$ is between $n$ and $n+1$. Specifically, $n<\sqrt{n(n+1)}<n+1$ for $n\ge 1$, so $\lfloor \sqrt{n(n+1)}\rfloor =n$. Therefore: $$a_{k+2}=n(n+1)+n=n^2+2n=(n+1{)}^2-1$$

Now, $a_{k+3}=a_{k+2}+\lfloor \sqrt{a_{k+2}}\rfloor$ But $a_{k+2}=(n+1{)}^2-1$, so $\sqrt{a_{k+2}}=\sqrt{(n+1{)}^2-1}$. Since $(n+1{)}^2-1<(n+1{)}^2$, $\sqrt{a_{k+2}}<n+1$, and $\sqrt{a_{k+2}}>n$ (since $(n+1{)}^2-1>n^2$ for $n\ge 1$), so $\lfloor \sqrt{a_{k+2}}\rfloor =n$. Thus: $$a_{k+3}=(n+1{)}^2-1+n=n^2+2n+n-1=n^2+3n-1$$

But let's look for the next perfect square. Let us try to see if the sequence can reach $(n+1{)}^2$. From above, $a_{k+2}=(n+1{)}^2-1$, $a_{k+3}=n^2+3n-1$.

Let us try to generalize. For large $a_i$, $\lfloor \sqrt{a_i}\rfloor$ increases slowly compared to $a_i$, so the sequence grows slowly.

But more importantly, we can show that for any starting $m$, the sequence will eventually reach a perfect square, and then the above process repeats.

Let us prove that for any $a_i$, there exists $j>i$ such that $a_j$ is a perfect square.

Let $a_i$ be arbitrary. Let $n=\lfloor \sqrt{a_i}\rfloor$. Then $n^2\le a_i<(n+1{)}^2$.

If $a_i=n^2$, we are done. If not, $a_i=n^2+r$ for $1\le r<2n+1$.

At each step, $a_{i+1}=a_i+\lfloor \sqrt{a_i}\rfloor$. Since $a_i\ge n^2$, $\sqrt{a_i}\ge n$, so $\lfloor \sqrt{a_i}\rfloor \ge n$.

Let us consider the sequence of $a_i$ modulo $n$:

Let us try to reach $(n+1{)}^2=n^2+2n+1$.

From $a_i=n^2+r$, after $s$ steps, $a_{i+s}=n^2+r+sn$ (since $\lfloor \sqrt{a_{i+t}}\rfloor =n$ for $a_{i+t}<(n+1{)}^2$).

We want $a_{i+s}=(n+1{)}^2=n^2+2n+1$. So: $$n^2+r+sn=n^2+2n+1$$ $$r+sn=2n+1$$ $$sn=2n+1-r$$ $$s=\frac{2n+1-r}{n}$$

Since $1\le r<2n+1$, $2n+1-r$ is positive and less than $2n$. So $s$ is an integer if and only if $n$ divides $2n+1-r$.

But even if $s$ is not integer, after $t$ steps, $a_{i+t}$ will reach or exceed $(n+1{)}^2$, at which point $\lfloor \sqrt{a_{i+t}}\rfloor =n+1$.

Therefore, after a bounded number of steps, the sequence will cross from $n^2$ to $(n+1{)}^2$.

Now, consider the difference $a_{i+t}-(n+1{)}^2$. For some $t$, $a_{i+t}$ will be exactly $(n+1{)}^2$ if $a_i$ is congruent to $n^2$ modulo $n$.

But even if not, after passing $(n+1{)}^2$, the process repeats with $n$ replaced by $n+1$.

Therefore, for any starting $m$, the sequence will eventually hit a perfect square, and then the process repeats. Thus, the sequence contains infinitely many perfect squares.

Therefore, the sequence $a_i$ contains infinitely many perfect squares.