Question

Можно ли заплатить 25 рубл. 11 монет. достоинством (1,3,5) рубл?
Если да, то приведите все варианты

Answer 1

Пусть мы заплатили так, как требуется по условию.
Представим, что выбранные монеты пожертвовали рубль на благотворительность, а потом решили отдать туда же половину своего номинала. 
После первого процесса сумма уменьшилась на 11 и стала равна 14 рублям, а номиналы монет стали 0, 2 и 4 рубля, после второго - сумма стала в два раза меньше (7 рублей), а новые номиналы - 0, 1 и 2 рубля.

Итак, нужно найти все способы выдать 7 рублей 11 монетами по 0, 1 и 2 рубля. Понятно, что двухрублёвых монет должно быть не больше трёх - иначе сумма была бы больше 4 * 2 = 8 рублей, а на самом деле всего 7.

Перебираем варианты:
- нет двухрублевых монет. Надо выдать 7 рублей - это 7 монет по 1 рублю и 11 - 0 - 7 = 4 монеты по 0 рублей.
- одна двухрублевая монета. Осталось выдать 5 рублей - 5 монет по 1 рублю и 11 - 1 - 5 = 5 монет по 0 рублей.
- две монеты по 2 рубля. Осталось выдать 3 рубля - 3 монеты по 1 рублю, 11 - 2 - 3 = 6 монет по 0 рублей.
- три монеты по 2 рубля. Осталось выдать 1 рубль - 1 монета по 1 рублю, 11 - 3 - 1 = 7 монет по 0 рублей.

А теперь монеты одумались и забрали свои пожертвования обратно. Получились четыре способа заплатить 25 рублей:
- 0 по 5₽ + 7 по 3₽ + 4 по 1₽
- 1 по 5₽ + 5 по 3₽ + 5 по 1₽
- 2 по 5₽ + 3 по 3₽ + 6 по 1₽
- 3 по 5₽ + 1 по 3₽ + 7 по 1₽