Puzzle #31. Монеты

🎲 Существуют монеты следующего номинала:

1 копейка, 5 копеек, 10 копеек, 25 копеек, 50 копеек.

Определите, какое наименьшее количество монет необходимо, чтобы составить любую сумму от 1 копейки до 1 рубля ?!

Разбор: 

1. Очевидно, что нам нужны 4 однокопеечных монеты для получения сумм величиной до 4 копеек.
2. 2. Добавив одну пятикопеечную монету, мы можем получить любую сумму от 1 до 9 копейки. 
3. Добавление 10-копеечной монеты позволяет составить суммы величиной до 19 копеек. 
4. Еще одна 10-копеечная монета делает доступными суммы до 29 копеек. 
5. Одна 25-копеечная монета позволяет составить все суммы до 54 копеек. 
6. Наконец, одна 50-копеечная монета расширяет диапазон доступных сумм до 1 рубля. 

Итого нам нужны 9 монет следующих достоинств: 1 копейка, 1 копейка, 1 копейка, 1 копейка, 5 копеек, 10 копеек, 10 копеек, 25 копеек, 50 копеек.