ID: 00009002
Есть $16$ монет по $2$, $\text{рубля}$ и $29$ монет по $5$, $\text{рублей}$.
а) Можно ли этими монетами набрать сумму $175$, $\text{рублей}$?
б) Можно ли этими монетами набрать сумму $176$, $\text{рублей}$?
в) Какое наименьшее количество монет, каждая по $1$, $\text{рублю}$, нужно добавить, чтобы иметь возможность набрать любую целую сумму от $1$, $\text{рубля}$ до $180$, $\text{рублей}$ включительно?
Источник: ФИПИ
Что дано: $16$ монет по $2$ рубля и $29$ монет по $5$ рублей. Любая набираемая сумма имеет вид $2x+5y$, где $0\leqslant x\leqslant 16$ (двушки) и $0\leqslant y\leqslant 29$ (пятёрки).
Пункт а). Набрать $175$? Возьмём все $29$ пятёрок ($145$ рублей) и $15$ двушек ($30$ рублей): $145+30=175$. Значит — да.
Пункт б). Набрать $176$? Нужно $2x+5y=176$. Чтобы $5y=176-2x$ делилось на $5$, нужно $2x\equiv 176\equiv 1\pmod 5$, откуда $x\equiv 3\pmod 5$, то есть $x\in\{3,8,13\}$ (в пределах $0..16$). Считаем $y=\dfrac{176-2x}{5}$: при $x=3,8,13$ получаем $y=34,32,30$ — все больше $29$. Значит подходящего набора нет, сумму $176$ собрать нельзя.
Пункт в). Сколько рублёвых монет добавить, чтобы набирать любую сумму от $1$ до $180$? Без единиц самая большая сумма — $2\cdot 16+5\cdot 29=32+145=177$. Чтобы дотянуть до $180$, не хватает $180-177=3$ рублей, поэтому рублёвых монет нужно хотя бы $3$.
Трёх единиц хватает. Недостающие маленькие суммы $1$ и $3$ теперь набираются прямо рублёвыми монетами. А любую другую сумму до $180$ получаем так: основную часть — двушками и пятёрками (они дают все суммы $\geqslant 4$ нужного вида), а «хвостик» $1$, $2$ или $3$ добавляем единицами. Поэтому покрываются все суммы от $1$ до $180$. Наименьшее число рублёвых монет — 3.
а) да; б) нет; в) $3$.