ВсОШ 2022, 11 класс, задача 7
( баллов) Для натурального числа рассмотрим все различные точные квадраты, которые можно получить из вычёркиванием одной цифры в его десятичной записи. Докажите, что количество этих квадратов не превосходит некоторой величины, не зависящей от .
(С. Берлов, Ф. Петров, Д. Крачун)
Ответ
Решение.
Пусть число состоит из цифры. Считаем далее, что : меньшие числа не влияют на искомую ограниченность. Для обозначим через число, получающееся удалением из числа цифры с номером с конца. Обозначим через количество точных квадратов в множестве . Наша цель — доказать, что ограничено сверху.
Пусть , где не кратно . Если нечётно, то число может быть точным квадратом только при , так что в этом случае . Если чётно, то заключительные нулей не влияют на дело, поэтому . Поэтому далее считаем, что не кратно .
Выделим множество из номеров , для которых — точный квадрат, причём натуральные числа , , попарно различны. Отметим следующее: 1. , следовательно при всех ; 2. ; 3. кратно .
Из свойства следует, что для различных номеров из имеет место оценка
Сопоставляя это со свойством , получаем, что . Таким образом, все элементы , кроме, быть может, одного, больше, чем . Обозначим , тогда и .
Пусть — два элемента множества . Тогда по свойствам , имеем
С другой стороны, по свойству число кратно . Положим . Хотя бы одно из чисел , кратно , и хотя бы одно кратно . Кроме того, если нечётно, то нечётны числа , , поэтому одно из чисел , не кратно — а другое, соответственно, кратно . Иначе не кратно , и аналогичным образом получаем, что одно из чисел , кратно .
Рассмотрим пятиэлементное подмножество , наименьший элемент обозначим , а наибольший . Обозначим . Если нечётно, положим , ; иначе положим , . Из доказанного следует, что элементы множества дают не более двух различных остатков по модулю и не более двух различных остатков по модулю . Значит, в найдутся два различных элемента такие, что кратно . Тогда по получаем
откуда следует, что . Таким образом, если разбить отрезок на группы подряд идущих чисел, в каждой из которых отношение любых двух элементов меньше чем (количество таких групп меньше, например, миллиона), то любая из этих групп содержит не более элементов множества . Отсюда вытекает ограниченность числа .