2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу 1, 2  След.
 
 Какие монеты надо выпускать?
Сообщение25.03.2014, 01:05 
Аватара пользователя
В тридевятом царстве введена новая денежная единица тугрик. Монет-
ный двор хочет выпустить всего шесть видов монет так, чтобы любую
сумму от 1 до 20 тугриков можно было набрать одной или двумя моне-
тами. Какие монеты надо выпускать?

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

 
 
 
 Re: Какие монеты надо выпускать?
Сообщение25.03.2014, 08:04 
Бросается в глаза набор из идущих подряд нечетных чисел.

 
 
 
 Re: Какие монеты надо выпускать?
Сообщение25.03.2014, 08:41 

(Оффтоп)

Ktina в сообщении #840433 писал(а):
В тридевятом царстве введена новая денежная единица тугрик
Назовите имя государства.

 
 
 
 Re: Какие монеты надо выпускать?
Сообщение25.03.2014, 09:06 
Аватара пользователя
Необходимость единицы - очевидна. Без двойки можно обойтись, 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, отвечающий условию задачи. На вопрос, минимален ли он, я пока ответить не могу.

 
 
 
 Re: Какие монеты надо выпускать?
Сообщение25.03.2014, 09:17 
Аватара пользователя
Это как https://en.wikipedia.org/wiki/Sidon_sequence, только задача наоборот. Наверняка тоже имеет название.

 
 
 
 Re: Какие монеты надо выпускать?
Сообщение25.03.2014, 09:39 
Аватара пользователя
Да, только перебор на компе. Вручную начал - чувствую, варианты пропускаю...

 
 
 
 Re: Какие монеты надо выпускать?
Сообщение25.03.2014, 09:49 
Компьютерным перебором получаем следующие решения:
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.

 
 
 
 Re: Какие монеты надо выпускать?
Сообщение25.03.2014, 10:14 
Аватара пользователя
Cash в сообщении #840455 писал(а):
Бросается в глаза набор из идущих подряд нечетных чисел.

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

 
 
 
 Re: Какие монеты надо выпускать?
Сообщение25.03.2014, 10:20 
Аватара пользователя
Ktina в сообщении #840504 писал(а):
Или я чего-то не понимаю?

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

 
 
 
 Re: Какие монеты надо выпускать?
Сообщение25.03.2014, 10:28 
А в 1, 2, 5, 8, 9, 10 чётные и нечётные строго чередуются.

 
 
 
 Re: Какие монеты надо выпускать?
Сообщение25.03.2014, 10:32 
Cash все таки имел ввиду 1,3,5,7,9,10 :-)

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

 
 
 
 Re: Какие монеты надо выпускать?
Сообщение25.03.2014, 10:37 
Аватара пользователя
Sender в сообщении #840510 писал(а):
А в 1, 2, 5, 8, 9, 10 чётные и нечётные строго чередуются.

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

 
 
 
 Re: Какие монеты надо выпускать?
Сообщение26.03.2014, 08:25 
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}$
Гипотеза:
(удалил)

 
 
 
 Re: Какие монеты надо выпускать?
Сообщение26.03.2014, 10:59 
Если $m=4$, можно вспомнить, что каждое натуральное число представимо суммой 4-х квадратов, т.е. $c_{4,n}\leqslant \sqrt{n}.$

 
 
 
 Re: Какие монеты надо выпускать?
Сообщение26.03.2014, 16:33 
Аналогично, можно получить верхние оценки для $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$. :-)

 
 
 [ Сообщений: 17 ]  На страницу 1, 2  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group