Олимпиадная задача Горбачева: усложнения чисел и невозможность получить полный квадрат
Задача
Назовём усложнением числа приписывание к нему одной цифры в начало, в конец или между любыми двумя его цифрами. Существует ли натуральное число, из которого невозможно получить полный квадрат с помощью ста усложнений?
Решение
Докажем, что среди 500-значных чисел найдётся искомое. Если 500-значное число усложнить 100 раз, получится 600-значное число. Существует менее 7·10299 600-значных полных квадратов ((3·10299)² < 10599). Зафиксируем k – один из этих квадратов. Количество чисел, из которых его можно получить описанной в условии операцией, не превосходит количества способов зачеркнуть в нем 100 цифр, то есть
Таким образом, общее количество 500-значных чисел, из которых может быть получен полный квадрат, не превосходит 7·10299·2600 < 7·10299·8200 < 9·10449, то есть меньше количества 500-значных чисел.
Ответ
Существует.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь