Al Zimmermann - Sums and Products

[Pavlovsky]

whitefox

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

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

[Pavlovsky]

61 24.5691 Valery Pavlovsky Ekaterinburg, Russia 25 Nov 2015 20:35

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

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

[dimkadimon]

Pavlovsky в сообщении #1076711 писал(а):

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

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

[Pavlovsky]

dimkadimon в сообщении #1076925 писал(а):

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

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

[whitefox]

dimkadimon
Топ-10 тоже неплохо.
Мои поздравления.

[dimkadimon]

whitefox в сообщении #1076933 писал(а):

dimkadimon
Топ-10 тоже неплохо.
Мои поздравления.

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

[Pavlovsky]

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

[whitefox]

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

[Pavlovsky]

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

[dimkadimon]

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

[Pavlovsky]

whitefox в сообщении #1076984 писал(а):

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

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

[Herbert Kociemba]

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.

[dimkadimon]

Как вам новый вариант задачи? Мы с Алом решили что это самый сложный и интересный вариант. Даже N=23 трудно найти.

[Yadryara]

Меня терзают смутные сомненья, что наш Jarek и с этой модификацией успешно разобрался Браво

[dimkadimon]

Yadryara в сообщении #1078410 писал(а):

Меня терзают смутные сомненья, что наш Jarek и с этой модификацией успешно разобрался Браво

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