Математикажан қалалық Жәутіков олимпиадасы, 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.

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