Методичка Зайцева 1 Н. А. Зайцев УНИВЕРС

Методичка Зайцева 1
Н. А. Зайцев
УНИВЕРСАЛЬНАЯ МОНЕТНАЯ СИСТЕМА (УМС)

У Мартина Гарднера в «Математических досугах» (М., 1972) есть такая задача:
Для того чтобы набрать сумму в 99 центов, потребуется по крайней мере восемь американских монет: в половину и четверть доллара, две десятицентовых и четыре монеты по одному центу. Представьте себе, что какая-нибудь новая независимая нация избрала вас своим президентом. Вы должны утвердить монетную систему, в которой наименьшей монетой является один цент. Задача состоит в том, чтобы любую сумму от одного до ста центов можно было отсчитать не более чем двумя монетами и чтобы при этом число различных монет в денежной системе оказалось минимальным.
Это требование выполняется, например, в том случае, если вы отчеканите 18 монет достоинством 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 20, 30, 40, 50, 60, 70, 80, 90 центов. Попробуйте теперь подобрать такие монеты, чтобы это число уменьшилось. Любая сумма должна быть образована либо одной монетой, либо двумя. В последнем случае обе монеты могут, конечно, иметь как разные, так и одинаковые достоинства.
Ответ: Двух наборов из шестнадцати монет разного достоинства вполне достаточно для того, чтобы любую сумму от 1 до 100 центов представить не более, чем двумя монетами. Отчеканить надо монеты достоинством 1, 3, 4, 9, 11, 16, 20, 25, 30, 34, 39, 41, 46, 47, 49, 50 центов. Не доказано, что задачу нельзя решить с меньшим числом монет.