2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1 ... 3, 4, 5, 6, 7, 8, 9 ... 11  След.
 
 Re: Al Zimmermann - Sums and Products
Сообщение25.11.2015, 10:50 
Аватара пользователя


21/02/10
1594
Екатеринбург
whitefox

Да. Ваш вариант постановки простой и понятный. Качаю одну идею. Подобные идеи мелькают и в дискуссионной группе форума.

Будем строить решение так.
Берем последовательность чисел [1,2,...,x] и добавляем к ней числа из $\forall a\in A(x<a\leqslant\frac{x^2}2)$, и с наименьшим $|A^2|$.

 Профиль  
                  
 
 Re: Al Zimmermann - Sums and Products
Сообщение25.11.2015, 20:38 
Аватара пользователя


21/02/10
1594
Екатеринбург
61 24.5691 Valery Pavlovsky Ekaterinburg, Russia 25 Nov 2015 20:35

24.5 обещанные Herbert Kociemba 0,98*25. Остальные 0,0691 это результат моих интеллектуальных усилий. :D

dimkadimon 5 дней прошло. Где ваши 25 баллов?

 Профиль  
                  
 
 Re: Al Zimmermann - Sums and Products
Сообщение26.11.2015, 07:00 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
Pavlovsky в сообщении #1076711 писал(а):
dimkadimon 5 дней прошло. Где ваши 25 баллов?


Специально для вас нашел последнее решение :)

 Профиль  
                  
 
 Re: Al Zimmermann - Sums and Products
Сообщение26.11.2015, 07:36 
Аватара пользователя


21/02/10
1594
Екатеринбург
dimkadimon в сообщении #1076925 писал(а):
Специально для вас нашел последнее решение


Царский подарок. Спасибо.

 Профиль  
                  
 
 Re: Al Zimmermann - Sums and Products
Сообщение26.11.2015, 08:35 
Заслуженный участник
Аватара пользователя


19/12/10
1546
dimkadimon
Топ-10 тоже неплохо. :D
Мои поздравления. :appl:

 Профиль  
                  
 
 Re: Al Zimmermann - Sums and Products
Сообщение26.11.2015, 08:41 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
whitefox в сообщении #1076933 писал(а):
dimkadimon
Топ-10 тоже неплохо. :D
Мои поздравления. :appl:

Большое спасибо, я доволен! Теперь наступает самое интересное, если кто нибудь из топ-6 найдет новое решение то он станет первым. Хотя это мало вероятно.

 Профиль  
                  
 
 Re: Al Zimmermann - Sums and Products
Сообщение26.11.2015, 09:57 
Аватара пользователя


21/02/10
1594
Екатеринбург
6 человек независимо друг от друга получили одинаковые результаты. Для математика это ничего не значит. А с точки зрения экспериментатора это 100% гарантии оптимальности.

 Профиль  
                  
 
 Re: Al Zimmermann - Sums and Products
Сообщение26.11.2015, 13:37 
Заслуженный участник
Аватара пользователя


19/12/10
1546
А нельзя ли, исходя из структуры решений, доказать их оптимальность?

 Профиль  
                  
 
 Re: Al Zimmermann - Sums and Products
Сообщение26.11.2015, 14:10 
Аватара пользователя


21/02/10
1594
Екатеринбург
whitefox в сообщении #1076984 писал(а):
исходя из структуры решений, доказать их оптимальность?


Искать програмно улучшения текущих результатов бессмысленно. Конкурс программистов закончился. Много ли желающих будет участвовать в конкурсе математиков?!

-- Чт ноя 26, 2015 17:06:49 --

Pavlovsky в сообщении #1076508 писал(а):
Будем строить решение так.
Берем последовательность чисел [1,2,...,x] и добавляем к ней числа из $\forall a\in A(x<a\leqslant\frac{x^2}2)$, и с наименьшим $|A^2|$.


Забавно получается алгоритм Herbert Kociemba

 Профиль  
                  
 
 Re: Al Zimmermann - Sums and Products
