IMO Shortlist

Answer. No.

Assume that $a_{1}, a_{2}, a_{3}, \ldots$ is such a sequence. For each positive integer $k$, let $y_{k}= \overline{a_{k} a_{k-1} \ldots a_{1}}$. By the assumption, for each $k > N$ there exists a positive integer $x_{k}$ such that $y_{k}=x_{k}^{2}$.

I. For every $n$, let $5^{\gamma_{n}}$ be the greatest power of $5$ dividing $x_{n}$. Let us show first that $2 \gamma_{n} \geqslant n$ for every positive integer $n > N$.

Assume, to the contrary, that there exists a positive integer $n > N$ such that $2 \gamma_{n} < n$, which yields
$$y_{n+1}=\overline{a_{n+1} a_{n} \ldots a_{1}}=10^{n} a_{n+1}+\overline{a_{n} a_{n-1} \ldots a_{1}}=10^{n} a_{n+1}+y_{n}=5^{2 \gamma_{n}}\left(2^{n} 5^{n-2 \gamma_{n}} a_{n+1}+\frac{y_{n}}{5^{2 \gamma_{n}}}\right) .$$
Since $5 \nmid y_{n} / 5^{2 \gamma_{n}}$, we obtain $\gamma_{n+1}=\gamma_{n}<n<n+1$. By the same arguments we obtain that $\gamma_{n}=\gamma_{n+1}=\gamma_{n+2}=\ldots$. Denote this common value by $\gamma$.

Now, for each $k \geqslant n$ we have
$$\left(x_{k+1}-x_{k}\right)\left(x_{k+1}+x_{k}\right)=x_{k+1}^{2}-x_{k}^{2}=y_{k+1}-y_{k}=a_{k+1} \cdot 10^{k}$$
One of the numbers $x_{k+1}-x_{k}$ and $x_{k+1}+x_{k}$ is not divisible by $5^{\gamma+1}$ since otherwise one would have $5^{\gamma+1} \mid \left(\left(x_{k+1}-x_{k}\right)+\left(x_{k+1}+x_{k}\right)\right)=2 x_{k+1}$. On the other hand, we have $5^{k} \mid \left(x_{k+1}-x_{k}\right)\left(x_{k+1}+x_{k}\right)$, so $5^{k-\gamma}$ divides one of these two factors. Thus we get
$$5^{k-\gamma} \leqslant \max \left\{x_{k+1}-x_{k}, x_{k+1}+x_{k}\right\}<2 x_{k+1}=2 \sqrt{y_{k+1}}<2 \cdot 10^{(k+1) / 2}$$
which implies $5^{2 k}<4 \cdot 5^{2 \gamma} \cdot 10^{k+1}$, or $(5 / 2)^{k}<40 \cdot 5^{2 \gamma}$. The last inequality is clearly false for sufficiently large values of $k$. This contradiction shows that $2 \gamma_{n} \geqslant n$ for all $n > N$.

II. Consider now any integer $k > \max \{N / 2, 2\}$. Since $2 \gamma_{2 k+1} \geqslant 2 k+1$ and $2 \gamma_{2 k+2} \geqslant 2 k+2$, we have $\gamma_{2 k+1} \geqslant k+1$ and $\gamma_{2 k+2} \geqslant k+1$. So, from $y_{2 k+2}=a_{2 k+2} \cdot 10^{2 k+1}+y_{2 k+1}$ we obtain $5^{2 k+2} \mid y_{2 k+2}-y_{2 k+1}=a_{2 k+2} \cdot 10^{2 k+1}$ and thus $5 \mid a_{2 k+2}$, which implies $a_{2 k+2}=5$. Therefore,
$$\left(x_{2 k+2}-x_{2 k+1}\right)\left(x_{2 k+2}+x_{2 k+1}\right)=x_{2 k+2}^{2}-x_{2 k+1}^{2}=y_{2 k+2}-y_{2 k+1}=5 \cdot 10^{2 k+1}=2^{2 k+1} \cdot 5^{2 k+2} .$$
Setting $A_{k}=x_{2 k+2} / 5^{k+1}$ and $B_{k}=x_{2 k+1} / 5^{k+1}$, which are integers, we obtain
$$\begin{equation*} \left(A_{k}-B_{k}\right)\left(A_{k}+B_{k}\right)=2^{2 k+1} \tag{1} \end{equation*}$$
Both $A_{k}$ and $B_{k}$ are odd, since otherwise $y_{2 k+2}$ or $y_{2 k+1}$ would be a multiple of $10$ which is false by $a_{1} \neq 0$; so one of the numbers $A_{k}-B_{k}$ and $A_{k}+B_{k}$ is not divisible by $4$. Therefore (1) yields $A_{k}-B_{k}=2$ and $A_{k}+B_{k}=2^{2 k}$, hence $A_{k}=2^{2 k-1}+1$ and thus
$$x_{2 k+2}=5^{k+1} A_{k}=10^{k+1} \cdot 2^{k-2}+5^{k+1}>10^{k+1}$$
since $k \geqslant 2$. This implies that $y_{2 k+2}>10^{2 k+2}$ which contradicts the fact that $y_{2 k+2}$ contains $2 k+2$ digits. The desired result follows.

