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

[Ktina]

В тридевятом царстве введена новая денежная единица тугрик. Монет-
ный двор хочет выпустить всего шесть видов монет так, чтобы любую
сумму от 1 до 20 тугриков можно было набрать одной или двумя моне-
тами. Какие монеты надо выпускать?

Чисто случайно мне в голову пришло решение "1, 3, 4, 9, 11 и 16". Вернее, не совсем уж и случайно, просто после нескольких неудачных попыток мне повезло. Правильный ответ - "1, 3, 5, 7, 9, 10".
Есть ли другие решения? Есть ли общий способ решения подобных задач?

[Cash]

Бросается в глаза набор из идущих подряд нечетных чисел.

[Shadow]

(Оффтоп)

Ktina в сообщении #840433 писал(а):

В тридевятом царстве введена новая денежная единица тугрик

Назовите имя государства.

[Евгений Машеров]

Необходимость единицы - очевидна. Без двойки можно обойтись, 1+1, но тогда необходима тройка (кроме того, очевидно, необходима хотя бы одна монета номиналом 10 или более). Если включаем тройку - имеем 3+1=4, но нужна пятёрка. Аналогично, получаем необходимость 7 и 9. Разные пары 1, 3, 5, 7, 9 дают 2, 4, 6, 8, 10, опять 8 и 10, 12, вновь 12, 14 , 16, 18. Недостаёт 11, 13, 15, 17, 19, 20. С учётом имеющихся - для их получения можно добавить десятку.
Таким образом, имеем набор из 6 монет 1, 3, 5, 7, 9, 10, отвечающий условию задачи. На вопрос, минимален ли он, я пока ответить не могу.

[ИСН]

Это как https://en.wikipedia.org/wiki/Sidon_sequence, только задача наоборот. Наверняка тоже имеет название.

[Евгений Машеров]

Да, только перебор на компе. Вручную начал - чувствую, варианты пропускаю...

[Sender]

Компьютерным перебором получаем следующие решения:
1, 2, 5, 8, 9, 10;
1, 3, 4, 8, 9, 11;
1, 3, 4, 9, 11, 16;
1, 3, 5, 6, 13, 14;
1, 3, 5, 7, 9, 10.

[Ktina]

Cash в сообщении #840455 писал(а):

Бросается в глаза набор из идущих подряд нечетных чисел.

Тогда их должно быть не шесть, а не менее десяти. Ведь десять нечётных сумм от 1 до 19 можно будет набрать лишь одной монетой, так как сумма любых двух будет чётной. Или я чего-то не понимаю?

[TOTAL]

Ktina в сообщении #840504 писал(а):

Или я чего-то не понимаю?

"1, 3, 4, 9, 11 и 16"
Здесь идут подряд две нечетных, потом подряд одна четная, потом подряд две нечетных, потом подряд одна четная. Т.е. тоже едет все подряд.

[Sender]

А в 1, 2, 5, 8, 9, 10 чётные и нечётные строго чередуются.

[Shadow]

Cash все таки имел ввиду 1,3,5,7,9,10

Пятью монетами можно набрать всех сумм до 16, причем единственным способом. 1,3,5,7,8
Можно сказать..универсальное решение

[TOTAL]

Sender в сообщении #840510 писал(а):

А в 1, 2, 5, 8, 9, 10 чётные и нечётные строго чередуются.

А в 1, 5, 9, 2, 8, 10 сначала идут нечетные, а потом четные.

[Cash]

Shadow, спасибо.
Я имел ввиду, что двумя монетами из $<1, 3, \ldots, 2n-1, 2n>$ (всего $n+1$) можно набрать любую сумму до $4n$ включительно

-- Ср мар 26, 2014 10:10:08 --

Интересно было бы обобщить эту задачу.
Пусть $c_{m,n}$ - наименьшая мощность множества, удовлетворяющего свойству, что для любого $k \leqslant n$ можно выбрать не более $m$ элементов, что их сумма равнялась $k$.
1. Найти $c_{3,120}$
2. Найти асимптотику $c_{m,n}$
Гипотеза:
(удалил)

[Sender]

Если $m=4$, можно вспомнить, что каждое натуральное число представимо суммой 4-х квадратов, т.е. $c_{4,n}\leqslant \sqrt{n}.$

[Sender]

Аналогично, можно получить верхние оценки для $c_{m,n}$ при $m>4$ из рассмотрения результатов решения проблемы Варинга. Например, $c_{9,n} \leqslant \sqrt[3]{n}$.
При $m=3$ можно посмотреть в сторону гипотезы Гольдбаха. Если вдруг она верна, то $c_{3,n} \leqslant \pi(n).$ Это позволяет существенно снизить верхнюю оценку для $c_{3,120}$ с $31$ до $30$.