Prime Sums

[whitefox]

Приведённые выше результаты по количеству не изоморфных схем были получены полным перебором.
Который выполнился удивительно быстро - для N=5 и N=6 мгновенно, для N=7 менее чем за час, а для N=8 менее чем за четыре часа.

[Pavlovsky]

Для N=8 601080390 вариантов. И это без учета изоморфизмов. Действительно немного.

[whitefox]

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

Для N=8 601080390 вариантов. И это без учета изоморфизмов. Действительно немного.

Удивительно то, что для чётных N (6 и 8) имеется очень мало не изоморфных схем.

[Pavlovsky]

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

Удивительно то, что для чётных N (6 и 8) имеется очень мало не изоморфных схем.

Для четных N все схемы близкие к оптимальной должны иметь вид: строк N/2, колонок N/2, прямых диагоналей N/2, обратных диагоналей N/2. Причем для диагоналей всего два вида: все диагонали черные, все диагонали белые. То есть в принципе нет разнообразия схем. И вообще можно сказать все они одинаковые.

-- Ср ноя 14, 2012 17:34:45 --

Все упирается в свойство. Для четных N две различные диагонали могут перескаться в двух точках. Что позволяет строить суперэффективные схемы. Посмотрите на таблицу рекордов. Любой рекорд (минимум) для четных N гораздо ближе к предыдущему нечетному числу, чем к последующему.

[whitefox]

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

Для четных N все схемы близкие к оптимальной должны иметь вид: строк N/2, колонок N/2, прямых диагоналей N/2, обратных диагоналей N/2. Причем для диагоналей всего два вида: все диагонали черные, все диагонали белые. То есть в принципе нет разнообразия схем. И вообще можно сказать все они одинаковые.

Вы чертовски правы.
Проверил все 6 схем для N=6 и все 39 схем для N=8, во всех случаях выполняется указанное Вами свойство.

[svb]

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

Интересный факт: во всех приведённых случаях каждой схеме со структурой $a_1,a_2,a_3,a_4,a_5$ соответствует схема со структурой $a_5,a_4,a_3,a_2,a_1$, либо сама структура симметрична.

Всего можно провести 4N линий, которым соответствует матрица пересечений из одних 4. Выбору 2N линий некоторой схемы соответствует дополнительная схема из 2N не выбранных линий. Сумма матриц пересечений этих двух схем равна матрице из 4.

[whitefox]

svb
Вы совершенно правы.
Также очевидно, что нижние и верхние оценки этих схем соответственно равны.

-- 14 ноя 2012, 20:05 --

То есть Вы уже доказали теорему, которую взялся доказывать Pavlovsky


-- 14 ноя 2012, 20:11 --

Поэтому приведённые мной количества не изоморфных схем нужно уменьшить примерно вдвое.

[Nataly-Mak]

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

Все равно мало. Скажем, для n=5, согласно Россеру должно быть еще одно преобразование.

А чем не годится преобразование "взятие дополнения"?

Цитата:

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

Интересный факт: во всех приведённых случаях каждой схеме со структурой $a_1,a_2,a_3,a_4,a_5$ соответствует схема со структурой $a_5,a_4,a_3,a_2,a_1$, либо сама структура симметрична.

А это похоже преобразование, не описанное Россером. Надо пожалуй потратить время и сделать из этой гипотезы теорему.

Так ведь Россер не рассматривал преобразование пандиагональных квадратов только по 2N линиям
Пандиагональный квадрат преобразовывается по всем 4N линиям.

К тому же, пандиагональный квадрат и квадрат, удовлетворяющий условиям конкурсной задачи, - это всё-таки разные в принципе квадраты. Как я уже отметила, преобразование "взятие дополнения" применимо к пандиагональным квадратам (то есть сохраняет пандиагональность квадрата), но не применимо к квадратам, удовлетворяющим условиям конкурсной задачи.

То, о чём пишет whitefox, и есть в некотором роде "взятие дополнения", только не для самого квадрата, а для соответствующей ему схемы из 2N линий.

[whitefox]

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

Теорема 3.4. Группа G имеет порядок 4n^2*Fi(n), если n четно и 8n^2*Fi(n) , если n
нечетно. Fi(n) это число целых чисел меньше чем n и взаимно простых с n .

Помимо уже указанных преобразований, Россер рассматривал ещё одно, а именно преобразование:

