Магические квадраты

[svb]

Несколько слов о невозможности квадрата 5858

Если рассмотреть квадрат с магической суммой 5858 по модулю 9, воспользовавшись методом 12d3, можно увидеть распределение остатков:
0 - 7 шт.
3 - 1 шт.
4 - 37 шт.
6 - 16 шт.
8 - 3 шт.
В каждом ряду суммы этих остатков могут принимать значения 8, 17, 26, 35, 44, 53 .. (=8 (mod 9)). Оценим максимальную сумму, она меньше 8+8+8+6+6+6+6+6=54, но не может быть =53. Сумма остатков=271, т.е. мы можем написать:
$8x+17y+26z+35u+44t=271$,
где x,y,z,u,t - количества рядов с соответствующими суммами, $x+y+z+u+t=8$, исключив $u$ можно переписать:
$3x+2y+(z-t)=1$
при этом $u+y=8-x-z-t=1$, т.к. 3 всего одна, т.е. $t=7-x-z$, или
$2x+y+z=4$
Итого, 3 решения:
$1. x=2, z=0, t=5$ примем y=0, u=1, другой вариант хуже
$2. x=1, z=2, t=4$
$3. x=0, z=4, t=3$
Но t не может быть больше 3, т.к. 8-ок всего 3, и при t=3 в каждую строку с суммой 44 может входить только одна 8 (и обязательно входит). С учетом этого максимальное число 4-ок в строках:
8 - 2 (0 0 0 0 0 0 4 4)
26 - 5 (0 0 4 4 4 4 4 6)
35 - 5 (3 4 4 4 4 4 6 6)
44 - 3 (4 4 4 6 6 6 6 8)
Для оставшегося решения максимальное число 4-ок:
3. 0*2+4*5+3*3+1*6=35
А у нас 37, т.е. решения нет.

Ниже приведены все возможные строки

0 0 0 0 0 0 0 8  ( 8)
0 0 0 0 0 0 4 4  ( 8)
0 0 0 0 0 3 6 8  (17)
0 0 0 0 3 4 4 6  (17)
0 0 0 4 4 4 6 8  (26)
0 0 0 4 4 6 6 6  (26)
0 0 3 4 4 8 8 8  (35)
0 0 3 4 6 6 8 8  (35)
0 0 3 6 6 6 6 8  (35)
0 0 4 4 4 4 4 6  (26)
0 3 4 4 4 4 8 8  (35)
0 3 4 4 4 6 6 8  (35)
0 3 4 4 6 6 6 6  (35)
0 4 4 6 6 8 8 8  (44)
0 4 6 6 6 6 8 8  (44)
0 6 6 6 6 6 6 8  (44)
3 4 4 4 4 4 4 8  (35)
3 4 4 4 4 4 6 6  (35)
4 4 4 4 4 8 8 8  (44)
4 4 4 4 6 6 8 8  (44)
4 4 4 6 6 6 6 8  (44)
4 4 6 6 6 6 6 6  (44)

[Nataly-Mak]

Итак, уважаемые коллеги, у нас остался один квадрат из последовательных смитов - 4-го порядка.

Я посоветовалась с ice00 в личной переписке, как нам приступить к решению этой задачи.

От ответил, что такие большие числа для него представляют сложность. Но если сделать ВСЕ потенциальные массивы в нормализованном виде (то есть вычесть из всех чисел массива минимальное число), тогда он сможет проверить такие потенциальные массивы на предмет составления их них магического квадрата, даже если таких массивов окажется очень много.

Это хорошая идея - сделать все потенциальные массивы в нормализованном виде.

Здесь уже был приведён maxal'ем ряд таких нормализованных потенциальных массивов, которые и я смогла проверить по своей программе (так как их было не очень много). Хорошая программа проверки есть и у svb (он мне её прислал).
Думаю, что и у 12d3 есть такая программа.

Какие будут предложения? Приступим?

[Pavlovsky]

А что обозначает абревиатура ПМК? Искать расшифровку на 92-х страницах обсуждения трудно.

[Nataly-Mak]

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

А что обозначает абревиатура ПМК?

ПМК - полумагический квадрат.

