Prime Sums

[Nataly-Mak]

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

Впрочем, я не спорю, дело вкуса, кому как нравится. Мне больше нравится полный перебор, он надёжнее

[whitefox]

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

Решение, если оно существует, может найтись и при полном переборе довольно быстро

По закону Мёрфи, если решение существует, то при полном переборе оно будет найдено самым последним.

[Nataly-Mak]

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

По закону Мёрфи, если решение существует, то при полном переборе оно будет найдено самым последним.

Это неправильный закон, в печку его
Я десятки раз находила магические квадраты там, где полный перебор не выполняется за реальное время, и находились эти решения иногда мгновенно. Самый удивительный был ассоциативный квадрат 6-го порядка из простых чисел. Написала программу, запустила и собралась идти завтракать, не успела встать со стула, как решение появилось на экране

[whitefox]

То что у Вас "лёгкая рука" я уже заметил.

[Nataly-Mak]

Получено решение с 13 правильными зачётными линиями. Эх, как обидно, чуть-чуть не хватило.

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

Предположим: правильная 13-ая зачётная линия найдена.
Обозначим сумму простых сумм по 13 найденным зачётным линиям $S_1$.
$S_2=1802-S_1$
Вопрос такой: может ли $S_2$ оказаться:
а) не простым числом;
б) простым числом, имеющимся среди значений найденных 13 сумм

Думаю, что вполне возможно и то, и другое. Может, ошибаюсь?

Да, $S_2$ оказалась не простым числом, она равна 115.
А $S_1=1687$, и в сумме получаем 1802.

[svb]

Случайно наткнулся.

Задача.
Пусть $a_i$ - число клеток, через которые проходит $i$ линий. Доказать, что $a_1+4a_2+9a_3+16a_4$ зависит только от $N$. Чему равна эта сумма?

Пока ответа не знаю

-- Ср дек 05, 2012 16:37:51 --

Известные соотношения:
$a_1+2a_2+3a_3+4a_4=2N^2$
$a_3+2a_2+3a_1+4a_0=2N^2$
$a_0+a_1+a_2+a_3+a_4=N^2$

-- Ср дек 05, 2012 16:45:58 --

И для полноты картины:
$S_{\min } = \frac{{a_4 \left( {4a_4 + 6a_3 + 4a_2 + 2a_1 } \right) + a_3 \left( {3a_3 + 4a_2 + 2a_1 } \right) + a_2 \left( {2a_2 + 2a_1 } \right) + a_1 a_1 }}{2} + N^2 $
$S_{\max } = 2N^2 \left( {N^2 + 1} \right) - S_{\min } $

-- Ср дек 05, 2012 17:17:29 --

Еще проверил. Оказывается, что условие задачи не совсем верно, но ... тем интереснее

[dimkadimon]

Улучшить решения у меня не получается. Понятия не имею как тут народ находит перебором (случайным или нет) лучшие решения. Ведь перебор даже 19ти чисел займёт 10^17 проверок. Я пробовал достаточно оптимизированый перебор с быстрым отсечением плохих решений и он даже близко к концу не подошёл.


Решил заняться нахождением разных решений близким к лучшим. Если у кого есть эти решения то пожалуйста сообщите.

Для N=6 MIN нашёл все решения от 890 до 910, кроме 892.
Для N=6 MАХ нашёл все решения от 1740 до 1758, кроме 1754, 1752 и 1750.
Для N=7 MIN нашёл все решения от 1808 до 1842, кроме 1810 (ещё неизвестно про 1804).
Для N=7 MАХ нашёл все решения от 3060 до 3086, кроме 3068, 3074 и 3080 (ещё неизвестно про 3088).

[Scryer]

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

Для N=6 MIN нашёл все решения от 890 до 910, кроме 892.
Для N=6 MАХ нашёл все решения от 1740 до 1758, кроме 1754, 1752 и 1750.
Для N=7 MIN нашёл все решения от 1808 до 1842, кроме 1810 (ещё неизвестно про 1804).
Для N=7 MАХ нашёл все решения от 3060 до 3086, кроме 3068, 3074 и 3080 (ещё неизвестно про 3088).

For N=6 MIN I have 892 - I have been stuck there for a long time.
For N=6 MAX I have 1754 and 1750, but not 1752.
For N=7 MAX I have nothing for your list.
For N=7 MIN I have nothing for your list.

[Pavlovsky]

Есть 3090 для N=7! Остались N=6 (максимум и минимум) и N=8,10 (максимум). Думаю, что эти задачи будут решены на этой неделе.
Кто хочет занять второе место? У вас еще есть несколько дней.

[Nataly-Mak]

