Prime Sums

[Nataly-Mak]

dimkadimon

Цитата:

Это редкость в оптимальном решении

У вас больше нет ни одного рекорда с повторением простых сумм?

-- Пн ноя 05, 2012 08:07:00 --

Посмотрела свои решения 502 и 790, в этих решениях простые суммы не повторяются.
Но вот решение 510 есть с повторением простых сумм:

31, 67, 59, 47, 53, 29, 61, 79, 43, 41, 79

И решение 508 тоже есть с повторением простых сумм:

29, 71, 61, 59, 41, 71, 67, 53, 37, 47, 43

Не исключено, что и решение 502 есть с повторением.

[Pavlovsky]

Nataly-Mak в сообщении #640167 писал(а):

Повторение простых сумм - дело обычное, во многих решениях это имеется.

Повторение простых сумм, явный признак не оптимальности решения. У меня во всех решениях суммы линий не входящих в зачет, гораздо больше сумм линий входящих в зачет.

[Nataly-Mak]

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

Повторение простых сумм, явный признак не оптимальности решения.

Пока не понимаю, почему в оптимальных решениях простые суммы не могут повторяться; точнее - могут (как в примере dimkadimon для N=5), но очень редко.

И dimkadimon пока не ответил на вопрос: есть ли у него другие рекорды с повторением простых сумм?
Обращаю этот вопрос ко всем участникам, имеющим рекордные решения.

[Pavlovsky]

Nataly-Mak в сообщении #640196 писал(а):

Пока не понимаю, почему в оптимальных решениях простые суммы не могут повторяться;

Маленькие числа, в оптимальном решении должны концентрироваться на зачетных линиях. Значит незачетным линиям должны доставаться большие числа.

Пример моего решения для N=8 максимальное простое число в зачетных линиях =239. А минимальная сумма в незачетных линиях =292. С ростом N этот разрыв увеличивается.

[Nataly-Mak]

Нет, всё равно непонятно.
Ну и пусть себе маленькие числа концентрируются в зачётных линиях. Однако это не мешает ещё на какой-то линии получить такое же простое число в сумме, то есть повтор. И какя разница - какая из этих двух линий с повторяющейся суммой будет считаться зачётной?? Каждая из них может считаться зачётной!

[dimkadimon]

Nataly-Mak в сообщении #640196 писал(а):

И dimkadimon пока не ответил на вопрос: есть ли у него другие рекорды с повторением простых сумм?

нет

[Nataly-Mak]

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

[svb]

Задача.
Рассмотрим разбиение чисел 1,2,...,m$ , где $m = n^2 $ , на 5 групп $M_0 ,M_1 ,M_2 ,M_3 ,M_4 $ . Пусть $a_i $ - число элементов в группе $M_i$ , $m\left( x \right)$ - номер группы, к которой принадлежит число $x$ .
Порядок чисел внутри каждой группы произвольный, тогда число различных разбиений равно $C = \frac{{m!}}{{a_0 !a_1 !a_2 !a_3 !a_4 !}}$ . Для каждого разбиения можно определить значение:
$count\left( r \right) = count\left( {a_0 ,a_1 ,a_2 ,a_3 ,a_4 } \right) = \sum\limits_{i = 1}^m {im\left( i \right)} $
Чему равно число разбиений $F\left( t \right)$ , для которых $count\left( {a_0 ,a_1 ,a_2 ,a_3 ,a_4 } \right) = t$ ?

Пример. $n = 5$ . $C\left( {1,8,7,8,1} \right) = {\rm 1893102354000}$ , $F\left( {482} \right) = F\left( {818} \right) = 1$ .
$\sum\limits_{t = 482}^{812} {F\left( t \right)} = {\rm 1893102354000}$ , а вот чему равно $F\left( {502} \right)$ или $F\left( {790} \right)$ ?

[dimkadimon]

Nataly-Mak в сообщении #640167 писал(а):

Интересный вопрос: является ли ряд решений 502, 504, 506, ...,786, 788, 790 для N=5 полным, или в нём есть отсутствующие элементы?

Вот ето правда интересный вопрос. Стоит исcледовать

[Nataly-Mak]

Россияне на данный момент выглядят в таблице результатов совсем не плохо:

Цитата:

2 Alex Chernov 50.000000 11-04-2012 @ 20:18:58
6 Serg Belyaev 49.994300 10-31-2012 @ 22:12:29
27 Natalya Makarova 46.164400 11-06-2012 @ 07:11:58
30 Vladimir Chirkov 45.325700 11-04-2012 @ 15:43:24
38 Artem Ripatti 32.933600 10-14-2012 @ 11:53:28
42 Pavel Burdanov 28.311000 10-22-2012 @ 15:19:55
44 Valery Pavlovsky 10.964800 11-05-2012 @ 17:00:12
50 Konstantin Porozov 5.696070 10-20-2012 @ 18:52:20