Отредактировала статью "Наименьшие магические квадраты из последовательных чисел Смита" и статью "Наименьшие магические квадраты из чисел Смита" (соответствующая последовательность в OEIS A170928).
Написала статью "Магические квадраты четвёртого порядка из последовательных простых чисел" (это о последовательности A173981 в OEIS).

Готовлю статью "Магические квадраты пятого порядка из последовательных простых чисел" и соответствующую последовательность в OEIS.

[Nataly-Mak]

Написала статью "Магические квадраты пятого порядка из последовательных простых чисел".

Интересное получается чередование массивов, складывающихся и не складывающихся в магические квадраты. Я проверила 50 потенциальных массивов, только 32 дали магические квадраты.
Последовательность магических констант этой группы квадратов получилась такая:

313, 577, 703, 785, 865, 949, 1111, 1703, 2041, 2071, 2579, 2677, 2809, 3157, 3379, 3545, 4001, 4135, 4873, 5143, 5513, 5549, 5659,  5695, 5731, 5917, 6031, 6277, 6427, 6547, 7951, 8027

Думаю, что последовательность можно продолжить.
Готовлю статью для OEIS о данной последовательности.

[Pavlovsky]

Пусть у нас есть последовательность из 16 чисел: $0\leq x_1<x_2<...<x_{16}$ .
Тогда из 16! перестановок этих чисел, только 14 перестановок (с точностью до изоморфизма) могут подходить для построения нетрадиционного пандиагонального магического квадрата 4х4.



В квадратах, на рисунке, это индексы переменных.

[Nataly-Mak]

Может быть, я что-то не так поняла.
Взяла один из имеющихся у меня нетрадиционных пандиагональных квадратов 4-го порядка:

7 22 16 25
20 21 11 18
19 10 28 13
24 17 15 14

Ему соответствует такой квадрат из индексов элементов массива:

1 13 7 15
11 12 3 9
10 2 16 4
14 8 6 5

Такого вроде нет в приведённом вами наборе.

___
Написала статью "Магические квадраты шестого порядка из последовательных простых чисел".

Интересно, что из 100 проверенных потенциальных массивов, следующих подряд, магические квадраты построились из чисел всех массивов.
Будет ли разрыв в этой последовательности?

[Pavlovsky]

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

Может быть, я что-то не так поняла.

1 13 7 15
11 12 3 9
10 2 16 4
14 8 6 5

Такого вроде нет в приведённом вами наборе.

этот квадрат изоморфен квадрату:

1 13 8 14
11 12 2 10
9 3 16 4
15 7 6 5

То есть если из конкретного набора удовлетворяющего условию: $0\leq x_1<x_2<...<x_{16}$ можно построить ваш пандиагональный квадрат , то второй квадрат будет тоже пандиагональным на этом наборе чисел. И наоборот.

[Nataly-Mak]

Да, получается.
Но тогда надо определить, что вы понимаете под изоморфизмом пандиагональных квадратов 4-го порядка.
Я посмотрела на эти два пандиагональных квадрата, они не являются изоморфными в смысле определения изоморфных (эквивалентных) магических квадратов.

[Pavlovsky]

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

7 22 16 25
20 21 11 18
19 10 28 13
24 17 15 14

7   20   18   25
22   21   11   16
17   10   28   15
24   19   13   14

Второй квадрат тоже пандиагональный

[Nataly-Mak]

Да это я вижу
Но эти два квадрата не изоморфны в смысле обычного определения изоморфности.

[Pavlovsky]

Пусть у нас есть произвольный набор чисел $0\leq x_1<x_2<...<x_{16}$ и две перестановки этих чисел A и B.
Определение. Перестановки A и B будем называть изоморфными если выполняется условие:
Для любого набора чисел удовлетворяющего условию $0\leq x_1<x_2<...<x_{16}$, перестановка A является пандиагональным квадратом <=> перестановка B является пандиагональным квадратом.

Мне казалось что такое определение изоморфизма естественно и интуитивно понятно.

Цитата:

они не являются изоморфными в смысле определения изоморфных (эквивалентных) магических квадратов

А какое определение используется для магических квадратов?

[Nataly-Mak]

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

