Латинские квадраты

[Nataly-Mak]

Спасибо, что потрудились над задачей. Однако ответ не совсем хорош. Виновата, что не поставила ещё одно очень важное условие в задаче, но я думала, что оно само собой выполнится
Поскольку латинский квадрат нужен мне для построения магического квадрата, то необходимо, чтобы латинский квадрат являлся нетрадиционным магическим квадратом с магической константой 36. В построенном вами квадрате это условие не выполняется, магической константы нет в двух столбцах.
Я уже перебрала множество вариантов, но решение так и не нашла. Может быть, оно и не существует? Хотела написать программу для решения задачи, но очень много неизвестных, программа получится "долгоиграющая".
В статье “Концентрические магические квадраты” вы можете посмотреть на тот магический квадрат (заполненный тоже наполовину), который мог бы быть построен из данного латинского квадрата (с добавлением второго ортогонального латинского квадрата). Использование латинского квадрата помогло мне заполнить квадрат наполовину.
Может быть, я неправильно заполнила вписанные квадраты 3х3 и 5х5. В заполнении окаймления уверена.

[Nataly-Mak]

Составила программу для заполнения второй и восьмой строк латинского квадрата. Эта программа выдаёт очень много вариантов заполнения. Затем написала вторую программу – заполнения второго и восьмого столбца квадрата. Но входные данные в эту программу ввожу вручную. Понятно, что так много вариантов не проверишь. А если написать программу для всех переменных сразу, то не дождёшься, когда она выполнится.
Неужели задача не имеет решения?
Источником задачи послужили очень интересные концентрические магические квадраты на иллюстрации из какого-то старого журнала, которая была опубликована в разделе
http://dxdy.ru/topic12959.html
Пытаюсь проникнуть в алгоритм построения таких магических квадратов. По сути дела мы имеем вариант метода окаймлённых квадратов. Мне удалось построить похожие концентрические магические квадраты, заключённые в магическом квадрате 7-ого порядка. А вот с концентрическими магическими квадратами, заключёнными в магическом квадрате 9-ого порядка, ничего не получается.
Для того чтобы задачу было проще решать, я разложила магический квадрат 13-ого порядка на два латинских квадрата. Вот первый латинский квадрат, соответствующий магическому квадрату 13-ого порядка с иллюстрации:

7  8  9  10  11  12  0  1  2  3  4  5  6
8  9  2  12  11  0  12  1  0  3  12  5  4
9  0  6  11  2  10  2  10  1  6  5  12  3
10  7  8  2  10  4  9  4  9  4  4  5  2
11  2  1  9  4  7  6  7  5  3  11  10  1
12  12  11  9  8  5  7  6  4  3  1  0  0
0  0  2  3  6  7  6  5  6  9  10  12  12
1  12  11  8  4  6  5  7  8  4  1  0  11
2  1  1  3  7  5  6  5  8  9  11  11  10
3  9  8  8  2  8  3  8  3  10  4  3  9
4  7  7  1  10  2  10  2  11  6  6  5  8
5  7  10  0  1  12  0  11  12  9  0  3  7
6  4  3  2  1  0  12  11  10  9  8  7  5

Maxal, может быть, в журнале есть какие-нибудь объяснения к иллюстрации с концентрическими магическими квадратами, которую вы опубликовали? Подскажите, пожалуйста

[Nataly-Mak]

Извините, что не по теме
Это не латинские квадраты. Я назвала их сотовыми, и метод, в котором они используются, тоже назвала методом сотовых квадратов. Метод я нашла в книге Чебракова. Однако способ построения сотового квадрата любого порядка n=4k+2, k=1, 2, 3… понять не могу.
Сотовый квадрат составляется из квадратов 2х2, в которых записываются числа 0, 1, 2, 3 в произвольном порядке. Понятно, что всего таких квадратов будет 24. Вот пример сотового квадрата 6-ого порядка:

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

