International Mathematical Olympiad Shortlisted Problems

Answer. No.

Assume that $a_1,a_2,a_3,\dots$ is such a sequence. For each positive integer $k$, let $y_k=\overline{a_k{a}_{k-1}\dots 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⩾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\dots a_1}=10^n{a}_{n+1}+\overline{a_n{a}_{n-1}\dots 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}=\dots$. Denote this common value by $\gamma$.

Now, for each $k⩾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)=2x_{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 }⩽\max \left\{x_{k+1}-x_k,x_{k+1}+x_k\right\}<2x_{k+1}=2\sqrt{y_{k+1}}<2\cdot 10^{(k+1)/2}$$ which implies $5^{2k}<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⩾n$ for all $n>N$.

II. Consider now any integer $k>\max \{N/2,2\}$. Since $2{\gamma }_{2k+1}⩾2k+1$ and $2{\gamma }_{2k+2}⩾2k+2$, we have ${\gamma }_{2k+1}⩾k+1$ and ${\gamma }_{2k+2}⩾k+1$. So, from $y_{2k+2}=a_{2k+2}\cdot 10^{2k+1}+y_{2k+1}$ we obtain $5^{2k+2}\mid y_{2k+2}-y_{2k+1}=a_{2k+2}\cdot 10^{2k+1}$ and thus $5\mid a_{2k+2}$, which implies $a_{2k+2}=5$. Therefore, $$\left(x_{2k+2}-x_{2k+1}\right)\left(x_{2k+2}+x_{2k+1}\right)=x_{2k+2}^2-x_{2k+1}^2=y_{2k+2}-y_{2k+1}=5\cdot 10^{2k+1}=2^{2k+1}\cdot 5^{2k+2}.$$ Setting $A_k=x_{2k+2}/5^{k+1}$ and $B_k=x_{2k+1}/5^{k+1}$, which are integers, we obtain $$\begin{array}{c}\left(A_k-B_k\right)\left(A_k+B_k\right)=2^{2k+1}\end{array}\text{\hspace{1em}(1)}$$ Both $A_k$ and $B_k$ are odd, since otherwise $y_{2k+2}$ or $y_{2k+1}$ would be a multiple of $10$ which is false by $a_1\ne 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^{2k}$, hence $A_k=2^{2k-1}+1$ and thus $$x_{2k+2}=5^{k+1}{A}_k=10^{k+1}\cdot 2^{k-2}+5^{k+1}>10^{k+1}$$ since $k⩾2$. This implies that $y_{2k+2}>10^{2k+2}$ which contradicts the fact that $y_{2k+2}$ contains $2k+2$ digits. The desired result follows.

---

Alternative solution.

Again, we assume that a sequence $a_1,a_2,a_3,\dots$ satisfies the problem conditions, introduce the numbers $x_k$ and $y_k$ as in the previous solution, and notice that $$\begin{array}{c}{y}_{k+1}-y_k=\left(x_{k+1}-x_k\right)\left(x_{k+1}+x_k\right)=10^k{a}_{k+1}\end{array}\text{\hspace{1em}(2)}$$ for all $k>N$. Consider any such $k$. Since $a_1\ne 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}⩾x_k^2+10^k>2x_k^2$, so $x_{k+1}/x_k>\sqrt{2}$, which implies that $$\begin{array}{c}1<\frac{q_k}{p_k}=1+\frac{2}{x_{k+1}/x_k-1}<1+\frac{2}{\sqrt{2}-1}<6\end{array}\text{\hspace{1em}(3)}$$ 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⩾\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\}\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}⩾\frac{1}{36}\cdot {\left(\frac{2}{5}\right)}^k\cdot 5^{2r_k}\text{ and }6>\frac{2\cdot 5^{k-r_k}{c}_k}{2^{k-1}\cdot 5^{r_k}{b}_k}⩾\frac{4}{9}\cdot {\left(\frac{5}{2}\right)}^k\cdot 5^{-2r_k}$$ so $$\begin{array}{c}\alpha k+c_1<r_k<\alpha k+c_2\text{ for }\alpha =\frac{1}{2}{\log }_5\left(\frac{5}{2}\right)<1\text{ and some constants }{c}_2>c_1.\end{array}\text{\hspace{1em}(4)}$$ Consequently, for $C=c_2-c_1+1-\alpha >0$ we have $$\begin{array}{c}(k+1)-r_{k+1}⩽k-r_k+C\end{array}\text{\hspace{1em}(5)}$$ Next, we will use the following easy lemma.

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

Proof. Euler's theorem gives $5^{2^s}\equiv 1\left(\mathrm{mod}{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{array}{c}{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\left(\mathrm{mod}10^{r_k}\right)\end{array}\text{\hspace{1em}(6)}$$ since $r_k⩽k-2$ by (4); hence $y_{k+1}\equiv 5^{2\left(k-r_k\right)}{c}_k^2\left(\mathrm{mod}10^{r_k}\right)$. Let us consider some large integer $s$, and choose the minimal $k$ such that $2\left(k-r_k\right)⩾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{2c_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{array}{c}{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\left(\mathrm{mod}10^s\right)\end{array}\text{\hspace{1em}(7)}$$ By (5) and the minimality of $k$ we have $d⩽2C$, so $5^d{c}_k^2⩽5^{2C}\cdot 81=D$. Using $5^4<10^3$ we obtain $$5^s\cdot 5^d{c}_k^2<10^{3s/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.