$$S_{\alpha}=\begin{Vmatrix} \alpha & 0 \\ 0 & \alpha \end{Vmatrix}\text{, где }(\alpha,n)=1$$

Иными словами квадрат $A$ преобразуется в квадрат $B$ по правилу: $B(i',j')=A(\alpha\cdot i,\alpha\cdot j)$ при $\alpha$ взаимнопростом с $n$.
Именно это преобразование и даёт функцию Эйлера $\varphi(n)$.
Очевидно, что при этом преобразовании линии переставляются, но их суммы сохраняются.

-- 14 ноя 2012, 21:16 --

С учётом этого преобразования, число не изоморфных схем станет ещё меньше.

[Nataly-Mak]

Тогда получается, что преобразование "взятие дополнения" Россер не рассматривал?
А почему же? Ведь оно переводит пандиагональный квадрат в пандиагональный.

Правда, не понятно, о преобразованиях каких пандиагональных квадратов идёт речь: классических или нетрадиционных.
Но в конкурсной задаче квадраты заполняются числами от 1 до n^2; значит, эти квадраты должны рассматриваться как классические, если проводить аналогию между ними и пандиагональными квадратами.

[whitefox]

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

Тогда получается, что преобразование "взятие дополнения" Россер не рассматривал?
А почему же? Ведь оно переводит пандиагональный квадрат в пандиагональный.

А сохраняется ли при этом магическое число?

Теоремы 3.3 и 3.4 Россера определяют группу автоморфизмов пандиагонального квадрата, а они магическое число сохраняют.

[Nataly-Mak]

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

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

Тогда получается, что преобразование "взятие дополнения" Россер не рассматривал?
А почему же? Ведь оно переводит пандиагональный квадрат в пандиагональный.

А сохраняется ли при этом магическое число?

Магическая константа сохраняется только в случае классических пандиагональных квадратов.
К нетрадиционным пандиагональным квадратам преобразование "взятие дополнения" тоже применимо (сохраняет пандиагональность), но не сохраняет магическую константу.

Цитата:

Теоремы 3.3 и 3.4 Россера определяют группу автоморфизмов пандиагонального квадрата, а они магическое число сохраняют.

Каких пандиагональных квадратов: классических или нетрадиционных?

[whitefox]

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

Каких пандиагональных квадратов: классических или нетрадиционных?

Нетрадиционных, так как по Россеру элементы квадрата могут принадлежать любому полю с характеристикой взаимно простой с $n$.
И больше никаких ограничений он не вводит (в частности нет ограничения, что элементы должны принадлежать множеству $1\dots n^2$ и не должны повторяться).

[svb]

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

$$S_{\alpha}=\begin{Vmatrix} \alpha & 0 \\ 0 & \alpha \end{Vmatrix}\text{, где }(\alpha,n)=1$$

Иными словами квадрат $A$ преобразуется в квадрат $B$ по правилу: $B(i',j')=A(\alpha\cdot i,\alpha\cdot j)$ при $\alpha$ взаимнопростом с $n$.

Прелесть!
Для нечетных N можно поменять диагонали с горизонталями/вертикалями с помощью $S = \left\| {\begin{array}{*{20}c} 1 & 1 \\ { - 1} & 1 \\ \end{array}} \right\|$

[Nataly-Mak]

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

Помимо уже указанных преобразований, Россер рассматривал ещё одно, а именно преобразование:

$$S_{\alpha}=\begin{Vmatrix} \alpha & 0 \\ 0 & \alpha \end{Vmatrix}\text{, где }(\alpha,n)=1$$

Иными словами квадрат $A$ преобразуется в квадрат $B$ по правилу: $B(i',j')=A(\alpha\cdot i,\alpha\cdot j)$ при $\alpha$ взаимнопростом с $n$.
Именно это преобразование и даёт функцию Эйлера $\varphi(n)$.
Очевидно, что при этом преобразовании линии переставляются, но их суммы сохраняются.

Не входит ли сюда замеченное мной давным-давно (ещё задолго до прочтения статьи Россера) преобразование пандиагональных квадратов нечётного порядка, названное "строки-диагонали"?



Очень красивое преобразование.
Преобразование описано в статье.
Статья из цикла статей "Преобразования магических квадратов".
Кстати, в этой же статье описано и преобразование "взятие дополнения" (глава 4).