Again, we assume that a sequence $a_{1}, a_{2}, a_{3}, \ldots$ satisfies the problem conditions, introduce the numbers $x_{k}$ and $y_{k}$ as in the previous solution, and notice that
$$\begin{equation*} y_{k+1}-y_{k}=\left(x_{k+1}-x_{k}\right)\left(x_{k+1}+x_{k}\right)=10^{k} a_{k+1} \tag{2} \end{equation*}$$
for all $k > N$. Consider any such $k$. Since $a_{1} \neq 0$, the numbers $x_{k}$ and $x_{k+1}$ are not multiples of $10$, and therefore the numbers $p_{k}=x_{k+1}-x_{k}$ and $q_{k}=x_{k+1}+x_{k}$ cannot be simultaneously multiples of $20$, and hence one of them is not divisible either by $4$ or by $5$. In view of (2), this means that the other one is divisible by either $5^{k}$ or by $2^{k-1}$. Notice also that $p_{k}$ and $q_{k}$ have the same parity, so both are even.

On the other hand, we have $x_{k+1}^{2}=x_{k}^{2}+10^{k} a_{k+1} \geqslant x_{k}^{2}+10^{k}>2 x_{k}^{2}$, so $x_{k+1} / x_{k}>\sqrt{2}$, which implies that
$$\begin{equation*} 1<\frac{q_{k}}{p_{k}}=1+\frac{2}{x_{k+1} / x_{k}-1}<1+\frac{2}{\sqrt{2}-1}<6 \tag{3} \end{equation*}$$
Thus, if one of the numbers $p_{k}$ and $q_{k}$ is divisible by $5^{k}$, then we have
$$10^{k+1}>10^{k} a_{k+1}=p_{k} q_{k} \geqslant \frac{\left(5^{k}\right)^{2}}{6}$$
and hence $(5 / 2)^{k}<60$ which is false for sufficiently large $k$. So, assuming that $k$ is large, we get that $2^{k-1}$ divides one of the numbers $p_{k}$ and $q_{k}$. Hence
$$\left\{p_{k}, q_{k}\right\}=\left\{2^{k-1} \cdot 5^{r_{k}} b_{k}, 2 \cdot 5^{k-r_{k}} c_{k}\right\} \quad \text{ with nonnegative integers } b_{k}, c_{k}, r_{k} \text{ such that } b_{k} c_{k}=a_{k+1} .$$
Moreover, from (3) we get
$$6>\frac{2^{k-1} \cdot 5^{r_{k}} b_{k}}{2 \cdot 5^{k-r_{k}} c_{k}} \geqslant \frac{1}{36} \cdot\left(\frac{2}{5}\right)^{k} \cdot 5^{2 r_{k}} \quad \text{ and } \quad 6>\frac{2 \cdot 5^{k-r_{k}} c_{k}}{2^{k-1} \cdot 5^{r_{k}} b_{k}} \geqslant \frac{4}{9} \cdot\left(\frac{5}{2}\right)^{k} \cdot 5^{-2 r_{k}}$$
so
$$\begin{equation*} \alpha k+c_{1}<r_{k}<\alpha k+c_{2} \quad \text{ for } \alpha=\frac{1}{2} \log _{5}\left(\frac{5}{2}\right)<1 \text{ and some constants } c_{2}>c_{1} . \tag{4} \end{equation*}$$
Consequently, for $C=c_{2}-c_{1}+1-\alpha>0$ we have
$$\begin{equation*} (k+1)-r_{k+1} \leqslant k-r_{k}+C \tag{5} \end{equation*}$$
Next, we will use the following easy lemma.

Lemma. Let $s$ be a positive integer. Then $5^{s+2^{s}} \equiv 5^{s}\left(\bmod 10^{s}\right)$.

Proof. Euler's theorem gives $5^{2^{s}} \equiv 1\left(\bmod 2^{s}\right)$, so $5^{s+2^{s}}-5^{s}=5^{s}\left(5^{2^{s}}-1\right)$ is divisible by $2^{s}$ and $5^{s}$.

Now, for every large $k$ we have
$$\begin{equation*} x_{k+1}=\frac{p_{k}+q_{k}}{2}=5^{r_{k}} \cdot 2^{k-2} b_{k}+5^{k-r_{k}} c_{k} \equiv 5^{k-r_{k}} c_{k} \quad\left(\bmod 10^{r_{k}}\right) \tag{6} \end{equation*}$$
since $r_{k} \leqslant k-2$ by (4); hence $y_{k+1} \equiv 5^{2\left(k-r_{k}\right)} c_{k}^{2}\left(\bmod 10^{r_{k}}\right)$. Let us consider some large integer $s$, and choose the minimal $k$ such that $2\left(k-r_{k}\right) \geqslant s+2^{s}$; it exists by (4). Set $d=2\left(k-r_{k}\right)-\left(s+2^{s}\right)$. By (4) we have $2^{s}<2\left(k-r_{k}\right)<\left(\frac{2}{\alpha}-2\right) r_{k}-\frac{2 c_{1}}{\alpha}$; if $s$ is large this implies $r_{k}>s$, so (6) also holds modulo $10^{s}$. Then (6) and the lemma give
$$\begin{equation*} y_{k+1} \equiv 5^{2\left(k-r_{k}\right)} c_{k}^{2}=5^{s+2^{s}} \cdot 5^{d} c_{k}^{2} \equiv 5^{s} \cdot 5^{d} c_{k}^{2} \quad\left(\bmod 10^{s}\right) \tag{7} \end{equation*}$$
By (5) and the minimality of $k$ we have $d \leqslant 2 C$, so $5^{d} c_{k}^{2} \leqslant 5^{2 C} \cdot 81=D$. Using $5^{4}<10^{3}$ we obtain
$$5^{s} \cdot 5^{d} c_{k}^{2}<10^{3 s / 4} D<10^{s-1}$$
for sufficiently large $s$. This, together with (7), shows that the $s$$\text{th}$ digit from the right in $y_{k+1}$, which is $a_{s}$, is zero. This contradicts the problem condition.