Задача №15413

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

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

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

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

а) Представим сумму 175 рублей как $5x+2y\text{,}$ где $x$ — количество монет по 5 рублей, $y$ — по 2 рубля, $0⩽x⩽29\text{,}$ $0⩽y⩽16\text{.}$

Подбираем: при $x=29$ (нечётно

е) получаем $5\cdot 29=145\text{,}$ тогда $2y=175-145=30\text{,}$ откуда $y=15⩽16\text{.}$

Комбинация существует.

б) Для суммы 176 рублей: $5x+2y=176\text{,}$ $x$ должно быть чётным.

Максимальное чётное $x=28$ даёт $5\cdot 28=140\text{,}$ тогда $y=(176-140)/2=18>16\text{.}$

При уменьшении $x$ значение $y$ увеличивается, других целых решений в пределах ограничений нет.

Сумму 176 рублей набрать нельзя.

в) Пусть $A$ — множество сумм, набираемых монетами 2 и 5 рублей:

$A=\{2b+5c\mid 0⩽b⩽16,0⩽c⩽29\}\text{.}$

Максимальная сумма в $A$ равна $16\cdot 2+29\cdot 5=177\text{.}$

Проверка показывает, что все целые числа от 4 до 173 принадлежат $A\text{,}$ а числа 174 и 176 не принадлежат.

Таким образом, $A=\{0;2\}\cup \{4;5;\dots ;173\}\cup \{175;177\}\text{.}$

Чтобы с добавлением $k$ монет по 1 рублю можно было набрать любую сумму от 1 до 180, необходимо и достаточно, чтобы для каждого $S\in [1;180]$ существовало $t\in A$ такое, что $0⩽S-t⩽k\text{.}$

Это условие равносильно тому, что максимальный разрыв между последовательными элементами $A$ (и от 0 до первого, и от последнего до 180) не превышает $k\text{.}$

Разрывы: между 0 и 2 — число 1 (длина 1); между 2 и 4 — число 3 (длина 1); между 173 и 175 — число 174 (длина 1); между 175 и 177 — число 176 (длина 1); после 177 до 180 — числа 178, 179, 180 (длина 3).

Наибольшая длина разрыва равна 3, следовательно, минимальное $k=3\text{.}$

Ответ:

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

б) Нельзя набрать сумму 176 рублей.

в) 3.