Высшая проба 2021, 9 класс, задача 5
( баллов) Сережа задумал натуральное число , не превосходящее . Сначала он делит его с остатком на , получая неполное частное и остаток . Затем, на -ом шаге () он делит с остатком число на , получая неполное частное и остаток . Докажите, что
Ответ
Решение
Сначала проверим по индукции, что для всех . Неравенство следует из того, что . Пусть для некоторого . Так как , то . Из этого следует, что . Переход индукции доказан.
Таким образом, условие можно переписать в виде
Искомое равенство
равносильно тому, что для любого выполнены неравенства
Умножив систему неравенств на , получим
Преобразуем среднюю часть системы следующим образом:
где последнее равенство следует из .
Лемма . Для любого выполняется равенство
Доказательство.
где последнее равенство следует из , если положить .
Применим Лемму последовательно раз (для ) к правой части равенства . Получим цепочку равенств
Таким образом, равносильно неравенствам
которые следуют из того, что и $q_k\le9