При этом сотовый квадрат является вспомогательным для построения магического квадрата (вторым вспомогательным, первый вспомогательный квадрат строится просто методом террас), поэтому он должен быть нетрадиционным магическим квадратом.
Задача состоит в том, чтобы найти чёткий алгоритм составления такого сотового квадрата для любого порядка n=4k+2, хотя бы одного!
В книге Чебраков приводит примеры составления сотового квадрата для порядков n=6, 10, 14. Но как именно их составлять, непонятно. И потому уже сотовый квадрат 18-ого порядка я составить не могу.

[maxal]

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

Сотовый квадрат составляется из квадратов 2х2, в которых записываются числа 0, 1, 2, 3 в произвольном порядке. Понятно, что всего таких квадратов будет 24.

Для данной задачи число квадратиков 2x2 можно сократить до 16, учитывая, что квадратики
$\begin{bmatrix} 3 & 0\\ 1 & 2\end{bmatrix}$ и $\begin{bmatrix} 1 & 2\\ 3 & 0\end{bmatrix}$
и другие подобные пары взаимозаменяемы.

Добавлено спустя 25 минут 39 секунд:

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

Вот пример сотового квадрата 6-ого порядка:

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

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

Квадрат 18x18 получается из 9 копий вышеприведенного квадрата 6x6, размещая их в виде квадрата 3x3 (где каждая клетка - это копия квадрата 6x6).

[Nataly-Mak]

Ну, как составить сотовый квадрат 18-ого порядка, сообразить нетрудно Я тоже это сообразила, как только вслед за методом сотовых квадратов описала метод составных квадратов. А как быть с квадратом 22-ого порядка и с квадратом 26-ого порядка? И вообще с любым порядком n=4k+2. Для того чтобы метод можно было считать до конца разработанным, надо дать способ составления хотя бы одного квадрата для любого порядка данной серии порядков. Иначе это не общий метод получается, а просто несколько частных примеров для порядков n=6, 10, 14, 18.
Сколько разных квадратов 2х2 использовать при составлении сотового квадрата, не имеет значения.

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

По поводу взаимозаменяемости некоторых квадратов 2х2. Нет, нельзя отбросить взаимозаменяемые квадраты. Чебраков использует все 24 квадрата. И правильно делает!
В статье я показала построение двух магических квадратов 6-ого порядка с использованием двух сотовых квадратов, в которых как раз имеется пара взаимозаменяемых блоков 2х2. В результате получились магические квадраты, которые отличаются друг от друга этим самым блоком из четырёх чисел. Эти магические квадраты связаны преобразованием “плюс-минус 2”. Однако, насколько мне известно, данное преобразование не относится к числу эквивалентных преобразований магических квадратов. И поэтому с точки зрения науки о магических квадратах эти два магических квадрата считаются различными (не эквивалентными).
Чебраков подсчитал, что методом сотовых квадратов можно построить 95232 магических квадрата 6-ого порядка с учётом поворотов и отражений. Без учёта поворотов и отражений их будет11904. Среди этих магических квадратов будет много связанных друг с другом преобразованием типа “плюс-минус…”. Это как раз те квадраты, которые построены с использованием сотовых квадратов, содержащих взаимозаменяемые блоки 2х2.

[maxal]

Возвращаясь к вопросу о построении ортогональных латинских квадратов - это умеет делать команда MOLS из GAP'овского пакета GUAVA. Причем не только пару, но и вообще заданное количество попарно ортогональных латинских квадратов (если они существуют).

[maxal]

Sonic86 писал(а):

Можно вопрос? Для данного латинского квадрата сколько существует ортогональных?

Зависит от самого квадрата. Для некоторых квадратов вообще не существует ортогональных - см. теорему 13.2.3 на стр. 267 в книге Холла (ссылка выше) или раздел I.2.3 в этих лекциях.

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

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

А как быть с квадратом 22-ого порядка и с квадратом 26-ого порядка? И вообще с любым порядком n=4k+2.

