ВсОШ 2022, 11 класс, задача 7

Решение.

Пусть число состоит из цифры. Считаем далее, что : меньшие числа не влияют на искомую ограниченность. Для обозначим через число, получающееся удалением из числа цифры с номером с конца. Обозначим через количество точных квадратов в множестве . Наша цель — доказать, что ограничено сверху.

Пусть , где не кратно . Если нечётно, то число может быть точным квадратом только при , так что в этом случае . Если чётно, то заключительные нулей не влияют на дело, поэтому . Поэтому далее считаем, что не кратно .

Выделим множество из номеров , для которых — точный квадрат, причём натуральные числа , , попарно различны. Отметим следующее: 1. , следовательно при всех ; 2. ; 3. кратно .

Из свойства следует, что для различных номеров из имеет место оценка

Сопоставляя это со свойством , получаем, что . Таким образом, все элементы , кроме, быть может, одного, больше, чем . Обозначим , тогда и .

Пусть — два элемента множества . Тогда по свойствам , имеем

С другой стороны, по свойству число кратно . Положим . Хотя бы одно из чисел , кратно , и хотя бы одно кратно . Кроме того, если нечётно, то нечётны числа , , поэтому одно из чисел , не кратно — а другое, соответственно, кратно . Иначе не кратно , и аналогичным образом получаем, что одно из чисел , кратно .

Рассмотрим пятиэлементное подмножество , наименьший элемент обозначим , а наибольший . Обозначим . Если нечётно, положим , ; иначе положим , . Из доказанного следует, что элементы множества дают не более двух различных остатков по модулю и не более двух различных остатков по модулю . Значит, в найдутся два различных элемента такие, что кратно . Тогда по получаем

откуда следует, что . Таким образом, если разбить отрезок на группы подряд идущих чисел, в каждой из которых отношение любых двух элементов меньше чем (количество таких групп меньше, например, миллиона), то любая из этих групп содержит не более элементов множества . Отсюда вытекает ограниченность числа .