Дьявольские магические квадраты из простых чисел

[dimkadimon]

Интересная задача. Но боюсь что меньше 8 ненулевых ичеек для 4х4 нет. Вот мои лучшие результаты:

N=6, non-zero=16
(0,0,-1,2,4,1),
(0,4,2,0,0,0),
(0,0,2,0,2,2),
(2,0,1,0,0,3),
(0,0,2,4,0,0),
(4,2,0,0,0,0)

N=8, non-zero=14
(0,0,0,1,0,0,0,1),
(0,0,0,0,0,0,2,0),
(0,1,0,0,2,-1,0,0),
(0,1,0,0,0,1,0,0),
(2,0,0,0,0,0,0,0),
(0,0,0,1,0,2,0,-1),
(0,0,0,0,0,0,0,2),
(0,0,2,0,0,0,0,0)

N=9, non-zero=17
(0,0,3,0,0,0,0,0,0),
(0,0,0,0,3,0,0,0,0),
(0,0,0,-1,0,0,2,2,0),
(2,2,0,0,-1,0,0,0,0),
(0,0,0,3,0,0,0,0,0),
(0,0,0,0,0,3,0,0,0),
(0,1,0,1,0,0,0,1,0),
(0,0,0,0,0,0,0,0,3),
(1,0,0,0,1,0,1,0,0)

N=12, non-zero=41
(0,0,2,0,0,4,0,0,0,0,0,0),
(0,0,0,0,0,0,0,0,0,0,6,0),
(0,0,0,-4,0,-2,2,6,0,4,0,0),
(0,8,0,0,4,0,-4,0,0,0,-2,0),
(0,-6,0,0,4,6,2,0,0,0,0,0),
(6,0,8,0,0,-4,0,0,0,0,0,-4),
(0,0,-3,0,-2,0,0,0,5,6,0,0),
(0,4,-2,4,0,0,0,0,0,-4,0,4),
(0,0,0,0,0,3,0,0,0,0,2,1),
(0,0,-4,6,0,-1,0,0,6,0,0,-1),
(0,0,0,0,0,0,6,0,0,0,0,0),
(0,0,5,0,0,0,0,0,-5,0,0,6)


Для N=10 нашёл хорошее решения с 12 ненулевыми ячейками, решил пока не показывать ;)

[Nataly-Mak]

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

Интересная задача. Но боюсь что меньше 8 ненулевых ичеек для 4х4 нет.

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

0 1 -1 0
-1 0 0 1
1 0 0 -1
0 -1 1 0

всё равно 8 ненулевых элементов.
[это из статьи svb]

-- Пт авг 09, 2013 13:40:29 --

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

Вот мои лучшие результаты:

N=6, non-zero=16
(0,0,-1,2,4,1),
(0,4,2,0,0,0),
(0,0,2,0,2,2),
(2,0,1,0,0,3),
(0,0,2,4,0,0),
(4,2,0,0,0,0)

Для N=6 вроде должно быть решение лучше.
В статье svb есть такой пример с нулевой магической константой:

0 0 0 0 0 0 
0 0 0 0 0 0
0 0 0 0 0 0
1 -1 1 -1 1 -1
0 0 0 0 0 0
-1 1 -1 1 -1 1

Здесь 12 ненулевых элементов.
Кто найдёт такой же пандиагональный квадрат (с 12 ненулевыми элементами), но не с нулевой магической константой, тому пирожок

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

[svb]

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

Законы линейной алгебры не обманешь. Количество пандиагональных квадратов составляющих базис пространства пандиагональных квадратов должно равняться количеству независимых переменных при выводе общей формулы. Хотелось бы увидеть, в явном виде, скажем для N=7, 25 базисных квадратов. Очень хороший базис это когда квадраты его составляюще имеют минимальное количество ненулевых ячеек.

Прежде всего о квадратах с ненулевой суммой. Просто добавляем еще один элемент базиса - квадрат, в каждой клетке которого стоит единица. Этот элемент ортогонален векторам обобщенного базиса, т.е. линейно от них не зависим.

В статье доказано, что оболочкой обобщенного базиса является все пространство пандиагональных квадратов. Из обобщенного базиса достаточно выкинуть линейно зависимые вектора, чтобы получить обычный базис. Для нечетных $N$ это сделать совсем просто, для четных $N$ почти также просто, или можно добавить специальный квадрат из 3 строчек (см.статью), который также выражается через элементы обобщенного базиса. В статье есть пример подобного представления для $N=6$ и $N=8$.

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

[Nataly-Mak]

У меня море квадратов получается с 28 ненулевыми элементами, но я по программе для совершенных квадратов строю.
Например,

 1  1  0  3 -1  2 
 0  2  1  0  2  1 
 3 -1  2  1  1  0 
-1  3  0  1  1  2 
 2  0  1  2  0  1 
 1  1  2 -1  3  0 
S=6

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

-- Пт авг 09, 2013 14:18:40 --

svb
вы можете показать конкретный базис для пространства классических пандиагональных квадратов 4-го порядка? Не такой, какой показала я.

