Prime Sums

[dimkadimon]

Pavlovsky
Конкурс будет продолжаться до самого конца как планировалось. Возможно еще остались новые рекорды для N=6 и 7. Как организатор конкурса я не имею право получать призы (я решил так будет справедливо). Поетому 2ое и 3ие места еще свободны.

-- 22.10.2012, 15:14 --

Robert, I completely understand your frustration. I don't want to take anything away from your achievements. You were first to find most of the records and you reached 50 very quickly. This is why you are ranked 1st and your name is all over the tops page. You deserve full recognition for your effort.

Now due to this forum, a number of other people have found the "right" method. I will be honest with you, because I am one of those people. Without this forum I wouldn't have reached 50, at least not so quickly.

I want to point out a few things about this issue. First of all, Neil encourages discussion of the problem. This has been done in the past for other problems too. As far as I understand, problem discussion is ok, provided no solutions are given and no code is released before the end of the contest. Perhaps Neil can comment on that? Secondly, the people here are not here to win prizes and gloat about their ranking. Here we have a very friendly atmosphere, where people want to learn and discuss ideas. It is only this way that we can find new records and move science forward. This is what makes this site unique and different from other sites. No one is to blame for these issues.

You do raise an important point though. Where does one draw the line between problem discussion and revealing too much of the solution? Perhaps the rules of the contest should be tightened in the future. Again this is something that only Neil can decide.

I hope this post makes you feel better and you will continue competing.

[Gerbicz]

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

Gerbicz
Я не считаю, что я нарушаю правила конкурса.

This is true, becuase there is no rules page.

"1) Решений я не публикую. К тому же написанных правил у конкурса нет."
You don't need to publish them, for a programmer it is enough to read these ideas, then he/she can implement these. Dmitry is the living example for this.

"2) Идеи, которые я излагаю, достаточно очевидны. Их еще надо реализовать! То что вы в первую же ночь конкурса пришли к аналогичным идеям, и даже успели их реализовать, подтверждает это."

These ideas were not trivial even for me. Though it was not luck to find, if you see and solve lots of problems then you gain a great routine in problem solving.

"First of all, Neil encourages discussion of the problem. "

OK, I understand, but personally I don't like these open contests (own term, similar to "open exam" on universities where you can use everything).

"As far as I understand, problem discussion is ok, provided no solutions are given and no code is released before the end of the contest."

This means that everybody could use the best algorithms/ideas (if you can speak Russian or find a good translator), and then just code them like a slave. And the winner is the one who code them faster or has got more/faster computers.

"where people want to learn and discuss ideas. It is only this way that we can find new records and move science forward. This is what makes this site unique and different from other sites."

On those other sites there is a discussion also, but only after the contest. What is the difference between them? I would say nothing.
And on those sites some contestant also publish their code after the contest.

[svb]

Конкурсы из "школьных" задач лично мне были интересны более 40 лет тому назад, а сейчас я к ним равнодушен. Собственно и конкурсы меня не интересуют - призы и прочие "побрякушки" только любителям. Но другое дело интересные задачи. В этом что-то есть притягательное.
Gerbicz

Цитата:

These ideas were not trivial even for me. Though it was not luck to find, if you see and solve lots of problems then you gain a great routine in problem solving.

Странно, скорее всего у вас возникла своя ассоциация, т.е. собственная идея, но причем здесь Pavlovsky? А может это ложный ход? Для хорошей задачи самое опасное попасть под влияние чужой "идеи", которых великое множество.

Цитата:

OK, I understand, but personally I don't like these open contests (own term, similar to "open exam" on universities where you can use everything).

Хорошие преподаватели, например, в МФТИ всегда предпочитали "открытые" экзамены. Конечно, во времена Кордано, который спер решение у Тарталья, был другой менталитет. Но вы уж извините нас, "совков", мы еще не привыкли к "новым" порядкам

-- Вт окт 23, 2012 00:50:03 --

Интересно, для N=6 имеются решения min=887 max=1777 ?

[Pavlovsky]

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

Интересно, для N=6 имеются решения min=887 max=1777 ?

Решения должны быть четными. Сумма четного количества нечетных чисел - четна.

[Pavlovsky]

Gerbicz в сообщении #634451 писал(а):

OK, I understand, but personally I don't like these open contests (own term, similar to "open exam" on universities where you can use everything).

Я рядовой участник конкурса, и правил не разрабатываю. Так что вопрос какие должны быть правила конкурса явно не ко мне. Я готов выполнять любые написанные правила.