Во-первых, понятно, что квадраты порядка $4k$ существуют и легко строятся, например, расположением двух квадратиков 2x2:
$\begin{bmatrix} 3 & 0\\ 1 & 2\end{bmatrix}$ и $\begin{bmatrix} 0 & 3\\ 2 & 1\end{bmatrix}$
в шахматном порядке.

Квадрат 22 порядка строится так из квадратов 16 и 6 порядков так:
$\begin{matrix} K_{16} & X\\ X^T & K_6\end{matrix}$
где прямоугольник $X$ размером 16x6, заполняется в шахматном порядке теми же квадратиками 2x2, что и выше; а прямоугольник $X^T$ размером 6x16 является транспонированием $X$.

Квадрат 26 порядка аналогично строится из квадратов 20 и 6 порядков:
$\begin{matrix} K_{20} & Y\\ Y^T & K_6\end{matrix}$
где $Y$ - это прямоугольник 20x6, заполняемый теми же квадратиками 2x2 в шахматном порядке, а $Y^T$ - его транспонирование.

Понятно, что указанные конструкции легко обобщаются до любых квадратов порядка $4k+2.$

[Nataly-Mak]

Maxal, у меня ваш метод почему-то не работает.
Начала построение с квадрата 8-ого порядка по вашей инструкции. Вот какой квадрат получился:

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

Я правильно поняла, как надо расположить квадратики? Может, как-то по-другому?
В строках и столбцах всё хорошо, а в главных диагоналях магической константы нет.
Тогда я заменила четыре блока и получила полностью магический сотовый квадрат (конечно, нетрадиционный):

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

Попыталась я и сверстать квадрат 14х14 по вашей конструкции. Тоже пока не получилось. Какие-то блоки надо заменять. Получается опять же простой подбор. Но чем больше порядок квадрата, тем подбор становится труднее. А вы сами построили хотя бы один сотовый квадрат порядка n=4k+2 своим методом?

[maxal]

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

Maxal, у меня ваш метод почему-то не работает.
Начала построение с квадрата 8-ого порядка по вашей инструкции. Вот какой квадрат получился:

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

Я правильно поняла, как надо расположить квадратики? Может, как-то по-другому?
В строках и столбцах всё хорошо, а в главных диагоналях магической константы нет.

Я не учитывал необходимость равенства сумм диагоналей магической константе. По сути предыдущее решение давало квадраты, в которых равны только все суммы по строкам и столбцам.

На самом деле квадрат порядка $4k$ строится просто повторением следующего квадрата 4x4:

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

Например, квадрат 8x8 - это:

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

Теперь квадрат порядка $4k+2$ будет строить из квадрата порядка 6, который мы разместим в центре, и 4-х четвертей квадрата порядка $4(k-1)$ по углам. Например, для квадрата 14x14 сначала получаем такую конструкцию:

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

А далее верхний и нижний прямоугольники 4x6 замостим как и раньше квадратиками 2x2 в шахматном порядке, а верхние и нижние прямоугольники - их транспозициями

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

Этот метод легко обобщается до построения квадратов порядка $4k+2$ для нечетных $k$ (пример выше - для $k=3$). Для четных $k$ додумайте сами по аналогии.

[Nataly-Mak]

Вот теперь другое дело! Додумала для квадратов 10-ого и 18-ого порядка. Вот они:

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

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

Теперь метод сотовых квадратов можно считать завершённым. Благодаря вам, Maxal.

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

Возвращаюсь к латинским квадратам. Maxal, вы тут дали ссылку на какую-то программу, которая умеет строить ортогональные латинские квадраты. Пошла по этой ссылке, но ничего там не поняла
Не могли бы вы привести конкретный метод построения ортогонального квадрата, например, к такому латинскому квадрату:

