Высшая проба 2021, 10 класс, задача 5
( баллов) Сережа задумал натуральное число , не превосходящее . Сначала он делит его с остатком на , получая неполное частное и остаток . Затем, на -ом шаге () он делит с остатком число на , получая неполное частное и остаток . Докажите, что
Решение
Сначала проверим по индукции, что для всех . Неравенство следует из того, что . Пусть для некоторого . Так как , то . Из этого следует, что . Переход индукции доказан.
Таким образом, условие можно переписать в виде
Искомое равенство
равносильно тому, что для любого выполнены неравенства
Умножив систему неравенств на , получим
Преобразуем среднюю часть системы следующим образом:
где последнее равенство следует из .
Лемма . Для любого выполняется равенство
Доказательство.
где последнее равенство следует из , если положить .
Применим Лемму последовательно раз (для ) к правой части равенства . Получим цепочку равенств
Таким образом, равносильно неравенствам
которые следуют из того, что и $q_k\le9
A0 Не доказано, что: +...
A1 Ошибки в строгости неравенств: +..+.
A2 Решение через деление в столбик, и при этом ничего не написано про случай, когда в некоторый момент в частном получается 2019 (или разобран только случай, при котором, и не доказано, что иначе 2019 не может появиться ни на каком шаге): +/—. A3Решениечерезделениевстолбик.Доказано,чтоеслиnнеравно2019,тоостатокнеможетбытьравен 2019 ни на каком шаге. При этом случайне разобран.
A4 Разность (/2019 − 0,...) выражена черези, далее из этого без доказательства 1 2 3делается вывод об искомом равенстве (оценка вышеуказанной разности отсутствует): +/—.+: +/—.+: +..+.