Есть 16 монет по 2 рубля и 29 монет по 5 рублей.
а) Можно ли этими монетами набрать сумму 175 рублей?
б) Можно ли этими монетами набрать сумму 176 рублей?
в) Какое наименьшее количество монет, каждая по 1 рублю, нужно добавить, чтобы иметь возможность набрать любую целую сумму от 1 рубля до 180 рублей включительно?
Задание с развёрнутым ответом. Запишите решение и сравните его с разбором.
Ответ: а) да; б) нет; в) 3 монеты.
Решение
Сначала найдём общую сумму денег. Двухрублёвые монеты дают:
$$16\cdot2=32\text{ рубля}.$$
Пятирублёвые дают:
$$29\cdot5=(30-1)\cdot5=150-5=145\text{ рублей}.$$
Всего:
$$T=32+145=177\text{ рублей}.$$
а) Чтобы получить 175 рублей, из всей суммы нужно убрать:
$$177-175=2\text{ рубля}.$$
Одна монета по 2 рубля у нас есть. Уберём её. Останутся 15 двухрублёвых и 29 пятирублёвых монет:
$$15\cdot2+29\cdot5=30+145=175.$$
Ответ — да.
б) Чтобы получить 176 рублей, из всей суммы пришлось бы убрать:
$$177-176=1\text{ рубль}.$$
Убрать никаких монет — значит убрать 0 рублей. Убрать хотя бы одну — значит убрать не меньше 2 рублей, поскольку самая дешёвая монета стоит 2. Сумму ровно 1 рубль убрать невозможно. Поэтому 176 рублей набрать нельзя.
в) Чтобы набрать 180 рублей, общая стоимость всех монет должна быть хотя бы 180. Изначально она равна 177. Поэтому добавить нужно не меньше:
$$180-177=3$$
рублёвых монет. Две такие монеты дали бы только 179 рублей даже при использовании всех денег.
Покажем, что трёх монет действительно хватает для каждой суммы от 1 до 180, а не только для самой большой.
Сначала три монеты по рублю позволяют набрать подряд суммы 0, 1, 2 и 3. Ноль здесь означает, что мы не берём ни одной монеты. Допустим, некоторым набором уже можно набрать все целые суммы от 0 до $M$. Добавим монету стоимости $v$. Без неё доступны суммы $0,\ldots,M$, а с ней — суммы $v,\ldots,M+v$. Если $v\le M+1$, между этими двумя списками нет пропуска. Следовательно, доступны все суммы от 0 до $M+v$.
Применим это к двухрублёвым монетам. Изначально $M=3$, а $v=2\le4=M+1$. Каждая такая монета увеличивает верхнюю границу на 2, не создавая пропусков. После всех 16 монет получаем:
$$M=3+16\cdot2=3+32=35.$$
Теперь добавляем пятирублёвые. Первая удовлетворяет $5\le35+1=36$. После её добавления граница станет 40; следующие тем более удовлетворяют тому же условию. Все 29 пятирублёвых монет увеличивают границу ещё на:
$$29\cdot5=145.$$
В результате доступны все суммы от 0 до:
$$35+145=180.$$
Значит, доступны и все требуемые суммы от 1 до 180. Три рублёвые монеты необходимы и достаточны.
Ответ: а) да; б) нет; в) 3 монеты.