8  3  7  2  6  1  5  0  4
3  7  2  6  1  5  0  4  8
7  2  6  1  5  0  4  8  3
2  6  1  5  0  4  8  3  7
6  1  5  0  4  8  3  7  2
1  5  0  4  8  3  7  2  6
5  0  4  8  3  7  2  6  1
0  4  8  3  7  2  6  1  5
4  8  3  7  2  6  1  5  0

Один ортогональный квадрат получается просто отражением этого квадрата относительно горизонтальной оси симметрии, но этот квадрат мне не годится в конкретном построении магического квадрата. Другой я получила, разложив исходный магический квадрат на два латинских квадрата. Но если мне этот исходный магический квадрат неизвестен, тогда как быть? Сколько ортогональных латинских квадратов существует для данного латинского квадрата? Мне интересно знать все.
Далее, точно так же можно составить первый латинский квадрат для построения магического квадрата любого нечётного порядка. И к каждому первому латинскому надо построить ортогональный. Это будет представление метода альфила через использование двух ортогональных латинских квадратов. Поскольку метод построения второго латинского квадрата в данном случае я не знаю, то представила метод альфила через метод качелей.

[maxal]

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

Возвращаюсь к латинским квадратам. Maxal, вы тут дали ссылку на какую-то программу, которая умеет строить ортогональные латинские квадраты. Пошла по этой ссылке, но ничего там не поняла
Не могли бы вы привести конкретный метод построения ортогонального квадрата, например, к такому латинскому квадрату:

8  3  7  2  6  1  5  0  4
3  7  2  6  1  5  0  4  8
7  2  6  1  5  0  4  8  3
2  6  1  5  0  4  8  3  7
6  1  5  0  4  8  3  7  2
1  5  0  4  8  3  7  2  6
5  0  4  8  3  7  2  6  1
0  4  8  3  7  2  6  1  5
4  8  3  7  2  6  1  5  0

Это другая задача. Пакет GUAVA строит пару (тройки и т.д.) ортогональных квадратов заданной размерности, сам выбирая оба эти квадрата. Вы же хотите построить ортогональный квадрат к заданному - этого GUAVA делать не умеет, как я понял.
Навскидку для второй задачи нашлась такая программка на Прологе, но какова она на практике сказать затрудняюсь, да и с Прологом я не особо знаком.

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

Сколько ортогональных латинских квадратов существует для данного латинского квадрата? Мне интересно знать все.

Найдя один, можно указать как минимум $n!$ различных квадратов ортогональных к данному, всего лишь подставляя вместо чисел $1, 2, 3,\dots, n$ в найденном квадрате различные перестановки этих же чисел.

[Nataly-Mak]

Ага! Так ведь это точно так же, как уже было показано в методе Делаира. Только не n!, а (n-1)!, и ничего находить не надо, просто составлять второй квадрат, записывая в первой строке любую перестановку чисел от 0 до 8, но в первой ячейке обязательно должно стоять число 4, иначе не получится ортогональный квадрат. А каждая следующая строка получается циклическим сдвигом (последнее число переносится в начало). Таким образом, можно составить 8! ортогональных квадратов к тому, который приведён выше. Но как составить сразу тот единственный, который вместе с первым даст магический квадрат, построенный методом альфила. Вот в чём задача. Не проверять же все 8! ортогональных квадратов.
Но, кажется, вижу закономерность составления этого ортогонального квадрата (после того, как очень долго смотрела на него ) Покажу здесь этот самый единственный, который мне и нужен:

4  2  0  7  5  3  1  8  6
6  4  2  0  7  5  3  1  8
8  6  4  2  0  7  5  3  1
1  8  6  4  2  0  7  5  3
3  1  8  6  4  2  0  7  5
5  3  1  8  6  4  2  0  7
7  5  3  1  8  6  4  2  0
0  7  5  3  1  8  6  4  2
2  0  7  5  3  1  8  6  4

