Тип 19 № 20598

Решение

а) Да, возможно

Возьмём набор из 16 монет:

● одна монета номиналом 1 рубль;

● две монеты по 2 рубля;

● одна монета 5 рублей;

● двенадцать монет по 10 рублей.

Покажем, что с помощью этого набора можно составить любую целую сумму от 1 до 100 рублей.
Любое число $S \in [1; 100]$ представим в виде $$S = 10a + b, \quad 0 \le a \le 10,\; 0 \le b \le 9,$$ причём если $S = 100$, то берём все 10 десяток (хотя их 12). Для $S < 100$ используем $a$ монет по 10 рублей (где $a \le 9$). Остаток $b$ набираем монетами 1, 2, 2 и 5: они позволяют получить любое число от 0 до 9 (достаточно заметить, что $5, 2, 2, 1$ дают все остатки). Следовательно, набор из 16 монет подходит.

б) Нет, пяти монет недостаточно.

Предположим противное: выбрано 5 монет, позволяющих оплатить любую цену от 1 до 25 рублей.

Для того чтобы заплатить 3 рубля, необходимы как минимум две монеты (1 и 2). Для оплаты всех сумм от 1 до 4 рублей требуется не менее трёх монет (например, комбинации $1,1,2$ или $1,2,2$). Значит, среди пяти монет как минимум три заняты достоинствами 1 и 2.

Остаются две монеты. Рассмотрим два случая.

1. Если среди оставшихся двух монет нет двух десяток (то есть не более одной монеты 10 рублей), то максимальная сумма, которую можно набрать, не превосходит $$1 + 2 + 2 + 5 + 10 = 20$$ (или меньше, если нет пятёрки). Тогда нельзя оплатить 21 рубль — противоречие.

2. Если же обе оставшиеся монеты — десятки, то возможные наборы имеют вид либо $1,1,2,10,10$, либо $1,2,2,10,10$.
   В первом случае доступны суммы: без десяток — 1, 2, 3, 4; с одной десяткой — 11–14; с двумя — 21–24. Число 19 не получается.
   Во втором случае: без десяток — 1–5; с одной — 11–15; с двумя — 21–25. Число 19 также недостижимо.
   Значит, и в этом случае нельзя гарантировать оплату всех сумм до 25.

Следовательно, 5 монет недостаточно.

в) Минимальное количество монет — 13

Сначала докажем, что 12 монет не хватит.
Рассуждая аналогично пункту б), для оплаты всех сумм от 1 до 4 рублей необходимо минимум три монеты достоинством 1 или 2. Оставшиеся монеты (их не более 9) могут быть самого крупного номинала — 10 рублей, но если взять 10 десяток, то общее число монет станет 13, что больше 12. При 12 монетах максимум можно взять 9 десяток, две двойки и одну единицу, тогда общая максимальная сумма равна $$9 \cdot 10 + 2 + 2 + 1 = 95.$$ Значит, нельзя оплатить цены 96–100 рублей. Итак, 12 монет недостаточно.

Теперь покажем, что 13 монет достаточно. Возьмём набор: $$\underbrace{10, 10, \ldots, 10}_{9\text{ штук}},\; 5,\; 2,\; 2,\; 1.$$ Всего $9 + 1 + 2 + 1 = 13$ монет.

Для любой цены $S \le 100$ представим её в виде $S = 10a + b$, где $0 \le a \le 10$, $0 \le b \le 9$. Если $S = 100$, отдаём все 13 монет (сумма как раз 100). Если $S < 100$, то $a \le 9$ — берём $a$ монет по 10 рублей. Остаток $b$ набираем монетами $5, 2, 2, 1$:

● если $b \ge 5$, берём одну монету 5 рублей и добираем $b-5$ с помощью двух двоек и единицы (это возможно, так как эти три монеты дают все числа от 0 до 5);

● если $b < 5$, набираем его непосредственно из двоек и единицы. Таким образом, любая цена до 100 рублей будет оплачена без сдачи.

Следовательно, минимальное необходимое число монет равно 13.

Ответ:

а) да, может;

б) нет, не может;

в) 13 монет.