Prime Sums

[Nataly-Mak]

Конкретизирую свой вопрос ещё...
Есть 11 чисел с весом 3:

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

и есть ещё 20 натуральных чисел от 1 до 30, все отличны от приведённых 11 чисел и попарны различны между собой.
[ужё отмечала выше, что числа 32,33,34,35,36 в суммах по линиям не принимают участия]

Эти числа помещены в квадрат 6х6 (выше приведена схема размещения).
Из этих двух групп чисел набирается 12 сумм (по 12 линиям в квадрате 6х6 - строки, столбцы, всякие диагонали).
Обозначим числа с весом 3: a1,a2,a3,...,a11; числа второй группы будем обозначать символом х.
Тогда, например, первые 3 из 12 сумм набираются так:

s1=a1+x+a2+x+a3+x
s2=a1+x+x+x+x+a4
s3=x+x+x+a5+x+a4
. . . . . . . 

Подчеркну: числа второй группы зафиксированы, то есть в квадрате 6х6 они всегда расположены в одних и тех же ячейках.
При первоначальном расположении чисел в квадрате мы имеем 12 простых сумм по 12 линиям, и сумма этих простых сумм равна 902.

Теперь переставляем числа с весом 3. Делаем все 11! перестановок.

Вопрос: могут ли (теоретически) при такой перестановке чисел с весом 3 появиться новые простые суммы хотя бы в одной из рассматриваемых 12 линий

Больше не знаю, как можно изложить вопрос, чтобы получить на него ответ

[Nataly-Mak]

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

и есть ещё 20 натуральных чисел от 1 до 30, все отличны от приведённых 11 чисел и попарны различны между собой.
[ужё отмечала выше, что числа 32,33,34,35,36 в суммах по линиям не принимают участия]

Вообще какой-то маразм так быстро снимать возможность редактирования!
Как я понимаю по времени предыдущего сообщения, на обдумывание сообщения даётся всего один час. Это очень мало!
Я постоянно думаю над вопросом, постоянно возвращаюсь к сообщению и вижу в нём ошибки и/или опечатки.

Модераторы и администраторы, если вы сюда заходите, нельзя ли увеличить срок для редактирования сообщения?

Чтобы исправить опечатки или ошибки, приходится цитировать сообщение.
Вот привела цитату, в которой опечатка.
Конечно, правильно будет так: есть ещё 20 натуральных чисел от 1 до 31, все отличны от приведённых 11 чисел и попарно различны между собой.
На всякий случай перечисляю эти числа:

{24,26,27,23,30,28,31,29,16,18,25,21,19,13,22,20,17,6,2,9}

Может быть, правильнее сказать: есть ещё 20 натуральных чисел из интервала (1,31].

-- Вт ноя 06, 2012 13:33:43 --

Сочинила пример с квадратом 3х3.
Вот квадрат:

1 2 4 
3 9 7 
5 6 8

Имеем 4 зачётных линии (повторяющиеся простые суммы не учитываются):

1+2+4=7
2+9+6=17
4+7+8=19
2+3+8=13

Сумма простых сумм равна 56.

Будем переставлять числа с весом 1:

{1, 3, 6, 7, 9}
Остальные числа пусть стоят на своих местах.
Будем иметь 120 вариантов различных наборов сумм по 4 указанным линиям.

Неужели ни один из этих вариантов не даст другой набор простых сумм по этим 4 линиям?
Неважно, какая будет сумма этих простых сумм!

Аналогичный пример у меня с квадратом 6х6.

[Nataly-Mak]

Написала программку для приведённого выше примера с квадратом 3х3.
Когда задала условие, что все 4 суммы различны, получилось всего два решения с набором сумм: 7,13,19,17.
Когда убрала условие различности простых сумм, программа выдала следующие решения:

 7  13  19  17 
 56 
 7  13  19  17 
 56 
 7  19  19  11 
 56 
 7  19  19  11 
 56 
 13  13  13  17 
 56 
 13  13  13  17 
 56 
 13  19  13  11 
 56 
 13  19  13  11 
 56

Я пока мало что понимаю
Вижу, что другие простые суммы по 4 линиям получаются. Например, получена простая сумма 11; такой суммы нет в первоначальном наборе сумм.
Но... почему эти 4 суммы всегда дают результат 56
Случайное совпадение?

-- Вт ноя 06, 2012 15:26:45 --

Продолжаю эксперимент с квадратом 6х6.
Сделала небольшие перестановки во множествах чисел с весом 3 и с весом 4.
Но! По-прежнему переставляю только числа с весом 3, все остальные числа в квадрате остаются на своих местах.

Результат работы программы:

79  59  83  61  89  97  107  47  53  67  71  0  131  0  0 
 944 
83  67  101  61  79  89  103  47  59  53  71  0  137  0  0 
 950

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

Осмысливаю...

P.S. Нулями программа заменяет или суммы, не являющиеся простыми числами, или повторяющиеся суммы.

[Nataly-Mak]