Радует активность участника Vladimir Chirkov, он очень быстро достиг позиции 30.
И огорчает пассивность участников: Artem Ripatti, Pavel Burdanov, Konstantin Porozov.

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

Да, с баллами в этом конкурсе напряжёнка
Поскольку многие конкурсанты имеют 49 баллов с хвостиком, всё, что меньше 49 баллов, уже не котируется совершенно.
Ну, будем так считать (по-нашему ):
первая группа конкурсантов с количеством баллов больше 49 - это очень высокий рейтинг.
Втрорая группа - с количеством баллов больше 40 - тоже довольно высокий рейтинг.
Попасть в эти две группы - в данном конкурсе весьма хороший показатель.

-- Вт ноя 06, 2012 07:49:23 --

Вчера проделала эксперимент. Результат эксперимента ошарашил.

Имею некоторое решение для N=6 с результатом 902. Схема решения:

3 x 3 x 3 x
x x x 3 x x
3 x x x 3 x
x 3 x x x 3
x x 3 x x x
x 3 x x x 3

В схеме отмечены только элементы с весом 3, все остальные элементы (с весом 0,1,2,4) заменены символом х.
Множество чисел с весом 3:

{1,3,4,5,7,8,10,11,12,14,15}

Зафиксировала все элементы с весами 0,1,2,4, а для элементов с весом 3 организовала полный перебор, то есть это 11! (одиннадцать факториал) вариантов.
Написала программу, запускаю, и... получаю один-единственный результат - 902 (программа выполнилась мгновенно).
Возможно ли такое? Перепроверила код программы, ошибки не вижу.
Я ожидала получить кучу различных решений, пусть не минимальных, но хоть каких-нибудь. И вот такой получила результат.
До сих пор не могу поверить, что такое возможно. Может, всё-таки где-то ошиблась

Собираюсь продолжить эксперимент: организовать частичный перебор элементов с другими весами. Может, это что-то даст.
Да, интересный момент в этом примере: множество чисел с весом 0 - {32,33,34,35,36}.
Вот оно как Самые большие числа выброшены из игры.

[Pavlovsky]

svb в сообщении #640554 писал(а):

Задача.

Для начала можно порешать упрощенную задачу.
Найти все варианты сумм $S_1,S_2 ,S_3 ,S_4 $ таких, что $t=S_1+2*S_2 + 3*S_3+4*S_4 $. При заданных $\left( {a_0 ,a_1 ,a_2 ,a_3 ,a_4 } \right)$, на суммы $S_1,S_2 ,S_3 ,S_4 $ должны быть наложены дополнительные ограничения, обеспечивающие возможность набрать эти суммы числами 1,2,...,m$.

[dimkadimon]

Nataly-Mak в сообщении #640588 писал(а):

Возможно ли такое? Перепроверила код программы, ошибки не вижу.

Конечно. Все элементы которые двигаются имеют один и тот же вес (3), значит и сумма будет одинаковая.

-- 06.11.2012, 13:40 --

Nataly-Mak в сообщении #640588 писал(а):

первая группа конкурсантов с количеством баллов больше 49 - это очень высокий рейтинг.
Втрорая группа - с количеством баллов больше 40 - тоже довольно высокий рейтинг.

Я бы сказал что только 49.9+ это очень высокий рейтинг, а 49+ хороший рейтинг. Набрать 49 не так уж сложно. Как Robert говорил, самая простая программа отжига может набрать 49 баллов без проблем.

[Nataly-Mak]

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

Конечно. Все элементы которые двигаются имеют один и тот же вес (3), значит и сумма будет одинаковая.

Не поняла, какая сумма будет одинаковая?
Ведь элементы с весом 3 переставляются! Значит, суммы в линиях изменяются. Ведь эти элементы входят в 12 различных линий!
Получается, что ни один из 11! вариантов перестановок элементов с весом 3 не даёт 12 простых сумм в линиях (при фиксированных остальных элементах). Это неожиданный результат.

[dimkadimon]

Nataly-Mak в сообщении #640593 писал(а):

Не поняла, какая сумма будет одинаковая?
Ведь элементы с весом 3 переставляются! Значит, суммы в линиях изменяются. Ведь эти элементы входят в 12 различных линий!
Получается, что ни один из 11! вариантов перестановок элементов с весом 3 не даёт 12 простых сумм в линиях (при фиксированных остальных элементах). Это неожиданный результат.

Общая сумма S не меняется. Подумайте как следует над этим. Тут кроется вся суть задачи...

[Pavlovsky]

Nataly-Mak в сообщении #640593 писал(а):

Ведь элементы с весом 3 переставляются! Значит, суммы в линиях изменяются.

Это замечательная особенность использования схем. Любая перестановка чисел с одинаковым весом не изменяет сумму решения! То есть перебрав 11! вариантов перестановок чисел веса 3, вы могли получить много решений (у вас получилось только одно?), но все решения будут иметь результат 902!