Образцовое решение

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

1 цент, 1 цент, 1 цент, 1 цент, 5 центов, 10 центов, 10 центов, 25 центов, 50 центов.

Для проверки полученного ответа можно выбрать наугад несколько сумм и попробовать составить их с помощью наших девяти монет. Например, чтобы составить сумму 73 цента, нам потребуются монеты 50 центов, 10 центов, 10 центов и три по 1 центу.