For every natural number $x{}$, let $P(x)$ be the product of the digits of the number $x{}$. Is there a natural number $n{}$ such that the numbers $P(n)$ and $P(n^2)$ are non-zero squares of natural numbers, where the number of digits of the number $n{}$ is equal to (a) 2021 and (b) 2022?
Problem
Source: BMO Shortlist 2022, N3
Tags: number theory
Marinchoo
14.05.2023 11:41
The answer to both $a)$ and $b)$ is positive. We'll show that actually for any number of digits, there is a positive integer $n$ such that $P(n)$ and $P(n^2)$ are both squares. $a)$ We'll prove that $\underbrace{6\dots 6}_{2k}1^2 = \underbrace{4\dots 4}_{2k-1} 36 \underbrace{8\dots 8}_{2k-2} 921$ for all positive integers $k$. If $n_{k}=\frac{2}{3}\cdot (10^{2k+1}-1)-5$, then picking $k = 1010$ suffices as $P(n_{k}) = 6^{2k}$ and $P(n_{k}^2) = 4^{2k-1}\cdot 8^{2k-2}\cdot 18^2 = (3\cdot 2^{5k-1})^2$. To prove the above identity we simply evaluate both sides of the equation separately: \begin{align*} \underbrace{6\dots 6}_{2k}1^2 &= \left(\frac{2}{3}\cdot (10^{2k+1}-1)-5\right)^2 \\ &= \frac{4}{9}\cdot\left(10^{2k+1}-1\right)^2-\frac{20}{3}\cdot\left(10^{2k+1}-1\right)+25\\ &= \frac{4}{9}\cdot 10^{4k+2} - \frac{68}{9}\cdot 10^{2k+1} + \frac{289}{9} \end{align*}\begin{align*} \underbrace{4\dots 4}_{2k-1} 36 \underbrace{8\dots 8}_{2k-2} 921 &= \frac{4}{9}\cdot \left(10^{4k+2}-10^{2k+3}\right)+36\cdot 10^{2k+1}+\frac{8}{9}\cdot(10^{2k+1}-1)+921-888\\ &= \frac{4}{9}\cdot 10^{4k+2} - \frac{68}{9}\cdot 10^{2k+1} + \frac{289}{9} \end{align*}$b)$ We'll prove that $\underbrace{6\dots 6}_{2k+1}329^2 = \underbrace{4\dots 4}_{2k} 3994 \underbrace{2\dots 2}_{2k-2} 336241$ for all positive integers $k$. If $n_{k}=\underbrace{6\dots 6}_{2k+1}329$, then picking $k = 1009$ suffices as $P(n_{k}) = (3\cdot 6^{k+1})^2$ and $P(n_{k}^2) = (3^{4}\cdot 2^{3k+2})^2$. To prove the above identity we simply evaluate both sides of the equation separately: \begin{align*} \underbrace{6\dots 6}_{2k+1}329^2 &= \left(\frac{2}{3}\cdot (10^{2k+4}-1)-337\right)^2 \\ &= \frac{4}{9}\cdot \left(10^{2k+4}-1\right)^2 - \frac{1348}{3}\left(10^{2k+4}-1\right) + 113569\\ &= \frac{4}{9}\cdot 10^{4k+8} - \frac{4052}{9}10^{2k+4}+ \frac{1026169}{9} \end{align*}\begin{align*} \underbrace{4\dots 4}_{2k} 3994 \underbrace{2\dots 2}_{2k-2} 336241 &= \frac{4}{9}\cdot \left(10^{4k+8}-10^{2k+8}\right)+3994\cdot 10^{2k+4}+\frac{2}{9}\cdot(10^{2k+4}-1)+336241-222222\\ &= \frac{4}{9}\cdot 10^{4k+8} - \frac{4052}{9}10^{2k+4}+ \frac{1026169}{9} \end{align*} The above solution proves that for all integers $m\geq 5$, there is a number $n$ with $m$ digits. Indeed, $a)$ covers all odd numbers $m\geq 3$, and the construction in $b)$ works for all even $m\geq 6$. The remaining small values of $m$ can be dealt with directly: take $n=1$, $n=88$, and $n=1488$ respectively for $m=1,2,4$.
First of all, the most important thing in Yes/No problems is finding the correct answer. Here checking small cases (finding out $88$ is the only $\emph{nice}$ two-digit integer is kind of frustrating, but there are many three-digit ones, so we're ok) really gives you the feeling that not only should there be such $n$, but that there should be a lot of solutions. This is only natural as the function $P(\bullet)$ doesn't have any particularly nice properties and we can't say much about it except that $n$ must have an even number of $7$'s and $5$'s in order for $P(n)$ to be a perfect square for example. Having seen JBMO 1998 #1, I knew this problem would probably rely on a similar (seemingly miraculous) identity. Trying out $n = \overline{aa\dots aab}$, it turns out that $a = 6$ is actually really nice because it makes the first ~half digits of $n^2$ fours (so we don't have to worry about them for the product). Moreover, another ~half of the decimal representation of $n^2$ will be a continuous string of the same digit. Hence, $P(n^2)$ will be easy to calculate this way. Plugging $b=1$ immediately solves $a)$. The second part is trickier though (or at least I didn't find an easy construction). I knew the same idea had to work, so I started calculating the numbers $\overline{666r}^2$ for $P(r) = 6N^2$ until $r = 329$ worked (note that this doesn't require anywhere near $329$ checks for $r$ due to the second condition).