Selection tests for the Balkan Mathematical Olympiad 2013

We prove this by induction on $n$.

For $n=1,2,3$, the numbers $1$, $34$, and $122$ are good numbers and all their odd digits are less than $5$.

Assume that $a_n$ is an $n$-digit good number and all its odd digits are less than $5$.

If $a_n$ has an even digit $2m$, remove this digit and replace it by $4$ digits $mmmm$ to obtain an $n+3$-digit number. The sum of squares of the digits of this new number is equal to the sum of squares of the digits of $a_n$ and is therefore a perfect square. Notice that all the odd digits of this new $n+3$-digit good number are less than $5$. For example, replace the $4$ in the $2$-digit good number $34$ by $2222$ to obtain the $5$-digit good number $32222$.

If $a_n$ has no even digit, all its digits are less than $5$. We can multiply all its digits by $2$ to obtain a new $n$-digit good number. Choose one of the new even digits $2m$, remove it and replace it by four digits $mmmm$ to obtain a new $n+3$-digit good number and its odd digits $m$ are less than $5$. For example, for the $4$-digit good number $3333$ multiply all its digits by $2$ to obtain the $4$-digit good number $6666$ and then replace one of the $6$ by $3333$ to obtain the $7$-digit good number $3333666$.

This proves by induction that for any positive integer $n$, there exists an $n$-digit good number.