Как уже сказано, он получен просто разложением известного магического квадрата на два латинских ортогональных квадрата.
С ортогональными квадратами, которые строятся таким способом, всё ясно. Меня интересует вопрос: есть ли ортогональные квадраты к данному квадрату, которые строятся иначе.

[Nataly-Mak]

А можно здесь задачку из области квадратов? Очень интересно, имеет ли задача решение. Если имеет, то удастся построить идеальный сотовый традиционный магический квадрат! Такого ещё нет пока, насколько мне известно.
Надо составить квадрат 8х8 из квадратиков 2х2, которые заполняются числами 0, 1, 2, 3. Получившийся квадрат 8-ого порядка должен быть нетрадиционным магическим квадратом с магической константой 12 (то есть сумма чисел в каждой строке, каждом столбце и в обеих диагоналях этого квадрата равна 12).Кроме того, он должен быть ассоциативным, то есть сумма любых двух чисел, расположенных симметрично центра квадрата, равна одному и тому же числу – 3. И в довершение всего он должен быть пандиагональным, то есть сумма чисел в каждой разломанной диагонали квадрата тоже должна равняться 12 (разломанная диагональ – это диагональ, параллельная главной и проходящая тоже через 8 ячеек квадрата). Я начала решать задачу с заполнения части квадрата, а в пустые ячейки записала неизвестные величины. Затем записала условия магичности и пандиагональности квадрата и получила систему из 16 линейных уравнений с 16 неизвестными. К сожалению, не имею ни одного пакета программ, чтобы решить эту систему уравнений. В этом и прошу помочь. Если я не ошиблась при составлении уравнений (что легко проверить), то ответ должен быть однозначным: есть решение или нет его. Не забудьте, что все неизвестные могут принимать только четыре значения: 0, 1, 2, 3. Вот квадрат, который описан системой линейных уравнений:

1  0  x1  x2  x3  x4  0  1
3  2  x5  x6  x7  x8  3  2
x9 x10   0  1  2  0  .  .
x11  x12  2  3  3  1  .  .
x13  x14  2  0  0  1  .  .
x15  x16  3  1  2  3  .  .
1  0  .  .  .  .  1  0
2  3  .  .  .  .  3  2

Ячейки, в которых стоят точки, заполняются по ассоциативности.
Система уравнений получилась такая:
x1 + x2 +x3 +x4 = 10 x9 + x10 – x15 – x16 = 3 x11 + x12 – x13 – x14 = -3 x9 + x11 + x13 + x15 = 5 x10 + x12 + x14 + x16 = 7 x1 + x5 – x4 – x8 = -1 x2 + x6 – x3 – x7 = 1 x8 + x16 = 2 x4 + x7 + x14 + x15 = 6 x1 + x9 – x3 – x6 – x12 – x13 = -5 x5 – x10 = 2 x9 + x12 – x5 – x6 = 1 x4 + x11 + x14 – x2 – x7 – x15 = -3 x1 + x6 – x9 – x12 = -1 x1 + x2 + x5 + x6 = 6 x3 + x4 + x7 + x8 = 6
У меня остались ещё два уравнения, но они уже вроде как лишние. Может быть, среди приведённых 16 уравнений есть эквивалентные (что не сразу бросается в глаза), тогда можно использовать оставшиеся два уравнения. Вот они:
x9 + x10 + x11 + x12 = 6 x13 + x14 + x15 + x16 = 6
Вполне возможно, что я неправильно выбрала начальные условия в задаче, то есть надо по-другому заполнить ту часть квадрата, которая заполнена мной. Тогда можно попробовать другой вариант заполнения этой части квадрата.
Очень хочется получить ответ. Такой прекрасный квадрат должен построиться!
Метод сотовых квадратов подробно изложен в статье “Методы построения магических квадратов”.

// перенесено из темы "Мистика чисел". maxal

[maxal]

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

[Nataly-Mak]

Не поняла. Что значит пустое решение? Тогда в каком-нибудь пакете программ надо посчитать все определители системы и убедиться в том, что она не имеет решений.