Задача М662‍‍

Достаточно доказать, что можно заплатить без сдачи один рубль.

В копилке могут находиться монеты четырёх видов: однокопеечные, двухкопеечные, трёхкопеечные и пятаки. Поэтому монет какого‑то вида не меньше рубля.

Если это — пятаки, двухкопеечные или однокопеечные, то ясно, что можно заплатить рубль без сдачи.

Рассмотрим поэтому случай, когда больше, чем на рубль, трёхкопеечных монет, а монет каждого другого вида меньше, чем на рубль.

Если в копилке есть хотя бы одна однокопеечная монета, то, добавляя её к 33 трёхкопеечным, получаем рубль.

Если есть две двухкопеечные или два пятака, то, добавляя к 32 (соответственно к 30) трёхкопеечным, получаем рубль.

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

Если пятаков нет, то двухкопеечных монет не меньше двух (398 не делится на 3); если двухкопеечных нет, то пятаков не меньше двух (395 не делится на 3). Итак, в рассматриваемом случае есть один пятак и одна двухкопеечная, и мы можем набрать рубль, добавив один пятак и одну двухкопеечную к 31 трёхкопеечной монете.

Интересно разобраться, какие вообще суммы могут быть уплачены без сдачи при четырёхрублёвом наборе медных монет в копилке.

Например, если в копилке только двухкопеечные монеты, то не может быть уплачена никакая нечётная сумма; если только пятаки, то — никакая сумма, не делящаяся на 5; если, наконец, в копилке 133 трёхкопеечных и одна однокопеечная, то не может быть уплачена никакая сумма, которая при делении на 3 даёт в остатке 2.

Значит, если некоторая сумма может быть уплачена при любом четырёхрублёвом наборе медных монет в копилке, то она делится на 10 и при делении на 3 не даёт в остатке 2. Все ли такие суммы могут быть уплачены?