Mathematical Reflections 2017, Issue 3 - Problem O409

Problem:
Find all positive integers $n$ for which there are $n+1$ digits in base $10$, not necessarily distinct, such that at least $2n$ permutations of those digits produce $(n+1)$-digit perfect squares, with leading zeros not allowed. Note that two different permutations are considered distinct even if they lead to the same digit string due to repetition among the digits.

Proposed by Titu Andreescu, University of Texas at Dallas, USA

Solution:
We prove that all $n \geq 2$ satisfy the given property. Clearly, $n=1$ doesn't satisfy the given property. If $n=2$, take $144$ and the permutations $\{\textrm{id},(23),(13),(132)\}$ acting on the digits of $144$. If $n=3$, take $1444$ and the permutations $\{\textrm{id},(23),(24),(34),(234),(243)\}$ acting on the digits of $1444$. If $n=5$, take $160000$ and the $4!=24$ permutations acting on the digits of $160000$ moving only the zeros. Now, let $n \geq 4$ be even. Then, $n=2k$ for some integer $k \geq 2$. Observe that there are at least $(2k)!$ permutations acting on the digits of $10^{2k}$ that produces a perfect square (namely, the ones fixing $1$ in the first position and moving the other zeros) and $(2k)! \geq 4k$ for any integer $k \geq 2$. Let $n \geq 7$ be odd. Then, $n=2k-1$ for some integer $k \geq 3$. Observe that there are at least $k!\cdot (k-1)!$ permutations acting on the digits of $\underbrace{11\ldots 11}_{k \textrm{ ones}} \underbrace{55\ldots 55}_{k-1 \textrm{ fives}} 6$ that produces a perfect square and $k! \cdot (k-1)! \geq 2(2k-1)$ for any integer $k \geq 4$. The conclusion follows.