Maths Olympiad Prep

Library / /285 of 520

Number theory Difficulty 6.6 National olympiad Prove it

Determine whether there exists an infinite sequence of nonzero digits a1,a2,a3,a_{1}, a_{2}, a_{3}, \ldots and a positive integer NN such that for every integer k>Nk>N, the number akak1a1\overline{a_{k} a_{k-1} \ldots a_{1}} is a perfect square. (Iran) Answer. No.

Solution

Assume that a1,a2,a3,a_{1}, a_{2}, a_{3}, \ldots is such a sequence. For each positive integer kk, let yk=y_{k}= akak1a1\overline{a_{k} a_{k-1} \ldots a_{1}}. By the assumption, for each k>Nk>N there exists a positive integer xkx_{k} such that yk=xk2y_{k}=x_{k}^{2}. I. For every nn, let 5γn5^{\gamma_{n}} be the greatest power of 5 dividing xnx_{n}. Let us show first that 2γnn2 \gamma_{n} \geqslant n for every positive integer n>Nn>N. Assume, to the contrary, that there exists a positive integer n>Nn>N such that 2γn<n2 \gamma_{n} < n. Then 52γnxn2=yn5^{2 \gamma_{n}} \mid x_{n}^2 = y_{n}, but 5nyn5^n \nmid y_{n}, which contradicts the fact that yny_{n} is a perfect square. Therefore, 2γnn2 \gamma_{n} \geqslant n for every positive integer n>Nn>N. II. Consider now any integer k>max{N/2,2}k>\max \{N / 2,2\}. Since 2γ2k+12k+12 \gamma_{2 k+1} \geqslant 2 k+1 and 2γ2k+22k+22 \gamma_{2 k+2} \geqslant 2 k+2, we have γ2k+1k+1\gamma_{2 k+1} \geqslant k+1 and γ2k+2k+1\gamma_{2 k+2} \geqslant k+1. So, from y2k+2=a2k+2102k+1+y2k+1y_{2 k+2}=a_{2 k+2} \cdot 10^{2 k+1}+y_{2 k+1} we obtain 52k+2y2k+2y2k+1=a2k+2102k+15^{2 k+2} \mid y_{2 k+2}-y_{2 k+1}=a_{2 k+2} \cdot 10^{2 k+1} and thus 5a2k+25 \mid a_{2 k+2}, which implies a2k+2=5a_{2 k+2}=5. Therefore, (x2k+2x2k+1)(x2k+2+x2k+1)=x2k+22x2k+12=y2k+2y2k+1=5102k+1=22k+152k+2. \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 Ak=x2k+2/5k+1A_{k}=x_{2 k+2} / 5^{k+1} and Bk=x2k+1/5k+1B_{k}=x_{2 k+1} / 5^{k+1}, which are integers, we obtain (AkBk)(Ak+Bk)=22k+1. \left(A_{k}-B_{k}\right)\left(A_{k}+B_{k}\right)=2^{2 k+1} . Both AkA_{k} and BkB_{k} are odd, since otherwise y2k+2y_{2 k+2} or y2k+1y_{2 k+1} would be a multiple of 10 which is false by a10a_{1} \neq 0; so one of the numbers AkBkA_{k}-B_{k} and Ak+BkA_{k}+B_{k} is not divisible by 4 . Therefore (1) yields AkBk=2A_{k}-B_{k}=2 and Ak+Bk=22kA_{k}+B_{k}=2^{2 k}, hence Ak=22k1+1A_{k}=2^{2 k-1}+1 and thus x2k+2=5k+1Ak=10k+12k2+5k+1>10k+1, x_{2 k+2}=5^{k+1} A_{k}=10^{k+1} \cdot 2^{k-2}+5^{k+1}>10^{k+1}, since k2k \geqslant 2. This implies that y2k+2>102k+2y_{2 k+2}>10^{2 k+2} which contradicts the fact that y2k+2y_{2 k+2} contains 2k+22 k+2 digits. The desired result follows.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.