Полный квадрат

[Edward_Tur]

Назовем усложнением числа приписывание к нему одной цифры в начало, в конец или между любыми двумя его цифрами. Существует ли натуральное число, из которого невозможно получить полный квадрат с помощью ста усложнений?

Источник - ММО-2008

[Руст]

Да. Рассмотрим N значные числа их $9*10^{N-1}$. Добавлением 100 цифр получаем 100+N значное число. Среди них квадратами являются $M=[10^{50+N/2}]-[10^{(99+n)/2}]$. От каждого квадрата вычеркиванием 100 цифр получаем $C_{N+100}^{100}$ чисел, даже если все они разные получаются только $M*C_{N+100}^{100}<9*10^{N-1}$ N значных чисел. Это меньше их общего количества при больших N.
Конечно можно получить и конструктивное доказательство. Но это сложнее.