Есть 16 монеток по 2 рубля и 29 монеток по 5 рублей.
а) Можно ли взять несколько из них так, чтобы сумма взятых монет была равна 175?
б) Можно ли взять несколько из них так, чтобы сумма взятых монет была равна 176?
в) Какое наименьшее количество монеток по 1 рублю нужно добавить в набор, чтобы можно было получить любую целую сумму от 1 до 180 включительно?
Посмотреть решение
Предварительное решение, не проверено экспертом.
Ранее доступное решение переведено в общий параметрический рецепт; новая независимая проверка не проводилась.
Шаг 1. Количество монет каждого из двух номиналов ограничено данным запасом. Для всех пар количеств вычисляем сумму. Это все суммы, которые можно набрать; для заданной суммы достаточно найти хотя бы одну пару.
T=((15;29))
Шаг 2. Да. Приведённая конструкция удовлетворяет всем требованиям.
Шаг 1. Количество монет каждого из двух номиналов ограничено данным запасом. Для всех пар количеств вычисляем сумму. Это все суммы, которые можно набрать; для заданной суммы достаточно найти хотя бы одну пару.
T={}
Шаг 2. Нет. Необходимое и достаточное условие либо полная конечная область исключает такой случай.
Шаг 1. Количество монет каждого из двух номиналов ограничено данным запасом. Для всех пар количеств вычисляем сумму. Это все суммы, которые можно набрать; для заданной суммы достаточно найти хотя бы одну пару.
Шаг 2. Если добавлено c рублёвых монет, каждая исходно достижимая сумма v даёт все целые суммы от v до v+c. Проверяем покрытие требуемого отрезка этими промежутками. Достаточно 0≤c≤H, где H - правая граница отрезка: H рублёвых монет заведомо хватает. Первая подходящая величина c является минимумом.