Олимпиадная задача по теории чисел для 6–8 класса: можно ли собрать любую сумму рублей купюрами по 3 и 5?

Решение 1:   Если эта сумма кратна 3 (наименьшее возможное число 9), используем только 3-рублевые купюры. Если при делении на 3 она даёт остаток 1 (наименьшее возможное число 10), то берём две 5-рублевые купюры, остальное доплачиваем 3-рублевыми. Если же при делении на 3 сумма даёт остаток 2 (наименьшее возможное число 8), то берём одну 5-рублевую купюру, остальное доплачиваем 3-рублевыми.

Решение 2:   Докажем это по индукции.   База: сумму в 8 рублей выплатить можно.   Шаг индукции. Пусть сумму в n рублей можно выплатить 3- и 5-рублевыми купюрами. Если среди этих купюр есть хоть одна 5-рублевая, то заменив её на две 3-рублевые, мы получим  n + 1  рублей. Если же все купюры 3-рублевые, то их не меньше трёх, и, заменив три 3-рублевые купюры на две 5-рублевые, мы тоже получим  n + 1  рублей.