а) Можно ли этими монетами набрать сумму 175 рублей?
б) Можно ли этими монетами набрать сумму 176 рублей?
в) Какое наименьшее количество монет, каждая по 1 рублю, нужно добавить, чтобы иметь возможность набрать любую целую сумму от 1 рубля до 180 рублей включительно?
Посмотреть решение
Предварительное решение, не проверено экспертом.
Ранее доступное решение переведено в общий параметрический рецепт; новая независимая проверка не проводилась.
Шаг 1. Пусть x и y - количества монет достоинств a и b. Требуемая сумма T набирается тогда и только тогда, когда ax+by=T при целых 0≤x≤m, 0≤y≤n. Для каждого y от 0 до n проверяем, делится ли T−by на a и лежит ли x в своих границах. Это полный конечный список вариантов.
T=175
пример=((15;29))
Шаг 2. Да. Приведённый вариант удовлетворяет доказанным условиям.
Шаг 1. Пусть x и y - количества монет достоинств a и b. Требуемая сумма T набирается тогда и только тогда, когда ax+by=T при целых 0≤x≤m, 0≤y≤n. Для каждого y от 0 до n проверяем, делится ли T−by на a и лежит ли x в своих границах. Это полный конечный список вариантов.
T=176
count=0
Шаг 2. Нет. Полный список допустимых вариантов пуст либо необходимое условие нарушено.
Шаг 1. Вычислим множество B всех сумм ax+by в доказанных границах и оставим суммы от 0 до требуемой верхней границы T. Если добавлено k монет по 1, каждая сумма v из B даёт все целые значения от v до v+k. Чтобы эти промежутки покрыли от 0 до T, необходимо и достаточно k≥vnext−v−1 для любых соседних сумм и k≥T−vmax. Поэтому минимум k - максимум этих разрывов и остатка в конце. Это одновременно нижняя граница и доказательство покрытия всех сумм.