Задача 107860

Темы:    [ Признаки делимости на 3 и 9 ] [ Десятичная система счисления ] [ Признаки делимости (прочее) ] [ Полуинварианты ]

Сложность: 4 Классы: 8,9,10

Условие

Авторы: Канель-Белов А.Я., Анисов С.С.

Существует ли натуральное число, делящееся на 1998, сумма цифр которого меньше 27?

Решение

  Если число делится на 1998, то оно делится и на 999. Мы покажем, что не существует числа, делящегося на 999, сумма цифр которого меньше чем 27.
  Разобьем десятичную запись числа на группы по три цифры справа налево (последняя группа может состоять из одной или двух цифр). Сложим эти группы. Исходное число делится на 999 тогда и только тогда, когда полученная сумма делится на 999 (см. решение задачи 78550).
  Рассмотрим число, делящееся на 999, разобьём его на тройки цифр и вычислим сумму этих троек. Если новое число больше 1000, то снова разобьём его на тройки цифр и вычислим сумму, и так далее, пока не получим число, меньшее 1000. Это случится, поскольку число уменьшается при каждой операции. Действительно, если a₁, ..., a_k – неотрицательные целые числа, a_k ≠ 0  и  k ≥ 1,  то  a₀ + 1000a₁ + ... + 1000^ka_k > a₀ + a₁ + ... + a_k.
  Итак, после нескольких операций мы получим положительное число, меньшее 1000, делящееся на 999, следовательно, оно будет равно 999.
  Сумма цифр числа 999 равна 27. Достаточно доказать, что при наших операциях сумма цифр не увеличивается. Когда мы разрезаем число на тройки цифр, сумма цифр не меняется. Покажем, что при сложении сумма цифр не увеличивается. Действительно, обозначим через S(X) сумму цифр числа X. Из алгоритма сложения в столбик видно, что  S(X +Y) = S(X) + S(Y) – 9P(X, Y),  где  P(X, Y) — число переносов при сложении X и Y в столбик. Значит,
S(X + Y) ≤ S(X) + S(Y).

Источники и прецеденты использования

олимпиада
Название	Московская математическая олимпиада
год
Номер	61
Год	1998
вариант
Класс	10
задача
Номер	4