Городская Жаутыковская олимпиада по математике, 7 класс, 2019 год

Натуральное число называется замечательным, если оно представимо в виде произведения двух натуральных чисел с одинаковыми суммами цифр. Например, число 2020 замечательное, так как $2020=2 \cdot 1010.$ Докажите, что среди первых 2019 натуральных чисел, количество замечательных не более 888. ( Ибатулин И. )

Комментарий/решение

Пусть n - замечательное число, которое раскладывается на два множителя с суммами цифр s. Тогда, так как, они сравнимы с s по mod 9, то $n \equiv s^2 \pmod 9$. При этом несложно проверить, что любой квадрат дает остаток 0,1, 4, либо 7 при делении на 9. Следовательно для того чтобы число было замечательным, необходимо, чтобы оно было сравнимо с 0,1, 4, либо 7 по mod 9.

Рассмотрим 9 последовательных чисел: их остатки по mod 9 различны, при этом 4 из них являются остатками квадратов. Таким образом среди 9 последовательных чисел не более 4 являются замечательными. Откуда получаем, что среди первых 2019 чисел их не более чем $([\frac{2019}{9}]+1)*4=900$.

Если найдется 12 натуральных чисел, среди 2019 первых, таких, что они сравнимы с 0, 1, 4, или 7 по mod 9, при этом они не замечательные, то их можно будет исключить, и тем самым получится не более 888 чисел. Примеры: 7, 13, 18, 19, 27, 28, 31, 34, 37, 43, 45, 46.

Что требовалось доказать.