Монеты для любой цены

Последовательность применённых правил и переходов в пунктах задачи.

Учебный авторский материал. Порядок изучения не означает новую экспертную проверку решения или проверку источников.

Что разобрать сначала

Переходите по порядку или откройте то правило, которое вызвало затруднение. В конкретном решении используются только нужные для его условия ветви.

  1. Условие непрерывного покрытия цен
  2. Полный выбор количества монет

    Сначала: Условие непрерывного покрытия цен

  3. Вычисленные значения и пример

    Сначала: Полный выбор количества монет

  4. Ответ: да

    Сначала: Вычисленные значения и пример

  5. Условие непрерывного покрытия цен

    Сначала: Ответ: да

  6. Полный выбор количества монет

    Сначала: Условие непрерывного покрытия цен

  7. Вычисленные значения и пример

    Сначала: Полный выбор количества монет

  8. Ответ: нет

    Сначала: Вычисленные значения и пример

  9. Условие непрерывного покрытия цен

    Сначала: Ответ: нет

  10. Полный выбор количества монет

    Сначала: Условие непрерывного покрытия цен

  11. Вычисленные значения и пример

    Сначала: Полный выбор количества монет

  12. Ответ

    Сначала: Вычисленные значения и пример

Разобранный пример

У Пети есть монеты номиналом 1, 2, 5 и 10 рублей. Каждого вида монет у него по 100 штук. Цена пирожного в рублях выражается целым числом. Петя хочет купить пирожное без сдачи, но до покупки не знает сколько оно стоит.

а) Может ли Петя выбрать дома 16 монет так, чтобы купить пирожное стоимостью не более 100 рублей?

б) Может ли Петя выбрать дома 5 монет так, чтобы купить пирожное стоимостью не более 25 рублей?

в) Какое наименьшее количество монет нужно взять Пете, если известно, что пирожное стоит не более 100 рублей?

Посмотреть решение

Предварительное решение, не проверено экспертом.

Ранее доступное решение переведено в общий параметрический рецепт; новая независимая проверка не проводилась.

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

Открыть задачу целиком

Попробовать самостоятельно