2014 dxdy logo

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

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


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Какие монеты надо выпускать?
Сообщение25.03.2014, 01:05 
Аватара пользователя


01/12/11

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

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

 Профиль  
                  
 
 Re: Какие монеты надо выпускать?
Сообщение25.03.2014, 08:04 
Заслуженный участник


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

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


26/08/11
2057

(Оффтоп)

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

 Профиль  
                  
 
 Re: Какие монеты надо выпускать?
Сообщение25.03.2014, 09:06 
Заслуженный участник
Аватара пользователя


11/03/08
9490
Москва
Необходимость единицы - очевидна. Без двойки можно обойтись, 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 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Какие монеты надо выпускать?
Сообщение25.03.2014, 09:39 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Какие монеты надо выпускать?
Сообщение25.03.2014, 09:49 


14/01/11
2916
Компьютерным перебором получаем следующие решения:
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 
Аватара пользователя


01/12/11

8634
Cash в сообщении #840455 писал(а):
Бросается в глаза набор из идущих подряд нечетных чисел.

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

 Профиль  
                  
 
 Re: Какие монеты надо выпускать?
Сообщение25.03.2014, 10:20 
Заслуженный участник
Аватара пользователя


23/08/07
5420
Нов-ск
Ktina в сообщении #840504 писал(а):
Или я чего-то не понимаю?

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

 Профиль  
                  
 
 Re: Какие монеты надо выпускать?
Сообщение25.03.2014, 10:28 


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

 Профиль  
                  
 
 Re: Какие монеты надо выпускать?
Сообщение25.03.2014, 10:32 


26/08/11
2057
Cash все таки имел ввиду 1,3,5,7,9,10 :-)

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

 Профиль  
                  
 
 Re: Какие монеты надо выпускать?
Сообщение25.03.2014, 10:37 
Заслуженный участник
Аватара пользователя


23/08/07
5420
Нов-ск
Sender в сообщении #840510 писал(а):
А в 1, 2, 5, 8, 9, 10 чётные и нечётные строго чередуются.

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

 Профиль  
                  
 
 Re: Какие монеты надо выпускать?
Сообщение26.03.2014, 08:25 
Заслуженный участник


12/09/10
1547
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 


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

 Профиль  
                  
 
 Re: Какие монеты надо выпускать?
Сообщение26.03.2014, 16:33 


14/01/11
2916
Аналогично, можно получить верхние оценки для $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