Puzzle #131. Монетный двор

Разбор

Можно подобрать монеты следующего достоинства: 1, 3, 5, 7, 9, 10 рублей. Всего 6 монет. 

Давайте попробуем подобрать всего 5 типов монет. Но имея пять типов монет, мы сможем уплатить не более 20 денежных сумм: 

- 5, беря по одной монете; 

- 5, беря по две одинаковые монеты; 

- и еще не более 10, беря по две различные монеты. 

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

Получаем, что обязательно должна быть монета достоинством в 1 рубль. 

Тогда двухрублевой монеты нет (иначе сумму в 2 рубля можно было бы уплатить двумя способами), а трехрублевая обязательно есть, четырехрублевой нет (4 = 3 + 1), а пятирублевая есть. 

Но тогда получается, что сумму в 6 рублей можно составить двумя способами: 

6 = 5 + 1 = 3 + 3. Значит, сделать 20 сумм различными не удастся.

Остается вариант с 6ю типами монет.