Тема ОММО (Объединённая Межвузовская Математическая Олимпиада)

Отбор ОММО

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела оммо (объединённая межвузовская математическая олимпиада)

Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 1#41295

Скуперфильд хочет выплатить наложенный на него штраф в $1000$ фертингов монетами в $7$ и $13$ фертингов. Каким наименьшим количеством монет он может обойтись?

Источники: ОММО-2014, отборочный тур

Подсказки к задаче

Подсказка 1

Если монет в 7 фертингов - x штук, а в 13 - y штук, то выходит что 7x+13y=1000. Нам нужно минимизировать сумму x+y. Попробуйте в явном виде выразить её из равенства и понять, как сделать её максимальной!

Подсказка 2

Да, чтобы сумма была минимальной, нужно минимизировать y, но при этом сумма должна быть натуральной. Значит, 1000-6y делится на 7. Какой тогда остаток по модулю 7 должен иметь y? Какие ещё есть ограничения на y?

Подсказка 3

В силу того, что 1000-6y делится на 7, y имеет остаток 1 при делении на 7. Однако в силу того, что 7x=1000-13y>=0, y<=76. Осталось только найти число, которое удовлетворяло бы всем условиям.

Показать ответ и решение

Нужно минимизировать сумму $x+ y$ при условии, что $7x +13y = 1000$ и $x,y ∈ ℕ∪ {0}.$ Имеем $x +y = 1000−6y, 7$ так что для минимизации суммы нужно выбрать $y$ как можно больше, но так, чтобы $1000−6y y−-1 7 =143− y+ 7 ∈ℕ.$ Заключаем, что $y− 1$ должно делиться на $7.$ При этом из уравнения $7x = 1000− 13y ≥0,$ так что $y ≤76.$ Ближайшее снизу к $76$ число, которое даёт остаток $1$ по модулю $7$ это $71.$ Соответственно оптимальными значениями будут $1000−13⋅71- y =71,x= 7 =11.$ Всего монет $x +y = 11+ 71= 82.$