Сообщение26.11.2015, 15:16 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
Pavlovsky в сообщении #1076988 писал(а):
Искать програмно улучшения текущих результатов бессмысленно. Конкурс программистов закончился. Много ли желающих будет участвовать в конкурсе математиков?!

Я думаю многим будет интересно улучшить математическую теорию этой задачи, но это уже будет не конкурс, а общая работа.

Гипотеза: Максимальную версию этой задачи можно решить оптимально. То есть для любого $N$ можно найти решение где все суммы и умножения различны. Такое решение будет иметь $N(N+1)$ очков.

Гипотеза работает для $N\leq 50$:

$N=10$
110: 68,189,231,285,621,630,757,777,788,908

$N=20$
420: 11,30,54,58,76,84,121,172,192,201,208,250,284,410,435,441,479,491,494,496

$N=30$
930: 26,75,77,146,214,228,281,399,463,567,582,586,744,818,1174,1257,1283,1367,1424,1433,1597,1657,1667,1670,1742,1836,1886,1934,1941,1964

$N=40$
1640: 34,269,305,313,381,398,414,437,477,643,684,738,766,1159,1276,1395,1551,1588,1672,1682,1842,1993,2164,2253,2561,2628,2770,3035,3062,3182,3227,3318,3331,3581,3636,3662,3694,3876,3878,3942

$N=50$
2550: 60,109,131,188,283,377,441,531,581,761,886,1015,1083,1187,1380,1496,1576,1675,1714,1776,1865,2181,2200,2384,2398,2424,2748,2809,3216,3262,3331,3355,3504,3512,3745,3866,4191,4225,4298,4323,4420,4532,4562,4680,4733,4793,4836,4868,4874,4959

 Профиль  
                  
 
 Re: Al Zimmermann - Sums and Products
Сообщение26.11.2015, 15:28 
Аватара пользователя


21/02/10
1594
Екатеринбург
whitefox в сообщении #1076984 писал(а):
А нельзя ли, исходя из структуры решений, доказать их оптимальность?


Для алгоритма Herbert Kociemba вполне реально посчитать оценку. Полагаю она будет гораздо точнее, чем верхняя оценка Эрдёша.

 Профиль  
                  
 
 Re: Al Zimmermann - Sums and Products
Сообщение27.11.2015, 15:09 
Аватара пользователя


25/08/12
171
Germany
dimkadimon в сообщении #1076997 писал(а):
Гипотеза: Максимальную версию этой задачи можно решить оптимально. То есть для любого $N$ можно найти решение где все суммы и умножения различны. Такое решение будет иметь $N(N+1)$ очков.


Let p(i) be the i.th prime number, p(1)=2, p(2)=3, p(3)=5.... . Then a(k)= p(2^k), k=1,2,3,....N should give N(N+1) different values.

 Профиль  
                  
 
 Re: Al Zimmermann - Sums and Products
Сообщение29.11.2015, 12:15 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
Как вам новый вариант задачи? Мы с Алом решили что это самый сложный и интересный вариант. Даже N=23 трудно найти.

 Профиль  
                  
 
 Re: Al Zimmermann - Sums and Products
Сообщение30.11.2015, 22:26 
Аватара пользователя


29/04/13
8961
Богородский
Меня терзают смутные сомненья, что наш Jarek и с этой модификацией успешно разобрался :-) Браво :!:

Изображение

 Профиль  
                  
 
 Re: Al Zimmermann - Sums and Products
Сообщение01.12.2015, 04:42 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
Yadryara в сообщении #1078410 писал(а):
Меня терзают смутные сомненья, что наш Jarek и с этой модификацией успешно разобрался :-) Браво :!:

Ал добавил больше цифр после точки и теперь у Jarek меньше 30. Похоже что система округляла вверх. Задача NP-hard поэтому решить ее оптимально очень сложно, хотя решить ее лучше всех остальных (и набрать 30 баллов) вполне возможно.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 165 ]  На страницу Пред.  1 ... 3, 4, 5, 6, 7, 8, 9 ... 11  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: Dmitriy40


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group