У Пети есть монеты номиналом 1, 2, 5 и 10 рублей. Каждого вида монет у него по 100 штук. Цена пирожного в рублях выражается целым числом. Петя хочет купить пирожное без сдачи, но до покупки не знает сколько оно стоит.
а) Может ли Петя выбрать дома 16 монет так, чтобы купить пирожное стоимостью не более 100 рублей?
б) Может ли Петя выбрать дома 5 монет так, чтобы купить пирожное стоимостью не более 25 рублей?
в) Какое наименьшее количество монет нужно взять Пете, если известно, что пирожное стоит не более 100 рублей?
Посмотреть решение
Предварительное решение, не проверено экспертом.
Ранее доступное решение переведено в общий параметрический рецепт; новая независимая проверка не проводилась.
Шаг 1. Пусть уже выбранные монеты позволяют набрать все суммы от нуля до R. Следующая монета достоинства d сохраняет непрерывность ровно при d≤R+1; тогда покрываются все суммы до R+d. Если d>R+1, сумму R+1 уже нельзя получить ни этой, ни более крупными монетами. Последовательно применяем критерий по возрастанию номиналов.
Шаг 2. Для фиксированного количества монет перебираем все количества четырёх номиналов, не превышающие запас. Критерием непрерывности определяем наибольшую гарантированную цену. Увеличиваем общее количество, пока покрытие впервые не достигнет требуемой цены. Это доказывает минимальность; приводим количества монет и покрываемую сумму. Для заданного большего количества можно добавить лишние монеты, сохранив уже покрытые цены.
n=16
Шаг 3. Записываем точный список параметров или построенное распределение.
T=((1;2;1;12);130)
Шаг 4. Да. Построенный пример удовлетворяет всем условиям.
Шаг 1. Пусть уже выбранные монеты позволяют набрать все суммы от нуля до R. Следующая монета достоинства d сохраняет непрерывность ровно при d≤R+1; тогда покрываются все суммы до R+d. Если d>R+1, сумму R+1 уже нельзя получить ни этой, ни более крупными монетами. Последовательно применяем критерий по возрастанию номиналов.
Шаг 2. Для фиксированного количества монет перебираем все количества четырёх номиналов, не превышающие запас. Критерием непрерывности определяем наибольшую гарантированную цену. Увеличиваем общее количество, пока покрытие впервые не достигнет требуемой цены. Это доказывает минимальность; приводим количества монет и покрываемую сумму. Для заданного большего количества можно добавить лишние монеты, сохранив уже покрытые цены.
n=5
Шаг 3. Записываем точный список параметров или построенное распределение.
T=((1;2;1;1);20)
Шаг 4. Нет. Полученное необходимое ограничение исключает такую возможность.
Шаг 1. Пусть уже выбранные монеты позволяют набрать все суммы от нуля до R. Следующая монета достоинства d сохраняет непрерывность ровно при d≤R+1; тогда покрываются все суммы до R+d. Если d>R+1, сумму R+1 уже нельзя получить ни этой, ни более крупными монетами. Последовательно применяем критерий по возрастанию номиналов.
Шаг 2. Для фиксированного количества монет перебираем все количества четырёх номиналов, не превышающие запас. Критерием непрерывности определяем наибольшую гарантированную цену. Увеличиваем общее количество, пока покрытие впервые не достигнет требуемой цены. Это доказывает минимальность; приводим количества монет и покрываемую сумму. Для заданного большего количества можно добавить лишние монеты, сохранив уже покрытые цены.
Шаг 3. Записываем точный список параметров или построенное распределение.