ВсОШ 2022, 9 и 10 классы, задача 10
Докажите, что существует натуральное число такое, что при любом натуральном сумма цифр числа не меньше .
(Д. Храмцов)
Ответ
Решение. Положим . Через обозначим сумму цифр числа . Отметим простое свойство , которое сразу видно, если числа и сложить в столбик.
Лемма. Пусть — натуральное число, и пусть натуральное число кратно . Тогда .
Доказательство. Индукция по . База очевидна.
Предположим, что , и что утверждение доказано для всех чисел, меньших . Докажем его и для . Пусть последние цифр числа образуют число (возможно, с ведущими нулями), а все остальные — число (иначе говоря, ). Поскольку делится на , то и (положительное) число также кратно . Поэтому по предположению индукции, а тогда и .
Для решения задачи осталось взять такое , что , и заметить, что если и , то делится на и, значит, .
Замечание. В доказательстве леммы по сути использован следующий признак делимости на . Разобьём десятичную запись числа на блоки по цифр (первый блок может быть неполон). Воспринимая эти блоки как обычные числа (возможно, с ведущими нулями), сложим их, получив число . Тогда кратно тогда и только тогда, когда делится на .
У леммы есть несколько вариаций; например, любое число, делящееся на число , имеет сумму цифр, не меньшую .
Сформулирована лемма (или аналогичный верный факт), утверждение задачи сведено к этому факту, но сам факт не доказан.
Использован без доказательства признак делимости, сформулированный выше; баллы не снимаются.