Два номинала и недостающие суммы

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

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

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

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

  1. Полная область сумм
  2. Ответ: да

    Сначала: Полная область сумм

  3. Полная область сумм

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

  4. Ответ: нет

    Сначала: Полная область сумм

  5. Полная область сумм

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

  6. Добавление рублёвых монет

    Сначала: Полная область сумм

  7. Ответ

    Сначала: Добавление рублёвых монет

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

Есть 16 монеток по 2 рубля и 29 монеток по 5 рублей.

а) Можно ли взять несколько из них так, чтобы сумма взятых монет была равна 175?

б) Можно ли взять несколько из них так, чтобы сумма взятых монет была равна 176?

в) Какое наименьшее количество монеток по 1 рублю нужно добавить в набор, чтобы можно было получить любую целую сумму от 1 до 180 включительно?

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

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

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

Шаг 1. Количество монет каждого из двух номиналов ограничено данным запасом. Для всех пар количеств вычисляем сумму. Это все суммы, которые можно набрать; для заданной суммы достаточно найти хотя бы одну пару.
T=((15;29))\mathcal T=\left(\left(15;29\right)\right)
Шаг 2. Да. Приведённая конструкция удовлетворяет всем требованиям.
Шаг 1. Количество монет каждого из двух номиналов ограничено данным запасом. Для всех пар количеств вычисляем сумму. Это все суммы, которые можно набрать; для заданной суммы достаточно найти хотя бы одну пару.
T={}\mathcal T=\left\{\right\}
Шаг 2. Нет. Необходимое и достаточное условие либо полная конечная область исключает такой случай.
Шаг 1. Количество монет каждого из двух номиналов ограничено данным запасом. Для всех пар количеств вычисляем сумму. Это все суммы, которые можно набрать; для заданной суммы достаточно найти хотя бы одну пару.
Шаг 2. Если добавлено cc рублёвых монет, каждая исходно достижимая сумма vv даёт все целые суммы от vv до v+cv+c. Проверяем покрытие требуемого отрезка этими промежутками. Достаточно 0≤c≤H0\leq c\leq H, где HH - правая граница отрезка: HH рублёвых монет заведомо хватает. Первая подходящая величина cc является минимумом.
T=((0;1);(1;179);(2;180);(3;0))\mathcal T=\left(\left(0;1\right);\left(1;179\right);\left(2;180\right);\left(3;0\right)\right)
Шаг 3. Записываем найденное значение.
33

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

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