Если вас интересует мое личное мнение. Я использую специфический язык программирования. Который работает в сотни раз медленнее нормальных транслируемых языков программирования (например таких как C++). Поэтому, что бы получить приличный результат, мне приходится очень хорошо поработать головой. Если не будет возможности публичного обмена идеями (только идеями, а не решениями и детально разработанными алгоритмами), то интерес к такому конкурсу у меня упадет до минимума.

Gerbicz в сообщении #634451 писал(а):

This means that everybody could use the best algorithms/ideas (if you can speak Russian or find a good translator), and then just code them like a slave. And the winner is the one who code them faster or has got more/faster computers.

Все гораздо сложнее. Обмен базовыми идеями, позволит:
1) Подготовленным участникам немного раньше получить приличные результаты и переключится на решение действительно трудных проблем.
2) Не подготовленные участники конкурса, чуть улучшат свои результаты, но на распределение мест в первой десятке это никак не повлияет.
3) Посмотреть на конкурсную задачу, как на математическую проблему. Сформулировать и доказать свойства проблемы. И только затем разрабатывать алгоритмы на базе математически строгих утверждений. Это самый правильный подход. А вот кодировать первую пришедшую в голову мысль - путь в никуда.
4) Базовую идею еще надо реализовать. Решить множество небольших промежуточных проблем. Сформулировать вспомогательные идеи. Разработать оптимальный код программы. Эти задачи явно не для "like a slave".

-- Вт окт 23, 2012 10:28:56 --

Посмотрел тему. Чего же такого страшного я написал. Какие военные тайны выдал. Нашел конкретное только вот это.

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

Ранее писал, для четных N можно выбрать N/2 диагоналей и N/2 обратных диагоналей. Так чтобы любая диагональ и обратная диагональ пересекались в двух точках. Добавим к ним N/2 любых строк и N/2 любых колонок. Это и будет оптимальная схема зачетных 2N линий. Не трудно посчитать минимальный (максимальный) результат для этой схемы. Смотрите таблицу выше.

И что прочитав это можно набрать 50 баллов?? У меня почему то не получилось. Пока у меня вообще нет работающей программы и результатов.

[whitefox]

Вот никак не могу понять, почему Pavlovsky
не имеет права обсуждать эту задачу?

Задача-то, как оказалось, не является простым "школьным" примером. Она интересна сама по себе, безотносительно какой-либо связи с конкурсом.

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

Именно из этого исходил Кардано, когда опубликовал решение Тартальи.

[dimkadimon]

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

Вот никак не могу понять, почему Pavlovsky
не имеет права обсуждать эту задачу?

По правилам конкурса он имеет полное право обсуждать задачу.

[whitefox]

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

По правилам конкурса он имеет полное право обсуждать задачу.

Ну и какие тогда к нему претензии?
За что человека обидели?

[svb]

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

Посмотрел тему. Чего же такого страшного я написал. Какие военные тайны выдал. Нашел конкретное только вот это.

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

Ранее писал, для четных N можно выбрать N/2 диагоналей и N/2 обратных диагоналей. Так чтобы любая диагональ и обратная диагональ пересекались в двух точках. Добавим к ним N/2 любых строк и N/2 любых колонок. Это и будет оптимальная схема зачетных 2N линий. Не трудно посчитать минимальный (максимальный) результат для этой схемы. Смотрите таблицу выше.

И что прочитав это можно набрать 50 баллов?? У меня почему то не получилось. Пока у меня вообще нет работающей программы и результатов.

Самое забавное в том, что это неверно.

[Pavlovsky]

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

Самое забавное в том, что это неверно.

Что именно неверно? Конечно у меня нет доказательства, что эта схема оптимальная. Но если отказаться от

Цитата:

выбрать N/2 диагоналей и N/2 обратных диагоналей. Так чтобы любая диагональ и обратная диагональ пересекались в двух точках.

, тогда мы слишком много теряем. И не видно чем можно компенсировать эту потерю.

Сергей, у вас есть схемы (конфигурации) для четных N, которые превышают оценки из таблицы приведенной мной раньше? Не нужны сами схемы, дайте плиз контрольные суммы.
Таблица здесь (в таблице учтено, что решения должны быть четными):
post632702.html#p632702

[svb]

Pavlovsky

Цитата:

Что именно неверно?

Я стал искать схемы для N=6, которые составлял вручную, и с удивлением обнаружил, что никак не могу получить значение меньше 927. Но текущий рекорд 890. Потом нашел схему с 887.

