Высшая проба 2024, 11 класс, задача 2
( баллов) В некотором числе единиц, двоек, троек, , девяток, расположенных в некотором порядке. Каждую секунду в нём стирают последнюю цифру. Правда ли, что в какой-то момент после начального получится число, делящееся на ?
Ответ
Да, правда.
Остаток от деления числа на равен остатку суммы цифр числа при делении на . Мысленно выкинем из числа все девятки, так как они не меняют остаток суммы цифр при делении на . В нашем числе есть восьмёрок, а остальных цифр . Разобьём наши цифр на блоков по десять цифр. Если в каждом блоке не более восьмёрок, то всего их не более чем , значит, найдётся блок из подряд идущих восьмёрок. Пусть после стирания первой из них (если идти справа налево) сумма оставшихся цифр равна . Тогда при последовательном стирании следующих восьми восьмёрок суммы оставшихся цифр равны . Эти девять чисел дают попарно различные остатки при делении на девять (разность любых двух различных из них не кратна , ибо числа не кратны ), потому среди них найдётся кратное девяти.
