Какие монеты надо выпускать?

[Cash]

Да, гипотезу Гольдбаха я и имел ввиду для оценки $c_{3,120}$
Взяв единицу и первые 17 простых чисел получим $c_{3,120} \leqslant 18$
Но ведь наверняка можно улучшить...

-- Ср мар 26, 2014 20:10:16 --

Например, немного поработав с исходным списком можно повыкидывать "лишние", получив набор из 12 чисел
$\{1,2,3,7,13,23,31,37,43,47,59,67\}$

-- Ср мар 26, 2014 20:24:08 --

А вот набор из 11 чисел
$\{1, 2, 3, 7, 14, 22, 33, 43, 53, 61, 69\}$

-- Ср мар 26, 2014 20:27:05 --

Наверное, можно и брутфорс организовать по поиску с 9-ю или 10-ю элементами.
Но уже сегодня руки не доходят.

[Cash]

Порывшись в интернете, нашел, что эта задача известна как "задача о почтовых марках".
http://mathworld.wolfram.com/PostageStampProblem.html
http://www2.stetson.edu/~efriedma/mathmagic/0403.html

Ну и напоследок, честно решил свою задачу.
Набор $\{1, 3, 8, 9, 14, 32, 36, 51, 53\}$ позволяет набрать тремя элементами любую сумму от $1$ до $120$ (и даже до $121$)
Интересно, что искомый набор для 9 элементов единственный. Следующий по "емкости" набор позволяет собрать суммы только до $117$, т.е. число $120$, взятое с потолка, оказалось весьма содержательным.