A natural number is called a palindrome if it is read in the same way. from left to right and from right to left (in particular, the last digit of the palindrome coincides with the first and therefore not equal to zero). Squares of two different natural numbers have $1001$ digits. Prove that strictly between these squares, there is one palindrome.
Problem
Source: St. Petersburg 2019 9.1
Tags: number theory, palindromes, Digits
WallyWalrus
03.05.2019 18:23
Let $m,n\in\mathbb{N}$. If $m<n$ and $m^2,n^2$ have each $1001$ digits, results: $10^{1000}\le m^2<n^2<10^{1001}\Longleftrightarrow$ $10^{500}\le m<n<\sqrt{10}\cdot10^{500}$. $n^2-m^2\ge (m+1)^2-m^2=2m+1>2\cdot10^{500}$. Let $m^2=\overline{a_{1000}a_{999}\dots a_{1}a_0}$, where $a_k$ are digits in the decimal base, $a_{1000}\ne 0$. Denote $a_{500}=a$. Case 1: $0\le a\le 8$. Denote $b=a+1$. Consider the palindrome $N=\overline{a_{1000}a_{999}\dots a_{502}a_{501}ba_{501}a_{502}\dots a_{999}a_{1000}}$. $m^2<N$. $N-m^2\le\overline{a_{1000}a_{999}\dots a_{502}a_{501}b99\dots99} -\overline {a_{1000}a_{999}\dots a_{502}a_{501}a00\dots00}=$ $= 2\cdot10^{500}-1<n^2-m^2$ ($9$, respectively $0$ appear 500 times). Hence, $m^2<N<n^2$. Case 2: $a=9$. $m^2<\overline {99\dots99}$ ($9$ appears $1001$ times). Results: $\overline{a_{1000}a_{999}\dots a_{502}a_{501}}<\overline {99\dots99}$ ($9$ appears $500$ times). Denote $\overline{a_{1000}a_{999}\dots a_{502}a_{501}}+1=\overline{b_{499}b_{498}\dots b_1b_0}$. Consider the palindrome $M=\overline{b_{499}b_{498}\dots b_1b_00b_0b_1\dots b_{498}b_{499}}$. $m^2<M$. $M-m^2\le \overline{b_{499}b_{498}\dots b_1b_099\dots99}-\overline{a_{1000}a_{999}\dots a_{502}a_{501}900\dots00}=$ $=2\cdot10^{500}-1<n^2-m^2$ ($9$, respectively $0$ appear 500 times). Hence, $m^2<M<n^2$.