Тема ОММО (Объединённая Межвузовская Математическая Олимпиада)
Отбор ОММО
Вспоминай формулы по каждой теме
Решай новые задачи каждый день
Вдумчиво разбирай решения
ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!
Подтемы раздела оммо (объединённая межвузовская математическая олимпиада)
Решаем задачи

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

Задача 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.

Ответ:

 82

Рулетка
Вы можете получить скидку в рулетке!