Антимагические квадраты

[Nataly-Mak]

Отделено от темы Магические квадраты.

Цитата:

Антимагические квадраты порядка n - это квадраты, содержащие n^2 натуральных чисел, так, что суммы чисел на всех горизонталях, вертикалях и двух главных диагоналях различны (в отличие от магических квадратов). В [1-3, см. список литературы ниже] введено понятие антимагических квадратов первого и второго рода. В [3] получены ответы на два первых принципиальных вопроса (можно сказать, локального характера) - о существовании антимагических квадратов первого и второго рода различных порядков и способе их построения. Сразу за ними встают два следующих принципиальных вопроса (по существу, глобальных) - 1) сколько существует антимагических квадратов каждого порядка n ; 2) найти алгоритм, позволяющий найти все такие квадраты. Одновременно встает множество вопросов, открывающих другие направления в этой проблеме [3].
Литература. Акулич И. Антимагические квадраты //Фокус, 1994, № 2.
Федоров И. Еще раз об антимагических квадратах //Фокус, 1995, № 3.
Ваннэ Ю. Антимагические квадраты.//«Репетитор»

(Взято по ссылке http://www.uni.bsu.by/arrangements/psem/pr2.html )

И чего только не придумают! Статью Ваннэ Ю. нашла в Интернете, но пока особо не вникла. Читается статья тяжело, глянула на неё мельком.
Не знаю, какие способы построения антимагических квадратов изобретены, но у меня для этого сгодилась программа генерации наборов из $n$ строк. Подкорректировала её немножко, и она выдаёт антимагические квадраты любого порядка; до порядка 10 попробовала, квадрат строится в долю секунды. Вот пример антимагического квадрата 10-го порядка:

53 95 46 2 79 10 49 85 86 47
6 44 1 58 74 62 14 52 21 60
20 24 91 19 43 69 41 42 35 87
8 50 40 65 67 92 18 26 29 88
25 83 32 4 75 66 3 15 80 22
71 68 31 45 36 99 48 28 77 7
13 38 16 11 55 97 30 12 84 64
89 94 72 98 33 81 23 39 82 59
73 100 93 76 54 5 78 57 9 70
17 27 34 37 51 56 61 63 90 96

При этом замечу, что я не вникала, какие там определили антимагические квадраты 1-го и 2-го рода; взяла самое простое определение антимагического квадрата, которое присутствует в приведённой цитате. В приведённом мной примере суммы чисел во всех строках, столбцах и в обеих главных диагоналях различны.

Ну и что сложного построить такой квадрат? Пойдём дальше: почему антимагический квадрат можно заполнять только натуральными числами от $1$ до n^2? Введём по аналогии с магическими квадратами нетрадиционные антимагические квадраты. И вот перед вами нетрадиционный антимагический квадрат 8-го порядка из последовательных смитов.

985  1755  1581  654  861  728  895  391 
 438  666  346  1255  355  762  663  627 
 1736  958  648  729  1776  1626  562  1449 
 1376  202  778  634  852  588  1086  636 
 94  1219  913  58  915  483  274  535 
 1642  121  378  1284  706  645  265  454 
 382  1633  166  85  1165  576  517  1111 
 319  526  690  825  922  1282  1507  1678

Квадрат построился мгновенно. А вот магический квадрат 8-го порядка из того же самого массива смитов я не могу построить уже третий день.
Вопрос: какой квадрат проще построить – магический или антимагический? Я утверждаю, что антимагический построить гораздо проще, чем магический. Если кто-то против этого утверждения, пусть построит магический квадрат 8-го порядка из приведённого массива последовательных смитов. Если, конечно, он вообще существует. У меня, например, создаётся ощущение, что такого квадрата не существует. Третий день гоняю свою программу генерации полумагических квадратов. При этом программа каждый полумагический квадрат пытается превратить в магический, для этого используется очень простенький приём: перестановка всех строк в полумагическом квадрате. Но даже этот простой способ рассматривает 40320 вариантов квадрата. Приличное количество вариантов! Так вот, уже сгенерировано 436 полумагических квадратов из 34 различных наборов строк. То есть проверено 436*40320 вариантов кандидатов в магический квадрат (из 436 полумагических). И ничего! В конце концов, прогнала все 436 полумагических квадратов через программу ice00 (pms_diag8_). Результат тот же самый: ни одного магического квадрата. Разумеется, всё это не даёт основания считать, что магический квадрат из данного массива смитов не существует. Но как же его найти?!

Второй вопрос: как вам нравится сама идея построения антимагических квадратов?
Мне антимагические квадраты кажутся некоторым извращением. В статье Ваннэ написано, что поскольку по магическим квадратам всё давно исследовано, надо придумать что-то новое (передаю смысл своими словами). И вот придумали!..

-- Вт дек 01, 2009 07:52:43 --

Интересную задачу нашла в книге Б. А. Кордемского “Математическая смекалка” (Государственное издательство технико-теоретической литературы, М.: 1957).
В книге написано, что в 1884 году, в “Журнале элементарной математики” профессором В. П. Ермаковым была опубликована формула, которую можно представить в виде суммы двух волшебных квадратов:

A C D B        0    a+b    –a-b    0
D B A C        c-d   –a-c   a-c   c+d
B D C A    +   -c+d  –a+c  a+c  –c-d
C A B D        0    a-b    –a+b    0

Произвольно подбирая 8 чисел $A, B, C, D, a, b, c, d$ и складывая оба квадрата поклеточно, мы получим искомый волшебный квадрат. По поводу того, как подобрать эти 8 чисел, чтобы в клетках полученного квадрата стояли все целые числа от 1 до 16 (то есть, чтобы квадрат оказался традиционным), В. П. Ермаков пишет: “Мы не знаем простого решения этого вопроса и предоставляем читателям найти таковое”.

Я попробовала решить эту задачку, но пока не удалось. Ясно, что числа $A, B, C, D$ должны быть среди первых 16 натуральных чисел и, кроме того, $A + B + C + D$ должно равняться 34. А вот какими будут числа $a, b, c, d$?

[Nataly-Mak]

В книге Р. Стенли “Перечислительная комбинаторика” (М.: Мир, 1990) нашла вот такое определение атимагического квадрата:



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

16 12 8 4 20 24 28 32
15 11 7 3 19 23 27 31
14 10 6 2 18 22 26 30
13 9 5 1 17 21 25 29
45 41 37 33 49 53 57 61
46 42 38 34 50 54 58 62
47 43 39 35 51 55 59 63
48 44 40 36 52 56 60 64

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

http://narod.ru/disk/15562048000/Perech ... a.rar.html

[Nataly-Mak]

ice00
Очень рада, что приведённые мной квадраты вам пригодились.

А я построила антимагические квадраты 3-го порядка (по определению Стенли) из простых чисел и из смитов. Кажется, это наименьшие квадраты.

3 11 17
5 13 19
23 31 37

Это квадрат индекса 53. Квадрата с меньшим индексом из простых чисел у меня не получается. Кстати, индекс этого квадрата тоже простое число.

А это наименьший (по моим расчётам) антимагический квадрат из смитов индекса 741:

4 85 265
121 202 382
274 355 535

В одном источнике нашла: индекс антимагического квадрата называют ещё весом, то есть говорят, например, так: антимагический квадрат 3-го порядка из смитов с весом 741.

[Nataly-Mak]

В одной своей давней статье об идеальных квадратах чётно-чётного порядка нашла квадрат 12-го порядка, названный мной псевдоидеальным. Тогда мне ещё не было известно определение антимагического квадрата (по Стенли). Оказывается, этот квадрат является антимагическим индекса 870. В нём суммы чисел по всем главным и разломанным диагоналям равны 870, а суммы в строках и в столбцах не равны этому значению. Кроме того, квадрат является ассоциативным. Я тогда пыталась построить идеальный квадрат 12-го порядка, а получила антимагический!

11 110 131 86 71 38 47 62 95 122 119 2
142 27 22 51 82 99 106 75 58 15 34 135
1 120 121 96 61 48 37 72 85 132 109 12
140 29 20 53 80 101 104 77 56 17 32 137
4 117 124 93 64 45 40 69 88 129 112 9
138 31 18 55 78 103 102 79 54 19 30 139
6 115 126 91 66 43 42 67 90 127 114 7
136 33 16 57 76 105 100 81 52 21 28 141
8 113 128 89 68 41 44 65 92 125 116 5
133 36 13 60 73 108 97 84 49 24 25 144
10 111 130 87 70 39 46 63 94 123 118 3
143 26 23 50 83 98 107 74 59 14 35 134

В статье есть примечание, что ранее мной был построен аналогичный квадрат 21-го порядка. Не стала его искать (статей у меня уже так много, что найти трудно).

[maxal]

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

В книге Р. Стенли “Перечислительная комбинаторика” (М.: Мир, 1990) нашла вот такое определение атимагического квадрата:



Как я понимаю, в антимагическом квадрате сумма чисел во всех диагоналях, как главных, так и разломанных, равна одному и тому же числу

Этого недостаточно для того, чтобы квадрат был антимагическим. Например, для антимагического квадрата 4x4 кроме диагоналей и разломанных диагоналей антимагической константе также должна равняться сумма элементов с координатами (1,1), (2,3), (3,2), (4,4) (не являющяся никакой диагональю) и тому подобные. Общее число таких сумм (включая всяческие диагонали) для квадрата $d\times d$ равно $d!$. Различных диагоналей же всего $2d$.

[Nataly-Mak]

Да, в самом деле, о таких комбинациях элементов я не подумала. Теперь всё окончательно понятно в этом определении.
Но для квадратов порядка 3 количество всех возможных комбинаций элементов антимагического квадрата совпадает с количеством всяческих дтагоналей: 3! = 2*3. Правильно?
Значит, антимагические квадраты 3-го порядка у меня правильные. А квадрат 12-го порядка надо проверить, вполне возможно, что кроме всяческих диагоналей все другие комбинации в нём не дают нужной суммы.

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

[Nataly-Mak]

Пока работают программы проверки...

Написала программку построения антимагического квадрата 3-го порядка.
Такой наименьший антимагический квадрат построился из простых чисел:

3 11 17
5 13 19
23 31 37

Сейчас попробую из чисел Смита построить антимагический квадрат 3-го порядка.

Такой наименьший антимагический квадрат 3-го порядка из чисел Смита у меня получился:

4 121 265
85 202 346
274 391 535

Квадраты 3-го порядка строятся мгновенно. С квадратами 4-го порядка посложнее будет, но ещё не писала программу для квадратов 4-го порядка.

Да, а интересно какой наименьший антимагический квадрат 3-го порядка из произвольных натуральных чисел?

Вот наименьший из произвольных натуральных чисел:

1 3 5
2 4 6
7 9 11

[Nataly-Mak]

Кажется, у меня всё неправильно...
Дело это новое для меня - антимагические квадраты, так что могу поначалу что-то не то делать.
Кто в курсе, подскажите, пожалуйста.

Вот написала такой квадрат 3-го порядка:

1 2 3
4 5 6
7 8 9

[Это самый простой обратимый квадрат (вспомнила про обратимые квадраты, когда задумалась, как построить антимагический квадрат 4-го порядка)].

Этот квадрат ведь антимагический? Или нет?
Данный квадрат составлен из чисел от 1 до 9, то есть (по аналогии с магическими квадратами) его можно назвать классическим.
Кстати, о терминологии. Постоянная сумма в антимагическом квадрате называется, кажется, его индексом (или весом). Так, приведён антимагический квадрат 3-го порядка с индексом 15.
Но в этом квадрате сумма чисел во второй строке и во втором столбце тоже равна 15. Это допустимо в антимагическом квадрате? Или же суммы чисел во всех строках и столбцах должны быть отличны от индекса?

Да, а ведь антимагический квадрат 2-го порядка тоже существует:

1 2
3 4

Чем не антимагический квадрат? Классический, с индексом 5. И тоже обратимый.

Интересно: если приведённый квадрат 3-го порядка с индексом 15 антимагический, почему у меня программа его не нашла? Где-то ошибка! Сейчас буду искать.
Программой найден антимагический квадрат 3-го порядка с индексом 16 (из произвольных натуральных чисел). Кстати, и в этом квадрате сумма чисел во втором столбце тоже равна 16. Допустимо ли это? Я ничего не вижу в определении антимагического квадрата относительно сумм в строках и столбцах, какие они должны быть: все различные или могут быть совпадающие, и могут ли совпадать с индексом.

Определение антимагического квадрата приведено на стр. 75.

[Nataly-Mak]

Посмотрела программу для построения антимагических квадратов 3-го порядка из произвольных натуральных чисел. Никакой ошибки нет, просто программа у меня работает до первого квадрата, а первым находится квадрат с диагональю (1, 4, 11), что соответствует индексу 16. Когда убрала остановку после первого найденного квадрата, квадрат с диагональю (1, 5, 9) тоже нашёлся. И дальше ещё море антимагических квадратов программа выдала.

Возможно, что и из простых чисел, и из чисел Смита выше приведены не наименьшие антимагические квадраты 3-го порядка, надо проверить.

По аналогии с магическими квадратами будем называть антимагический квадрат наименьшим, если он имеет минимальный индекс.
Вот классический антимагический квадрат 3-го порядка имеет индекс 15, понятно, что это наименьший антимагический квадрат, составленный из попарно различных натуральных чисел. С другой стороны, понятно, что это тривиальный антимагический квадрат. Ну, записали все числа по порядку и получили антимагический квадрат Что же тут строить.
А вот второй, приведённый мной, антимагический квадрат 3-го порядка имеет индекс 16, он уже не тривиальный, но и не классический, т.к. составлен не из чисел от 1 до 9.

Из простых чисел не нашла антимагический квадрат 3-го порядка с индексом S<53.
А вот из чисел Смита нашёлся квадрат с индексом 669:

22 58 202
85 121 265
346 382 526

Вроде этот наименьший.

Для сравнения: наименьший магический квадрат 3-го порядка из простых чисел имеет магическую константу 177 (см.A164843); наименьший магический квадрат 3-го порядка из чисел Cмита имеет магическую константу 822 (см. A170928).

[Pavlovsky]

Глянул Статью
Ваннэ Ю. Антимагические квадраты.

Забавно.

Цитата:

Определение. Полнодиагональным антимагическим квадратом первого рода n-го порядка (далее ПАК1(n)) назовем таблицу размером nn клеток, заполненную натуральными числами от 1 до n2 таким образом, что суммы чисел по всем вертикалям, горизонталям и по всем полным диагоналям попарно различны. Под полной диагональю следует понимать набор чисел квадрата, в который входят числа либо главной диагонали, либо двух параллельных и лежащих по разные ее стороны малых диагоналей с общим количеством элементов в них равным n.
В этом случае такой квадрат представляет собой своеобразный "квадрат на торе".
И с с л е д о в а н и е.
Очевидно, что общее количество сумм в МАК1(n) равно 6n-2, а в ПАК1(n) равно 4n. Так как МАК1(n) и ПАК1(n) одновременно являются ПрАК1(n), то при n < 3 МАК1(n) и ПАК1(n) не существуют. МАК1(3) существуют, например :

1 7 8
2 9 6
3 5 4

Несмотря на обширный поиск ПАК1(3) не был найден. Так как каждая сумма содержит три числа, то возможное количество различных сумм ограничено числом, равным (9+8+7) - (1+2+3) + 1 = 19, в то время как необходимое количество различных сумм равно 3 * 4 = 12. В некотором смысле есть еще запас.

Задача. Построить традиционный пандиагональный (полнодиагональный) антимагический квадрат 3х3.

[Nataly-Mak]

Ну, вот, теперь можно всё окинуть одним взглядом

И определение тут. И, как я давно писала, в книге, откуда взято определение, написано, что обратимый квадрат является антимагическим. Значит, это правильно я рассуждала здесь чуть выше.
Следовательно, построение антимагических квадратов порядка n, составленных из попарно различных натуральных чисел от 1 до n^2, не представляет особого интереса; обратимый квадрат и будет антимагическим.
Интересно строить нетрадиционные антимагические квадраты, например, из простых чисел и из чисел Смита.

Из простых чисел наименьший антимагический квадрат 2-го порядка у меня такой:

3 5
11 13

с индексом 16.
Из смитов такой:

4 85
121 202

с индексом 206.
Оба квадрата наименьшие.
Теперь подумаю над построением нетрадиционных антимагических квадратов 4-го порядка.

-- Вт май 22, 2012 10:27:02 --

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

[maxal]

Антимагические в англоязычной литературе называют гетероквадратами (heterosquare), в то время как antimagic square дополнительно требует, чтобы суммы были последовательными числами.

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

Задача. Построить пандиагональный (полнодиагональный) антимагический квадрат 3х3.

Про гетероквадраты 3x3 в википедии написано (хотя источник не указан):
It is strongly suspected that there are exactly 3120 essentially different heterosquares of order 3.


Понятно, что если найти все гетероквадраты 3x3, то будет понятно, есть ли среди них пандиагональные. Хотя, возможно, задача отыскания пандиагонального гетероквадрата (а точнее доказательства, что его нет) проще.

-- Tue May 22, 2012 02:08:47 --

maxal в сообщении #574510 писал(а):

Про гетероквадраты 3x3 в википедии написано (хотя источник не указан):
It is strongly suspected that there are exactly 3120 essentially different heterosquares of order 3.

Подробности - здесь: http://www.magic-squares.net/anti-ms.ht ... erosquares

[Nataly-Mak]

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

Задача. Построить традиционный пандиагональный (полнодиагональный) антимагический квадрат 3х3.

На скорую руку набросала программку. Тут перебором полным всё быстро вроде решается, перебор-то всего 9 чисел (если я правильно понимаю, квадрат нужен традиционный, то есть составленный из чисел от 1 до 9).
Если не наврала в программе (писала быстро, ничего не проверяла), то квадрата такого не существует, программа выполнила полный перебор и ничего не нашла.

[maxal]

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

Если не наврала в программе (писала быстро, ничего не проверяла), то квадрата такого не существует, программа выполнила полный перебор и ничего не нашла.

Хочется непереборное решение. Уж больно размерность маленькая.

[Nataly-Mak]

По указанной вами ссылке приведены все традиционные гетероквадраты 3-го порядка (12 штук). Пандиагонального среди них нет.

Сколько различных сумм дают все тройки чисел, составленные из набора чисел 1, 2, 3, ..., 9?
Надо, чтобы было не менее 12 попарно различных сумм.
Нет столько (как говорит программа полного перебора)