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

[Nataly-Mak]

Пойду сначала выпью! Моя мама говорила так: "Без поллитра здесь не разберёшься"
Если разберусь, то напишу. Теперь подарок выглядит гораздо привлекательнее!

[Nataly-Mak]

Уф! Вроде одолела. Это второй квадрат в этой группе:

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

Метод построения латинских квадратов этой группы очень напоминает метод сотовых квадратов (для построения магических квадратов). Красивый метод!
А скажите-ка, пожалуйста, какой здесь будет четвёртый квадрат? Я попробовала добавить тривиальный квадрат по аналогии с квадратами 21-го порядка, но он, увы, не ортогонален построенным двум квадратам. Здесь, наверное, тоже надо как-то хитро “крутить”?
Третий квадрат теперь смогу построить. А вот про четвёртый пока не догадываюсь.

[tolstopuz]

Nataly-Mak писал(а):

Я попробовала добавить тривиальный квадрат по аналогии с квадратами 21-го порядка, но он, увы, не ортогонален построенным двум квадратам. Здесь, наверное, тоже надо как-то хитро “крутить”?

Видимо, да.

 0  1  2  3
 1  0  3  2
18 19  0  1
19 18  1  0

и т. д.

[Nataly-Mak]

Группу MOLS 20-го порядка по Wojtas полностью построила (см. статью “Ещё одна группа MOLS 20-го порядка”.
Теперь мои исследования пришли к такому этапу. В первой сотне порядков у меня остались всего три проблемных порядка. Проблемными я назвала такие порядки, для которых не могу пока построить даже пару ОЛК (подробнее в статье “Группы MOLS 26-го и 38-го порядка”). Это такие порядки: 62, 74 и 86. Для порядка 62 в книге “Handbook of Combinatorial Designs” приводится построение квази-разностной матрицы (см. пункт 3.74) из двух матриц $A_1$ и $A_2$. Однако не могу понять, как надо строить квази-разностную матрицу из приведённых матриц. Для порядков 74 и 86 в этой книге нет построений. Где можно найти построение групп MOLS для этих порядков? Известно, что $N(74) = 5$, $N(86) = 6$.
Ещё у меня имеется такой вопрос. Можно ли решить обратную задачу: по данной паре ОЛК составить квази-разностную матрицу? Вот, например, для своей пары ОЛК 18-го порядка (см. статью “Новые аспекты метода латинских квадратов (часть VI)” я составила такую квази-разностную матрицу:

1 1 2 10 12 5 8 3 7 6 11 4 a 9 b 13 c 2 d 6 e 1 8
1 2 1 12 10 8 5 7 3 11 6 a 4 b 9 c 13 d 2 e 6 8 1
1 13 a 8 b 2 c 12 d 1 e 8 6 1 13 3 6 4 10 7 3 7 2
1 a 13 b 8 c 2 d 12 e 1 6 8 13 1 6 3 10 4 3 7 2 7

(эти ортогональные латинские квадраты построены без всяких матриц по алгоритму, разработанному мной для порядков серии $n = 6k, k>1$).
Здесь $a, b, c, d, e$ – переменные, принимающие значения 14, 15, 16, 17, 18 в любой комбинации. Это правильная квази-разностная матрица? Каков критерий правильности такой матрицы? Ведь по приведённой матрице можно построить ту самую пару ОЛК, по которой составлена эта матрица. Однако матрицу можно составить в разных вариантах и этих вариантов будет очень много. Какой из этих вариантов будет правильный? Я надеюсь на успешное решение задачи о расширении данной группы ортогональных квадратов, состоящей пока из двух квадратов. И думаю, что это можно сделать по аналогии с рассмотренной здесь группой MOLS 18-го порядка, когда к квази-разностной матрице была добавлена одна строка, состоящая из переменных и единиц. Но это может, конечно, и не сработать. Однако интуиция мне говорит, что должно получиться. А для этого необходимо правильно составить квази-разностную матрицу по имеющейся паре ОЛК.
Вот такие пока проблемы. Есть и ещё несколько интересных вопросов, но не буду перегружать форум. Читайте статьи циклов “Группы ортогональных латинских квадратов” и “Новые аспекты метода латинских квадратов”.

[tolstopuz]

Nataly-Mak писал(а):

Для порядка 62 в книге “Handbook of Combinatorial Designs” приводится построение квази-разностной матрицы (см. пункт 3.74) из двух матриц $A_1$ и $A_2$. Однако не могу понять, как надо строить квази-разностную матрицу из приведённых матриц.

Столбцы первой матрицы берутся сначала как есть, а потом с минусом (то есть все ненулевые числа вычитаются из 54). Вместе со второй матрицей получается 10 столбцов, а после циклических перестановок - 70.

Nataly-Mak писал(а):

Ещё у меня имеется такой вопрос. Можно ли решить обратную задачу: по данной паре ОЛК составить квази-разностную матрицу?

Видимо, не всегда. Эти квадраты должны иметь довольно специальный вид - диагонали последовательных чисел. Но в вашем случае квадраты именно такие.

Nataly-Mak писал(а):

Это правильная квази-разностная матрица?

Похоже на правду.

Nataly-Mak писал(а):

Каков критерий правильности такой матрицы?

Для каждой пары строк разности элементов в каждом столбце по модулю 13 должны быть все разными. Столбцы, где в одной из проверяемых строк прочерк, естественно, пропускаются. Например, для строк 1 и 2 получаем

$$1-1=0, 1-2=12, 2-1=1, 10-12=11, 12-10=2, \ldots, 1-8=6, 8-1=7.$$

Точно так же проверяются строки 1-3, 1-4, 2-3, 2-4, 3-4. Если вы будете добавлять новую строку, надо будет проверить ее на совместимость с предыдущими.

Nataly-Mak писал(а):

Однако матрицу можно составить в разных вариантах и этих вариантов будет очень много. Какой из этих вариантов будет правильный?

Любой. Такие матрицы тоже можно назвать изоморфными.

Nataly-Mak писал(а):

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

Там было четыре столбца без прочерков, поэтому в новую строку как раз хорошо вписались четыре прочерка. У вас же три столбца, а прочерков пять.

Добавлено спустя 2 минуты 23 секунды:

http://www.emba.uvm.edu/~dinitz/preprin ... lvable.pdf
Здесь на стр. 23 есть порядок 74. Более того, в статье представлен общий метод получения пары квадратов любого порядка, кроме 2, 4, 6, 8. Да не простой пары, а с дополнительным условием - чтобы он не содержал латинских квадратиков 2x2, как четвертый квадрат порядка 20. Хотя для вас он, скорее всего, окажется слишком сложным, да еще и на английском.

Добавлено спустя 1 час 10 минут 37 секунд:

http://www.cems.uvm.edu/~dinitz/preprin ... .final.pdf
А это статья "Making the MOLS table", в которой есть вся теория и алгоритмы, использованные при построении таблицы с количеством квадратов.

[Nataly-Mak]

О-о-о! Это мне долго не переварить Спасибо, вот спасибо!!
По ссылкам ещё не ходила, вы напугали уже, что не разберусь. Так вы поможете?
В связи с общими алгоритмами у меня такой вопрос: там какие пары ОЛК строятся - диагональные или нет? Если недиагональные - мало интересу. Ведь доказано, что существуют пары диагональных ортогональных латинских квадратов всех порядков, кроме 2, 3 и 6. И где они? Большинство из тех групп MOLS, что мне удалось найти, содержат недиагональные латинские квадраты, которые в общем случае не пригодны для построения магичесих квадратов и их надо предварительно преобразовывать. Нужны пары ОЛК, состоящие из диагональных ЛК. При этом надо искать только для чётных порядков, потому что для нечётных порядков прекрасно работает метод Делаира. В статье Брауна, где приводятся три пары диагональных ОЛК 10-го порядка, вроде написано, что со всеми другими порядками всё уже решено, никаких проблем, только вот порядок 10 был самым упорным, но и для него автор нашёл такие пары ОЛК.
Сейчас удалось сочинить интересную пару ОЛК 12-го порядка, в ней второй латинский квадрат получается из первого перестановкой строк (см. http://www.natalimak1.narod.ru/mols12.htm ) (в статье Джонсона с компанией взяла одну картинку, совершенно не понимая, что в этой картинке хотела сказать компания, и построила по этой картинке пару ОЛК).
Аналогичную пару ОЛК 10-го порядка я нашла в Сети, автор пары Лямзин. Возникает вопрос: возможна ли аналогичная пара ОЛК для 14-го, 18-го и т. д. порядков (для порядков, являющихся степенью числа 2, все квадраты группы MOLS получаются друг их друга перестановкой строк).

[Nataly-Mak]

tolstopuz
Начинаю “переваривать” вашу информацию.
По одной из ваших ссылок нашла квази-разностную матрицу для построения пары ОЛК 62-го порядка, которая более понятная, чем в книге для группы MOLS данного порядка. А мне и не нужна группа, мне как раз нужна пара ОЛК. Видела там же и для пары порядка 74, но ещё не вникла.
По поводу моей задачи о добавлении к паре ОЛК 18-го порядка ещё одного (или двух) ортогональных квадратов. Я поняла так, что вы не дали заключение о полной невозможности решить эту задачу. Вы сказали только, что её невозможно решить аналогичным добавлением строки из переменных и единиц. Правильно? Но можно добавить какую-то другую строку для третьего (а может, и для четвёртого) квадрата, которая будет совместима по приведённому вами критерию с первыми тремя строками. Хорошая задача! Может быть, кто-нибудь возьмётся её решить? Ведь если удастся добавить два ортогональных квадрата, то будет улучшен имеющийся на сегодня результат для группы MOLS 18-го порядка. И даже если удастся добавить всего один квадрат, будет получена новая группа из трёх квадратов неизоморфная известной.
Ещё вы писали о том, что в одной из указанных вами статей приводятся общие алгоритмы построения пар ОЛК любого чётного порядка, кроме 2, 4, 6 и 8. Это очень интересно! Я глянула в эту статью, там такие заумные формулы, текст, конечно, нечитабелен и картинок совсем нет
А у меня остались без общего алгоритма только порядки серии $n = 2(mod 6)$. Да и отсюда надо выбросить все порядки, являющиеся степенью числа 2, а так же все порядки, для которых работает метод составных квадратов. И в результате проблемных порядков очень мало останется. Хотелось бы узнать общий алгоритм построения пар ОЛК именно данной серии порядков. Может быть, кто-нибудь сможет популярно изложить этот общий метод из приведённой статьи? Мне, конечно, там не разобраться.
А в общем, ещё раз огромное спасибо вам за всю информацию.

[tolstopuz]

Nataly-Mak писал(а):

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

Я тут еще чуть-чуть подумал и понял, что вообще никакую строку с пятью прочерками приписать нельзя. У вас осталось только три столбца без прочерков.

Nataly-Mak писал(а):

Может быть, кто-нибудь сможет популярно изложить этот общий метод из приведённой статьи?

Может быть, если найду на это пару дней. Но когда - пока не знаю.

Nataly-Mak писал(а):

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

А их всегда можно преобразовать?

[Nataly-Mak]

Не совсем пока поняла насчёт прочерков (то бишь переменных $a, b, c, d, e$). Почему нельзя три перменные вписать в столбцы, которые не содержат переменных, а две перменные вписть в те столбцы, в которых нет таких переменных? Какой-то нюанс я здесь не улавливаю
Насчёт преобразования латинских квадратов с помощью трансформации тождественной перестановки чисел. Я тут (см. выше) сформулировала эту задачу, чтобы доказать или опровергнуть мою гипотезу. Все построенные мной пары ОЛК, состоящие из недиагональных латинских квдаратов, мне удалось преобразовать элементарным подбором. Однако частные случаи не дают основания делать общий вывод.
maxal тут высказал предположение, что эта гипотеза в общем случае неверна. Моя же интуиция говорит обратное. Я уже приводила аргументы в пользу этой гипотезы (например, то, что Эйлер, являющийся основоположником метода латинских квадратов, не потребовал от латинских квадратов диагональности; более того, он тоже исследовал эту проблему на примерах квадратов 3х3, 4х4 и 5х5 и показал, что в диагоналях нужные суммы чисел достигаются простым переобозначением элементов). Однако примеров, опровергающих гипотезу, пока никто не привёл. Доказательства тоже нет.
Можно попробовать другой путь: из двух недиагональных ортогональных латинских квадратов строим греко-латинский квадрат (или же полумагический квадрат). Затем выполняем в этом греко-латинском квадрате перестановки строк и/или столбцов до тех пор, пока не получим нужных сумм в диагоналях. Частные примеры этого способа в моих статьях тоже приведены. Но надо доказать, что это будет работать для любого порядка.

[tolstopuz]

Nataly-Mak писал(а):

Не совсем пока поняла насчёт прочерков (то бишь переменных $a, b, c, d, e$). Почему нельзя три перменные вписать в столбцы, которые не содержат переменных, а две перменные вписть в те столбцы, в которых нет таких переменных?

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

[Nataly-Mak]

Ага! Вот теперь всё поняла. Таким образом, я могу добавить в свою матрицу строку только с тремя переменными (прочерками). Тогда у меня получится квадрат с подквадратом 3х3. Как вы думаете, может ли такой латинский квадрат быть ортогональным двум построенным мной латинским квадратам, содержащим подквадраты 5х5? Что-то я никак не соображу
Теперь по вопросу доказательства моей гипотезы. А нельзя ли доказать это утверждение методом математической индукции? Итак, мы имеем некоторую последовательность чисел из $n$ элементов, все числа последовательности принадлежат ряду натуральных чисел от 1 до n. Эта последовательность и есть набор чисел неправильной диагонали латинского квадрата, то есть диагонали, в которой сумма чисел не равна магической константе. Эйлер доказал утверждение для $n = 3, 4, 5$. Предположим, что утверждение верно для n – 1, то есть любую последовательность, состоящую из n – 1 элементов, принадлежащих ряду натуральных чисел от 1 до n - 1, мы можем превратить с помощью трансформации тождественной перестановки чисел в последовательность, сумма членов которой будет равна n(n – 1)/2. Докажем, что тогда утверждение верно и для $n$. Рассмотрим сначала случай, когда последний элемент последовательности, состоящей из $n$ элементов, есть элемент $n$, а среди остальных членов последовательности нет элемента $n$. Тогда очевидно, что утверждение выполняется. Это соответствует случаю, когда угловой элемент латинского квадрата есть элемент $n$, а среди остальных элементов диагонали нет элемента $n$. Если это не так, то, переставляя строки и/или столбцы квадрата и/или переобозначая элементы, мы можем получить именно такой вариант.
Скажите, пожалуйста, такое доказательство годится?

[tolstopuz]

Nataly-Mak писал(а):

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

Не получится. У вас только 13 столбцов, у которых в первых двух строках нет прочерков, и вы не заполните с их помощью все диагонали квадрата 15x15.

[Nataly-Mak]

Почему же не получится?
Вот, например, я добавила к своей матрице строку:
a 1 1 1 1 1 1 1 1 1 1 6 5 1 11 10 1 10 10 7 3 b c
и получила такой латинский квадрат с подквадратом 3х3:

a 1 7 12 14 11 8 c b 13 6 10 9 5 15 2 3 4
1 a 2 8 13 15 12 9 c b 14 7 11 10 6 3 4 5
7 2 a 3 9 14 1 13 10 c b 15 8 12 11 4 5 6
12 8 3 a 4 10 15 2 14 11 c b 1 9 13 5 6 7
14 13 9 4 a 5 11 1 3 15 12 c b 2 10 6 7 8
11 15 14 10 5 a 6 12 2 4 1 13 c b 3 7 8 9
4 12 1 15 11 6 a 7 13 3 5 2 14 c b 8 9 10
b 5 13 2 1 12 7 a 8 14 4 6 3 15 c 9 10 11
c b 6 14 3 2 13 8 a 9 15 5 7 4 1 10 11 12
2 c b 7 15 4 3 14 9 a 10 1 6 8 5 11 12 13
6 3 c b 8 1 5 4 15 10 a 11 2 7 9 12 13 14
10 7 4 c b 9 2 6 5 1 11 a 12 3 8 13 14 15
9 11 8 5 c b 10 3 7 6 2 12 a 13 4 14 15 1
5 10 12 9 6 c b 11 4 8 7 3 13 a 14 15 1 2
15 6 11 13 10 7 c b 12 5 9 8 4 14 a 1 2 3
3 4 5 6 7 8 9 10 11 12 13 14 15 1 2 a b c
8 9 10 11 12 13 14 15 1 2 3 4 5 6 7 b c a
13 14 15 1 2 3 4 5 6 7 8 9 10 11 12 c a b

По-моему вполне нормальный латинский квадрат. Разве нет?
Переменные $a, b, c$ принимают значения 16, 17, 18 в любой комбинации. Другое дело, что этот квадрат может быть не ортогонален первым двум (скорее всего, не ортогонален; это я ещё не проверила). Но зато, наверное, к этому квадрату можно сочинить второй соквадрат ортогональный ему. И тогда получится ещё одна новая пара ОЛК с подквадратами 3-го порядка.

[tolstopuz]

Nataly-Mak писал(а):

Почему же не получится?
Вот, например, я добавила к своей матрице строку:
a 1 1 1 1 1 1 1 1 1 1 6 5 1 11 10 1 10 10 7 3 b c
и получила такой латинский квадрат с подквадратом 3х3:

Во-первых, вы проигнорировали столбцы $(2, d, 4, 10, 10), (d, 2, 10, 4, 10), (6, e, 7, 3, 7), (e, 6, 3, 7, 3)$. Во-вторых, заполнили диагонали слева и справа от $c b$ не по матрице, а как попало. В третьих, при заполнении первых двух квадратов числа крутились по модулю $13$, а для последнего вы взяли модуль $15$, и получившаяся матрица не является квазиразностной ни по какому модулю.

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

[Nataly-Mak]

Ну, до таких нюансов я ещё не доросла Вот теперь постигаю и такие нюансы.
Однако получена новая квази-разностная матрица - раз! Два - к ней наверняка можно добавить четвёртую строку и получить второй ортогональный соквадрат (против этого не возражаете? сейчас попробую). Три - мы получим пару ОЛК (а может быть, и не получим, ещё бабушка надвое сказала; вы как думаете: получим или не получим? тут как раз та самая проблема, с которой я бьюсь с самого начала знакомства с методом латинских квадратов: построить ортогональных квадрат к заданному латинскому квадрату или доказать, что он не существует; хорошая задача!), содержащую подквадрат 3-го порядка, в то время как известные (по книге) пары ОЛК 18-го порядка содержат подквадрат 4-го порядка, а построенная мной раньше пара содержит подквадрат 5-го порядка. Понятно, что все эти пары ОЛК оригинальные (неизоморфные). Это правильная мысль? Может быть, это и не очень большое достижение, но я же на Нобелевскую премию не претендую
P.S. Вы не высказали своего мнения по поводу моего доказательства о преобразовании недиагонального латинского квадрата. Оно неправильное?
И никто не высказал.
maxal, я представила вариант доказательства утверждения, которое вы предположительно отвергли. Не вижу критики доказательства.

Добавлено спустя 2 часа 11 минут 17 секунд:

tolstopuz
Я исправилась в соответствии с вашим заключением. Составила новую квази-разностную матрицу из 3-х строк для одного квадрата и построила сам этот квадрат. Пожалуйста, скажите, стоит ли мне дальше напрягать извилины, чтобы добавить к этой матрице четвёртую строку и получить второй ортогональный соквадрат?
Спасибо вам за подробный разбор моих ошибок. Знаете, как приятно докапываться до самой сути.
Вот новая квази-разностная матрица:

1 1 8 1 2 10 12 5 8 3 7 6 15 11 a 9 b c 13 4 14
1 8 1 2 1 12 10 8 5 7 3 15 6 a 11 b 9 13 c 14 4
a b c 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

Латинский квадрат получается очень симметричный, аналогично третьему квадрату в группе MOLS из книги. Прямо обязан существовать для этого квадрата ортогональный соквадрат. Как вы думаете?