Pavlovsky
по-моему, я уже нашла контрпример, опровергающий ваше утверждение.
Или нет? Что скажете? Эти два решения что нам говорят? Перестановка чисел с одинаковым весом дала новый результат! Набор зачётных линий в этих двух квадратах одинаковый (одинаковая схема!), а вот простые суммы в этих линиях получились различные (в некоторых линиях совпадают).

[Nataly-Mak]

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

Еще раз.

Перестанвки чисел одинкового веса, не изменяет сумму решения.

Pavlovsky
я жду ответ, однако.
Может быть, вы признаете, что высказанное вами утверждение неверно?

Уж от господина Каменецкого ответа не жду, т.к. его ответы меня больше вообще не интересуют.

А вы почему нарушаете правила ведения дискуссии?
Высказали заведомо ложное утверждение и... в кусты. А кто будет отвечать за это утверждение?

[svb]

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

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$.

Я дал оценочную задачу, не имеющего прямого отношения к конкурсу. Получить некоторое разбиение особого труда не составляет. При N>7 используются граничные разбиения (которых по 1 штуке), а дальше простой перебор, который быстро дает результат. При N<8 граничные разбиения не дают решений. Естественно возник вопрос об их количестве, чтобы оценить возможности перебора. Распределение $F\left( t \right)$, скорее всего, похоже на биноминальное, а вот приведенные цифры говорят о большом количестве разбиений, которые приходится рассматривать и о достаточно призрачных надеждах нахождения истинных рекордов с помощью перебора.

[dimkadimon]

Начилось интересное соревнование: http://russianaicup.ru/

[Gerbicz]

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

Задача.
Рассмотрим разбиение чисел 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)$ ?

Basic question. On online judges you can find hundreds of similar problems.

[dimkadimon]

Ого! - Wes вышел на первое место.

[Pavlovsky]

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

Распределение , скорее всего, похоже на биноминальное, а вот приведенные цифры говорят о большом количестве разбиений, которые приходится рассматривать и о достаточно призрачных надеждах нахождения истинных рекордов с помощью перебора.

Мне кажется вы переоцениваете важность и сложность задачи разбиения чисел по группам. Условия задачи таковы, что даже для N=5 существует вагон и маленькая тележка рекордных решений. Нам надо сузить пространство решений таким образом, чтобы в нем осталось хотя бы одно рекордное решение.

Полагаю, что почти любое разбиение чисел по группам, задающее искомую сумму, годится для поиска решения. У меня к разбиению всего одно эвристическое требование:

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

[Pavlovsky]

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

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

В задаче поиска оптимальной схемы (конфигурации) нет локальных минимумов. Любой алгоритм по-координатного спуска приводит к глобальному минимуму.

Скорее всего это так, но почему это так?

И все таки локальные минимумы есть! Нашел последовательность по-кординатных спусков, котрая не находит глобальный минимум.

[dimkadimon]

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

И все таки локальные минимумы есть! Нашел последовательность по-кординатных спусков, котрая не находит глобальный минимум.

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

[Pavlovsky]

N=15.
Пронумеруем линии. Сначала строки от 1 до 15. Затем колонки 16 до 30. Затем прямые диагонали (идущие из левого верхнего угла в правый нижний угол) от 31 до 45. Затем обратные диагонали от 46 до 60.
Тогда следующая схема:
1,4,5,7,8,10,11,12,16,18,19,20,21,22,26,27,31,32,33,34,36,37,38,46,47,49,50,51,52,53 имеет сумму 36964. И не улчшается моим алгоритмом. Оптимальная схема имеет сумму 36962.

Алгоритм у меня самый простой. Перебираю все зачетные линии и пытаюсь заменить их на свободные линии. Если сумма уменьшилась, итеративно повторяю процедуру для новой схемы.

-- Чт ноя 08, 2012 18:23:57 --


Симпатичная конфигурация

[svb]

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

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

Пользуюсь аналогичным алгоритмом, как у Pavlovsky. Начальную схему выбираю случайным образом. Обычно хватает одного раза, но бывают исключения (локальный минимум), чаще всего при N<9. Сначала собирался записывать найденные схемы, но т.к. процесс очень быстрый, то отказался от этого. Глобальные минимумы также различны.

-- Чт ноя 08, 2012 16:51:27 --

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

Полагаю, что почти любое разбиение чисел по группам, задающее искомую сумму, годится для поиска решения. У меня к разбиению всего одно эвристическое требование:

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

Увы! Если бы это было так. При N=5 я могу проводить полный перебор для заданного разбиения по группам (и заданной схемы). Так вот, чаще решений нет

[svb]

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

Было бы интересно создавать "анимации" и при рассмотрении других интересных задач.

Теперь о нашей задаче. 2N простых чисел дают нам рекордные суммы S. Естественно рассмотреть возможные представления S в виде суммы простых чисел. Этих представлений очень много, но при малых N вполне обозримо. Если эти представления расположить в убывающем порядке, то получается любопытная картина. Поясню: рассматриваем разложения $S = P_1 + P_2 + ... + P_{2N} $, где $P_{i + 1} < P_i $ располагаем в порядке убывания (можно и наоборот, просто так их легче было генерировать). Наблюдается следующая вещь: рекордные разложения оказались в конце списка, не в самом конце, но рядом.