СПбГУ 2021, 10-11 классы, задача 5
( баллов) В стране Лимонии в обращении используются монеты достоинством , , и пиастров, где — натуральное число. Житель страны зашел в банк, не имея при себе наличных денег. Какую наибольшую сумму ему не смогут выдать в банке?
Ответ: .
Решение. Назовем натуральное число разложимым, если сумму банк может выплатить монетами достоинством только , и пиастров. Для любого обозначим через наименьшее разложимое число, дающее при делении на остаток . Докажем два утверждения.
) Если , , то при сумму банк выплатить сможет, а при — не сможет. Первое утверждение очевидно: надо вначале выплатить сумму , а затем добавить некоторое количество монет по пиастров. Предположим теперь, что и сумму выплатить можно. При этом придется использовать несколько монет по пиастров. Убрав все эти монеты, мы получим разложимую сумму, меньшую и тоже дающую остаток при делении на . Это противоречит минимальности .
) Числа пробегают значения при . Действительно, нам достаточно показать, что все они различны. Если кратно , то . Так как , мы получаем .
Очевидно, что суммы, кратные , выплатить можно. Тогда в силу ) ответом задачи будет
Найдем наибольшее из чисел . Пусть . Заметим, что
В силу ) существует единственное число , для которого . Поскольку остатки монет по модулю принимают значения , и , нам надо представить в виде суммы минимального количества этих чисел. Она реализуется так: складываем шестерки, пока не получится самое большое число, не превосходящее , а затем при необходимости добавляем или . В этой сумме будет слагаемых. Тогда
причем равенство реализуется при . Значит, ответом в задаче будет