Estonian Mathematical Olympiad

For any positive integer $a$, let $s(a)$ denote the sum of digits of $a$. Clearly $s(n+1)=s(n)+1$ unless the last digit of $n+1$ is zero. The only two consecutive integers that are both perfect squares are $0$ and $1$, but $s(n)=0$ is impossible for a positive $n$. The contradiction shows that the last digit of $n+1$ must be $0$ and the last digit of $n$ must be $9$.

Let $n$ be an interesting positive integer that ends with exactly $m$ digits $9$. Clearly $s(n)-s(n+1)=9m-1$. Note that a perfect square is congruent to $0$, $1$, $4$ or $7$ modulo $9$. As $s(n)-s(n+1)=9m-1\equiv 8(\mathrm{mod}9)$, we must have $s(n)\equiv 0(\mathrm{mod}9)$ and $s(n+1)\equiv 1(\mathrm{mod}9)$. But $s(n+1)=1$ is impossible, because this would require $n+1$ to be a power of $10$, in the case of which $n$ and $n+1$ would not consist of the same number of digits. Thus $s(n+1)\ge 8^2=64$, as $8^2$ is the next smallest perfect square congruent to $1$ modulo $9$. But as $s(n)>s(n+1)$, we have $s(n)\ge 9^2=81$. This implies that $n$ must contain at least $9$ digits. Containing exactly $9$ digits would be possible only if $n$ consisted entirely of nines, but in such case $n+1$ would contain one more digit. Hence $n$ must contain at least $10$ digits.

Consider now the $10$-digit number $n=788888899$. In this case $m=2$, $s(n)=81=9^2$ and $s(n+1)=81-9\cdot 2+1=64=8^2$, thus $n$ is interesting. Inserting zeros between $7$ and $8$ does not influence $s(n)$ and $s(n+1)$. So we can obtain an $m$-digit interesting number for every $m\ge 10$.