Уравнение для количества монет: условия и конструкция

Выводим целочисленную модель, доказываем полноту области и получаем ответ с конструкцией достижимости.

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

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

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

  1. Целые числа и необходимые условия
  2. Граница и достижимость
  3. Уравнение для количества монет

    Сначала: Целые числа и необходимые условия, Граница и достижимость

  4. Ответ: да

    Сначала: Уравнение для количества монет

  5. Ответ: нет

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

  6. Все суммы после добавления единичных монет

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

  7. Ответ

    Сначала: Все суммы после добавления единичных монет

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

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

а) Можно ли этими монетами набрать сумму 175 рублей?

б) Можно ли этими монетами набрать сумму 176 рублей?

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

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

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

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

Шаг 1. Пусть xx и yy - количества монет достоинств aa и bb. Требуемая сумма TT набирается тогда и только тогда, когда ax+by=Tax+by=T при целых 0≤x≤m0\leq x\leq m, 0≤y≤n0\leq y\leq n. Для каждого yy от 0 до nn проверяем, делится ли T−byT-by на aa и лежит ли xx в своих границах. Это полный конечный список вариантов.
T=175T=175
пример=((15;29))\text{пример}=\left(\left(15;29\right)\right)
Шаг 2. Да. Приведённый вариант удовлетворяет доказанным условиям.
Шаг 1. Пусть xx и yy - количества монет достоинств aa и bb. Требуемая сумма TT набирается тогда и только тогда, когда ax+by=Tax+by=T при целых 0≤x≤m0\leq x\leq m, 0≤y≤n0\leq y\leq n. Для каждого yy от 0 до nn проверяем, делится ли T−byT-by на aa и лежит ли xx в своих границах. Это полный конечный список вариантов.
T=176T=176
count=0count=0
Шаг 2. Нет. Полный список допустимых вариантов пуст либо необходимое условие нарушено.
Шаг 1. Вычислим множество BB всех сумм ax+byax+by в доказанных границах и оставим суммы от 0 до требуемой верхней границы TT. Если добавлено kk монет по 1, каждая сумма vv из BB даёт все целые значения от vv до v+kv+k. Чтобы эти промежутки покрыли от 0 до TT, необходимо и достаточно k≥vnext−v−1k\geq v_{n}ext-v-1 для любых соседних сумм и k≥T−vmax⁡k\geq T-v_{\max}. Поэтому минимум kk - максимум этих разрывов и остатка в конце. Это одновременно нижняя граница и доказательство покрытия всех сумм.
Δmax⁡=1\Delta_{\max}=1
T−bmax⁡=3T-b_{\max}=3
Шаг 2. Записываем полученное значение.
33

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

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