По индукции. База: 8 = 5 + 3 можно. Переход. Пусть k рублей можно. Докажем, что и k + 1 можно. - Если k можно уплатить так, что среди купюр есть 5 рублей - убираем 5 рублей, добавляем 3 + 3 = 6 рублей. - Если k можно уплатить только трехрублевками, то трехрублевок не менее 3 (минимальная сумма не меньше 8, которую можно оплатить 3-рублевками, равна 9). Тогда меняем 3 + 3 + 3 = 9 на 5 + 5 = 10. Переход доказан.
Answers & Comments
Verified answer
По индукции.База: 8 = 5 + 3 можно.
Переход. Пусть k рублей можно. Докажем, что и k + 1 можно.
- Если k можно уплатить так, что среди купюр есть 5 рублей - убираем 5 рублей, добавляем 3 + 3 = 6 рублей.
- Если k можно уплатить только трехрублевками, то трехрублевок не менее 3 (минимальная сумма не меньше 8, которую можно оплатить 3-рублевками, равна 9). Тогда меняем 3 + 3 + 3 = 9 на 5 + 5 = 10.
Переход доказан.