Я полагаю, что в этом базисе должно быть всего 3 базисных квадрата.

[Pavlovsky]

Возьмем ранее расмотренный квадрат 5х5

1,0,0,0,0
0,0,0,1,0
0,1,0,0,0
0,0,0,1,0
0,0,1,0,0

Если к ячейкам помеченным 1 добавить/вычесть константу получится снова пандиагональный квадрат.
Это можно записать так:
C=A+k*B, где A некий пандиагональный квадрат, который мы хотим изменить, B это квадрат представленный выше.

Но в качестве квадрата B можно взять любой пандиагональный квадрат.
Например:

0 1 -1 0
-1 0 0 1
1 0 0 -1
0 -1 1 0

В этом случае мы получим пандиагональный квадрат С, но магическая сумма у него будет такая же как у квадрата A. Спрашивается зачем тогда преобразовывали? Отсюда и требование чтобы магическая константа базисных квадратов была ненулевой. Мы ведь хотим получить квадрат с меньшей магической суммой.

[svb]

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

svb
вы можете показать конкретный базис для пространства классических пандиагональных квадратов 4-го порядка? Не такой, какой показала я.

Я полагаю, что в этом базисе должно быть всего 3 базисных квадрата.

У меня остался недописанный кусок статьи. Там кое-что есть любопытное.

[Nataly-Mak]

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

[svb]

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

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

Кусочек то маленький. Пространство $D$ - 4 квадрата и еще один нужно добавить из единичек, т.е. общая размерность $5=1+(N-2)^2$

[Nataly-Mak]

Спасибо за непоказ базиса.

По-моему, для классических пандиагональных квадратов 4-го порядка всего 3 базисных пандиагональных квадрата (я их показала выше). И потому размерность пространства классических пандиагональных квадратов 4-го порядка равна 3.

Это не противоречит и общей формуле таких квадратов.

[svb]

1,-1,1,-1
-1,1,-1,1
-1,1,-1,1
1,-1,1,-1

1,-1,-1,1
-1,1,1,-1
1,-1,-1,1
-1,1,1,-1

1,1,-1,-1
-1,-1,1,1
1,1,-1,-1
-1,-1,1,1

1,-1,1,-1
1,-1,1,-1
-1,1,-1,1
-1,1,-1,1

1,1,1,1
1,1,1,1
1,1,1,1
1,1,1,1

[Pavlovsky]

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

Прежде всего о квадратах с ненулевой суммой. Просто добавляем еще один элемент базиса - квадрат, в каждой клетке которого стоит единица.

Можно ведь добавить любой квадрат с ненулевой магической суммой? Ведь любой квадрат с ненулевой магической суммой очевидно независим от квадратов с нулевой суммой.

[svb]

Конечно, но зачем красоту нарушать?

-- Пт авг 09, 2013 14:21:41 --

Кстати, приведенный базис ортогональный.

[Pavlovsky]

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

А может, и с нулевой магической константой квадраты годятся?

В принципе и они годятся. Скажем у нас есть квадрат, где несколько чисел не являются простыми. Тогда можно крутить эти ячейки пока не получим в них простые числа. При этом магическая сумма исходного квадрата не изменяется.
Например можно попытаться заткнуть дырку в этом квадрате.

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

113 67 443 439 31 149 191
379 101 89 281 43 317 223
211 293 97 163 449 41 179
233 389 131 109 461 73 37
359 241 13 107 173 479 61
47 263 409 311 139 181 83
91 79 251 23 137 193 659

[Nataly-Mak]

Этой предложенный мной базис пространства классических пандиагональных квадратов 4-го порядка:

0 1 2 3
3 2 1 0
1 0 3 2
2 3 0 1

0 1 2 3
2 3 0 1
3 2 1 0
1 0 3 2

0 1 2 3
1 0 3 2
2 3 0 1
3 2 1 0

Это не что иное как три попарно ортогональных латинских квадрата (полная группа для порядка 4).

-- Пт авг 09, 2013 15:24:38 --

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

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

А может, и с нулевой магической константой квадраты годятся?

В принципе и они годятся. Скажем у нас есть квадрат, где несколько чисел не являются простыми. Тогда можно крутить эти ячейки пока не получим в них простые числа. При этом магическая сумма исходного квадрата не изменяется.
Например можно попытаться заткнуть дырку в этом квадрате.

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

113 67 443 439 31 149 191
379 101 89 281 43 317 223
211 293 97 163 449 41 179
233 389 131 109 461 73 37
359 241 13 107 173 479 61
47 263 409 311 139 181 83
91 79 251 23 137 193 659

А, вот это уже веселее

[Pavlovsky]

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

Конечно, но зачем красоту нарушать?

Пока одни думают о красоте, другие в поте лица сотые балла зарабатывают. Я уже писал, мне нужен базис, в котором квадраты имеют минимальное количество ненулевых ячеек. Ваш очень красивый базис для квадрата порядка 4 вообще не имеет нулевых элементов!