Конечно, возможно истина рядом, но ...

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

-- Вт окт 23, 2012 14:33:25 --

Да, еще хочу добавить. Для схем существует очевидное соотношение $min+max=2N^2(N^2+1)$, но это только для конкретной схемы. Реальные экстремумы могут не достигаться при малых N. Особенно, если забыть про четность

Посмотрел вашу таблицу. Она противоречить вашему утверждению о "произвольности" добавления строк/столбцов.

[Pavlovsky]

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

Она противоречить вашему утверждению о "произвольности" добавления строк/столбцов.

Да вы правы. Проверил различные варианты добавления строк и колонок. Минимум(максимум) достигается когда берем первые N/2 строк и N/2 колонок.

-- Вт окт 23, 2012 17:24:11 --

Поиск оптимальных конфигураций сама по себе является интересной задачей.
Вспомогательная задача.
Выберем в квадрате NxN 2N линий (строки, колонки, диагонали и обратные диагонали). По выбранным линиям можно составить схему пересечений. Такого вида:


В каждой ячейке, число означает количество пересечений выбранных линий в ячейке. Посчитаем количество ячеек с пересечениями каждого вида (a0,a1,a2,a3,a4).
Тогда можно посчитать оценку:
Sum1=a1+a2+a3+a4
Sum2=a2+a3+a4
Sum3=a3+a4
Sum4=a4
Min= [Sum1(Sum1+1)/2]+[Sum2(Sum2+1)/2]+[Sum3(Sum3+1)/2]+[Sum4(Sum4+1)/2]
Пример для конфигурации на рисунке:
Sum1=0+13+8+0=21
Sum2=13+8+0=21
Sum3=8+0=8
Sum4=0
Min= 231+231+36+0=498

Задача: Найти 2N линий таких чтобы оценка Min была наименьшей.

[svb]

Pavlovsky

Цитата:

Задача: Найти 2N линий таких чтобы оценка Min была наименьшей.

Имеется один интересный момент. Зависимость от (a1,a2,a3,a4) квадратичная, т.е. в окрестности экстремума ситуация достаточно пологая, что для реальных решений увеличивает набор проверяемых схем. Схемы можно находить и простеньким перебором.

Дополнительное усложнение проблемы в выборе множеств M1,M2,M3,M4. Выбор (1,2,...,a4),(a4+1,...) годится для подсчета, но при малых N эти множества никуда не годятся. Поэтому идет усложнение перебора.

Для больших N эта проблема исчезает - заполняем схему нужными нам числами и в путь - слишком большое пространство перебора. Здесь, конечно, имеется некоторый изъян в задаче. Интересно было бы найти новый вариант задачи. Крайний случай: если бы мы искали не простые линии, а из чисел смита, то решений бы и не было совсем. Искусственность выбора числа линий 2N бросалась в глаза с самого начала. Да и критерий подсчета результата сыграл свою роль. Иная картина была бы, возможно, если бы считали не сумму линий, а сумму квадратов значений линий. Тогда благостная картина развалилась бы.

[dimkadimon]

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

Искусственность выбора числа линий 2N бросалась в глаза с самого начала. Да и критерий подсчета результата сыграл свою роль. Иная картина была бы, возможно, если бы считали не сумму линий, а сумму квадратов значений линий. Тогда благостная картина развалилась бы.

Вы правы - 2N было выбрано совершено случайно. Я теперь думаю что 4N простых линий (где можно повторяющиеся) было бы интереснее. Ещё была такая идея: убрать число 2N и вместо линий использовать суммы из 5ти чисел. Первое число это одна из N^2 клеток, а остальные 4 это её соседи. Например

abc
def
ghi

имеет вот такие суммы:

a+b+d+c+g
b+a+c+e+h
c+b+a+f+i
d+a+e+g+f
e+b+f+h+d
f+c+d+e+i
g+d+h+a+i
h+e+i+b+g
i+f+h+g+c

В этом варианте можно искать не сумму простых чисел S, a просто количество простых чисел. Вот например тут 20 уникальных простых чисел из 25ти возможных:

9,15,21,5,3,
14,23,24,19,13,
20,25,22,10,12,
18,17,16,4,2,
6,7,8,11,1

Если будет интерес то можно открыть мини-конкурс с этими новыми правилами.

[dimkadimon]

Ура Robert нашел новый рекорд для N=6, а значит еще есть жизнь в етой задаче.