Эх, всё, что Pavlovsky надо для получения 50 баллов, в моей команде уже есть
И наоборот: всё, что моей команде надо для получения 50 баллов, уже есть у Pavlovsky.
Такое вот распределение.

whitefox
у нас есть несколько дней ... до конца света

[Pavlovsky]

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

Впрочем ничего особенного в алгоритме нет. Обычный перебор. Только перебор заменен на случайный выбор.

Немного слукавил. Есть в алгоритме секретная идея. Но ее публиковать пожалуй не буду.
1) Надо оставить что то себе.
2) Когда наберу 50 баллов, то может и опубликую.

[Nataly-Mak]

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

Немного слукавил. Есть в алгоритме секретная идея.

Ну, положим, алгоритм комбинирования случайного выбора с полным перебором может сработать и без всякой секретной идеи, если схема выбрана удачно.
Как я уже писала, моя программа, реализующая данный алгоритм для двух разных схем, легко даёт для первой схемы 12 правильных зачётных линий, а для второй схемы - 13 правильных зачётных линий. Выдаёт таких решений ну очень много. 14-ая зачётная линия получается или не простое число (например, 115, 119, 121), или простое число, повторяющее одно из первых 13 значений (например, 113, 127, 137).
Есть подозрение, что схемы эти выбраны неудачно и правильное решение вообще в них не "сидит", но это только предположение. Вот если бы был выполнен полный перебор, то это был бы факт. Увы, здесь полный перебор не выполняется за реальное время (ещё раз выскажу удивление, каким образом svb удалось выполнить полный перебор для схемы с оценкой 1802 очень быстро).

Цитата:

Но ее публиковать пожалуй не буду.
1) Надо оставить что то себе.
2) Когда наберу 50 баллов, то может и опубликую.

Ни, ни!
Наберёте 50 баллов, займёте 2-ое место, опубликуете секретную идею и... вас дисквалифицируют

Это напомнило мне анекдот о плачущей Фросе

[Pavlovsky]

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

если схема выбрана удачно

Так кто мешает перебрать все схемы? Неизоморфных схем от 1798 до 1802 всего 1158 штук.

[Nataly-Mak]

Хе-х...
Я для каждой схемы пишу отдельную программу. Увы, писать одну программу сразу для всех схем не умею
Это мне надо написать 1158 программ
Нет, никто не мешает, просто у меня мало времени осталось... до конца света

[Nataly-Mak]

Пытаюсь что-нибудь выжать из программы, реализующей алгоритм "случайный выбор + полный перебор". Ну вот как жалко, что 13 зачётных линий получаются, а 14-ая никак не хочет
Анализирую ситуацию. Взяла решение с 13 правильными зачётными линиями:

127,139,131,107,137,103,113,151,163,149,157,109,101

Сумма этих значений равна 1687, на 14-ую зачётную линию остаётся 115. Всё правильно, такая она и получается. Это плохо. Тогда изменяю набор первых 13 зачётных линий, заменяю 149 на 167. Теперь сумма по 13 зачётным линиям равна 1705 и на 14-ую зачётную линию остаётся 97. Это уже хорошо, такая простая сумма может быть получена в 14-ой линии.
Сужаю множество простых значений для проверки точно до 14 указанных чисел. Всё: либо сумма чисел в зачётной линии принимает одно из 14 значений и тогда программа идёт дальше, либо не принимает ни одно из 14 значений, и тогда перебор возвращается.

Запускаю программу, программа сразу выдаёт несколько решений с 13 правильными зачётными линиями, при этом на экран выводится значение 14-ой зачётной линии.
Показываю окно программы. Значения 14-ой зачётной линии получились 105 и 109. Второе значение уже хорошо, но повторяет одно из первых 13 значений.



Ну, пусть крутится теперь программа. Она может очень долго крутиться, так как в ней присутствует случайная расстановка 16 элементов (для 26 элементов полный перебор).

Покрутив программу с таким раскладом, можно изменить расклад (разложение 1802 на 14 простых) и снова покрутить. Решение найдётся, если а) оно в этой схеме существует и б) крупно повезёт

-- Пт дек 07, 2012 16:30:38 --

Активность на конкурсе очень низкая. В группе лидеров вообще полный штиль
Сейчас посчитала: 33 конкурсанта ввели последние результаты в октябре, почти половина всех участников! Занимаются ли они задачей или бросили её совсем? Трудно сказать. Но мне кажется, большинство вводят результаты сразу же, мало кто складывает их под подушку.

Уже 26 конкурсантов имеют 49+ баллов, 16 из них - 49,9+ баллов. Получается, что 21% участников проникли в алгоритм получения оптимальных решений для N>7. И только решения для N=6,7 для многих стали камнем преткновения.

Задача какая-то очень однобокая