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

Отбор ОММО

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

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

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

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

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

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

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

Задача 1#41295

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

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

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

Нужно минимизировать сумму $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$