Какие суммы не набираются монетами

Какую новую сумму можно получить из любой уже набранной, добавив одну монету достоинства 4?

Сколько соседних набираемых сумм достаточно найти, чтобы продолжать дальше шагами по 4 без пропусков?

1. Разбираем суммы до 9

Разделим числа до 9 на короткие группы.

• Суммы $1$, $2$, $3$ меньше самой маленькой монеты, поэтому невозможны.
• Суммы $4$, $6$, $7$ набираются одной монетой, сумма $8$ — парой $4+4$.
• Сумма $5$ невозможна: такой монеты нет, а две монеты дают уже не меньше $4+4=8$.

Остаётся сумма $9$. Проверим все возможности:

• с монетой $7$ остаётся $2$ — такую сумму не набрать;
• с монетой $6$ остаётся $3$ — её тоже не набрать;
• без монет $6$ и $7$ используются только четвёрки, но $9$ не делится на $4$.

Значит, среди этих чисел не набираются ровно $1$, $2$, $3$, $5$, $9$.

2. Находим участок без пропусков

Монета 4 позволяет продолжить любую набранную сумму шагами по 4. Поэтому ищем четыре соседних числа: они дадут начальную точку для каждого из четырёх возможных остатков при делении на 4.

Следующие четыре суммы набираются:

3. Доказываем, что новых пропусков не будет

Возьмём любое целое число $n\ge10$. Если оно больше $13$, будем вычитать по $4$, пока не получим число не больше $13$.

При последнем вычитании исходное число было хотя бы $14$, поэтому результат не меньше $14-4=10$. Значит, промежуток от 10 до 13 перескочить невозможно.

Итак,

$$n=s+4q,$$

где $s$ — одно из чисел $10$, $11$, $12$, $13$, а $q$ — целое неотрицательное число. Сумма $s$ уже набрана; добавим к ней $q$ монет по 4. Новых пропусков нет, а до 10 мы нашли ровно пять: $1$, $2$, $3$, $5$, $9$.

$5$

Четыре подряд идущие достижимые суммы закрывают все остатки при делении на $4$ и запускают бесконечное продолжение.

Если один разрешённый номинал равен $m$, попробуйте получить $m$ подряд идущих сумм; это может закончить проверку бесконечного множества.

Проверить только небольшой список чисел и объявить его полным, не объяснив, почему дальше невозможных сумм уже нет.

После конечного перебора ищите правило продолжения. В этой задаче его даёт прибавление одной монеты фиксированного достоинства.

Каждая из пяти исключённых сумм строго исключена, все остальные до 9 построены, для всех $n\ge10$ дано представление через четыре основания. Проверка до 500 — дополнительная сверка, не замена доказательству.