У замечательного популяризатора математики Мартина Гарднера в его книге «Математические досуги» (М., 1972) есть такая задача:
Чтобы набрать сумму в 99 центов, потребуется по крайней мере восемь американских монет: в половину и четверть доллара, две десятицентовых и четыре одноцентовика. Представьте, что вы президент новой независимой страны и должны утвердить монетную систему с наименьшей монетой в 1 цент. Задача состоит в том, чтобы любую сумму от 1 до 100 центов можно было отсчитать не более чем двумя монетами, а число различных монет в денежной системе оказалось бы при этом минимальным.
Гарнднер со ссылкой на книгу Sprague. Unterhaltsame Mathematik, Braunschweig, 1961 приводит такой ответ:
Для представления одной или двумя монетами сумм от 1 до 100 центов достаточно двух наборов по 16 монет с номиналами 1, 3, 4, 9, 11, 16, 20, 25, 30, 34, 39, 41, 46, 47, 49, 50 центов. Не доказано, что задачу нельзя решить меньшим числом монет.
Наша задача — вооружившись мощью вычислительной техники написать программу, которая найдёт все решения этой задачи.
Я задумался над алгоритмом решения давным-давно и в конце октября 2002 года написал соответствующую программу на языке C. Сначала был запущен вариант, в котором можно было брать не две, а три монеты, программа работала 6,5 часов. Для двух монет окончания работы программы я не дождался (перебор вариантов шёл слишком медленно) и остановил её после 11 часов работы. Алгоритм был оптимизирован, и теперь программа перебирала варианты в 30 раз быстрее. Всё равно медленно. Для третьего варианта я переписал основную часть кода на ассемблере, но это помогло мало.
Я запускал программу несколько вечеров подряд. После 90 часов работы была, наконец, найдена первая комбинация, которая совпадала с приведенной в книге. Ещё через 2,5 часа — вторая. После этого новые варианты перестали появляться, мне это надоело, и я остановил проект. Компьютер у меня тогда был с процессором Celeron (400 MHz).
Теперь, в 2016 году я вернулся к этой задаче, так как отсутствие полного ответа похоже на постоянно напоминающую о себе колючку. Программа была переписана на языке Java, за основу взят последний вариант алгоритма.
Старые два варианта теперь были обнаружены примерно за 1 час. Когда же программа проработала 6 часов с небольшим, ответ был получен целиком.
Итак, меньшим количеством монет задачу решить нельзя. А всего имеется 7 вариантов решения задачи:
1, 3, 4, 9, 11, 16, 20, 25, 30, 34, 39, 41, 46, 47, 49, 50
1, 3, 4, 7, 8, 9, 16, 17, 21, 24, 35, 46, 57, 68, 79, 90
1, 3, 4, 5, 8, 14, 20, 26, 32, 38, 44, 47, 48, 49, 51, 52
1, 3, 4, 5, 8, 14, 20, 26, 32, 38, 44, 46, 48, 49, 51, 53
1, 3, 4, 5, 8, 14, 20, 26, 32, 38, 44, 46, 47, 48, 49, 51
1, 3, 4, 5, 8, 14, 20, 26, 32, 38, 44, 45, 47, 48, 49, 52
1, 2, 3, 7, 11, 15, 19, 23, 27, 28, 29, 30, 61, 64, 67, 70
Когда писал этот текст, решил поискать в Интернете, не пытался ли кто ещё решить эту задачу. В 2015 году на одном англоязычном математическом форуме приводится решение задачи (которое я не понял) и все семь комбинаций. Я немного опоздал.
Задача: Написать программу, которая за адекватное время решит задачу методом полного перебора.
Декабрь 2016 г.