Некоторые исследователи (как пишет М. Гарднер) считают изоморфными магические квадраты, получающиеся друг из друга М-преобразованиями. Однако классическое количество магических квадратов 4-го порядка, данное Френиклем, равно 880, а это значит, что Френикль не считал изоморфными квадраты, получающиеся друг из друга М-преобразованиями. В противном случае квадратов было бы не 880, а 220. Следуя этому классическому примеру, я тоже не считаю М-преобразования изоморфизмом.

Что касается пандиагональных магических квадратов, то здесь изоморфными считаются ещё квадраты, получающиеся друг из друга параллельным переносом на торе.
Например, пандиагональных квадратов 4-го порядка 48 (с учётом поворотов и отражений), а с учётом параллельного переноса на торе их всего 3; точнее 3 базовых квадрата, каждый из которых порождает группу эквивалентности из 16 квадратов относительно переноса на торе.

Если следовать вашему определению... Ну, скажем, нашли мы некий пандиагональный квадрат, который соответствует перестановке А. Как найти все изоморфные ему квадраты в смысле вашего определения?

[Nataly-Mak]

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

(Оффтоп)

1
7 20 21 22
24 19 10 17
14 13 28 15
25 18 11 16

2
7 20 21 22
25 18 11 16
14 13 28 15
24 19 10 17

3
7 20 19 24
22 21 10 17
16 11 28 15
25 18 13 14

4
7 20 19 24
25 18 13 14
16 11 28 15
22 21 10 17

5
7 20 18 25
22 21 11 16
17 10 28 15
24 19 13 14

6
7 20 18 25
24 19 13 14
17 10 28 15
22 21 11 16

7
7 22 21 20
24 17 10 19
14 15 28 13
25 16 11 18

8
7 22 21 20
25 16 11 18
14 15 28 13
24 17 10 19

9
7 22 17 24
20 21 10 19
18 11 28 13
25 16 15 14

10
7 22 17 24
25 16 15 14
18 11 28 13
20 21 10 19

11
7 22 16 25
20 21 11 18
19 10 28 13
24 17 15 14

12
7 22 16 25
24 17 15 14
19 10 28 13
20 21 11 18

13
7 24 19 20
22 17 10 21
16 15 28 11
25 14 13 18

14
7 24 19 20
25 14 13 18
16 15 28 11
22 17 10 21

15
7 24 17 22
20 19 10 21
18 13 28 11
25 14 15 16

16
7 24 17 22
25 14 15 16
18 13 28 11
20 19 10 21

17
7 24 14 25
20 19 13 18
21 10 28 11
22 17 15 16

18
7 24 14 25
22 17 15 16
21 10 28 11
20 19 13 18

19
7 25 18 20
22 16 11 21
17 15 28 10
24 14 13 19

20
7 25 18 20
24 14 13 19
17 15 28 10
22 16 11 21

21
7 25 16 22
20 18 11 21
19 13 28 10
24 14 15 17

22
7 25 16 22
24 14 15 17
19 13 28 10
20 18 11 21

23
7 25 14 24
20 18 13 19
21 11 28 10
22 16 15 17

24
7 25 14 24
22 16 15 17
21 11 28 10
20 18 13 19

Чтобы не занимали много места, спрятала их под тег оффтоп.

Вы можете получить по своим формулам такие же 24 квадрата?

-- Ср апр 21, 2010 13:22:48 --

Да, вспомнила...

Вопрос к svb:
вами получен наименьший магический квадрат 8-го порядка из произвольных смитов.
Надо бы внести этот результат в последовательность A170928.
Как вы смотрите на это?

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

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

[Pavlovsky]

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

Вы можете получить по своим формулам такие же 24 квадрата?

Где можно использовать опубликованные 14 перестановок? Скажем мы реашем задачу построения пандиагональных МК 4х4 из чисел специального вида. То есть у нас есть огромный файл с числами упорядоченными по возрастанию. И нам не нужно строить все МК, достаточно построить один.
Тогда алгоритм может быть примерно таким:
1) Формируем 16 чисел кандидатов.
2) Далее проверяем 14 перестановок, по общей формуле, можно ли из этих чисел построить пандиагональный МК.

В результате проверка на возможность построения пандиагонального квадрата 4х4 из 16 чисел-кандидатов становится тривиальной. Выполняется не минуты, секунды, а мгновенно.