Н. Макарова

 

ПОСТРОЕНИЕ ДИАГОНАЛЬНЫХ ЛАТИНСКИХ КВАДРАТОВ

 

Здесь будут рассмотрены некоторые способы построения одиночных диагональных латинских квадратов (одиночных – это значит таких, для которых необязательно существует ортогональный соквадрат). В дальнейшем для термина “диагональный латинский квадрат” будет использоваться аббревиатура ДЛК.

Напомню определение диагональных латинских квадратов. Классический латинский квадрат порядка n называется диагональным, если в каждой главной диагонали квадрата находятся n различных элементов. В англоязычной литературе диагональные латинские квадраты называются “doubly diagonal”.

Для порядков 2 и 3 ДЛК не существуют. Для порядков 4 – 8 ДЛК конструируются элементарно. На рис. 1 – 2 показаны примеры ДЛК порядков 4 – 8.

 

 

Рис. 1

 

 

Рис. 2

 

Латинские квадраты порядков 4, 5, 7 и 8 взяты из стандартных групп MOLS, латинский квадрат 6-го порядка взят из книги Ю. В. Чебракова “Магические квадраты. Теория чисел, алгебра, комбинаторный анализ”, С. – Петербург, 1995. Напомню, что стандартные группы MOLS строятся в математическом пакете Maple.

Все приведённые латинские квадраты нормализованные, то есть в первой строке содержится тождественная перестановка чисел.

Любой диагональный латинский квадрат порядка n является нетрадиционным магическим квадратом с магической константой

 

S = (n – 1)n/2.

 

Не вызывает никаких затруднений построение диагональных латинских квадратов для порядков, являющихся простым числом или степенью простого числа. К таким порядкам относятся, например, порядки 9 и 11. Покажу примеры ДЛК для указанных порядков (рис. 3).

 

 

Рис. 3

 

Эти латинские квадраты тоже взяты из стандартных групп MOLS.

 

Итак, остаются такие латинские квадраты, порядки которых не являются простым числом или степенью простого числа. Среди таких порядков есть ещё две группы, для которых построение ДЛК не вызывает затруднений: а) нечётные порядки не кратные 3; б) составные порядки, представимые в виде произведения двух чисел, для каждого из которых существует ДЛК. Для порядков группы б) ДЛК строятся методом составных квадратов.

Для всех остальных порядков ДЛК построить не так просто, и первым таким порядком является 10.

Я нашла статью, в которой даётся метод построения ДЛК. Статья на английском языке, поэтому я не поняла суть метода, но примеры ДЛК из этой статьи покажу. Сначала данные о статье: Ervin Gergely. Doubly diagonalized latin squares. [Journal of Combinatorial Theory (A) 16, 266 – 272 (1974)]

Кстати, в этой статье приводится точно такой же ДЛК 6-го порядка, какой показан на рис. 1.

Итак, метод, описываемый в этой статье, выглядит примерно так. Для порядков вида n = 2k квадрат составляется из четырёх квадратов порядка k, как показано на рис. 4.

 

 

Рис. 4

 

Как конструируются квадраты D_i, я не поняла, точнее, для конкретного примера n = 10, конечно, поняла, но как это делать для любого порядка n = 2k, по одному примеру непонятно, надо переводить текст статьи, тогда, возможно, всё станет ясно.

Покажу пример, приведённый в статье. Это ДЛК 10-го порядка (рис. 5).

 

 

Рис. 5

 

Обратите внимание: каждый квадрат D_i содержит все числа от 0 до 9.

Для порядков вида n = 2k + 1 ДЛК имеет такую конструкцию (рис. 6):

 

 

Рис. 6

 

В статье приведён в качестве примера ДЛК 11-го порядка. Вы видите этот диагональный латинский квадрат на рис. 7.

 

 

Рис. 7

 

Ко всем диагональным латинским квадратам можно применить любое преобразование трансформации тождественной перестановки чисел, которое сохранит свойство диагональности. Покажу для примера превращение ДЛК с рис. 5 в нормализованный латинский квадрат с помощью такого преобразования. Трансформация тождественной перестановки чисел будет следующая:

 

0  1  2  3  4  5  6  7  8  9

1  7  3  4  5  0  9  8  2  6

 

Полученный в результате такого преобразования нормализованный диагональный латинский квадрат показан на рис. 8.

 

 

Рис. 8

 

Посмотрите на диагональные числа в этом латинском квадрате, они расположились очень интересно: сумма двух диагональных чисел в каждой строке равна 9. И таким свойством обладают не только диагональные числа; любые два числа, симметрично расположенные относительно вертикальной оси симметрии квадрата, в сумме дают 9. Изящный получился квадрат!

Напомню, что латинские квадраты, получаемые друг из друга преобразованием трансформации тождественной перестановки чисел, называются изоморфными. Таким образом, латинские квадраты, изображённые на рис. 5 и на рис. 8, изоморфные.

Другие ДЛК 10-го порядка есть, например, в трёх парах ОДЛК, приведённых в статье Брауна (эти пары показаны в моих ранних статьях, посвящённых ортогональным латинским квадратам). Покажу одну из этих пар ОДЛК (рис. 9).

 

 

Рис. 9

 

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

 

 

Рис. 10

 

Тоже любопытный получился квадратик. Посмотрите на квадраты 5х5, из которых он составлен, в них интересные свойства имеются. А вот можно ли построить к этому диагональному латинскому квадрату ортогональный соквадрат? Хорошая задача для читателей!

 

Теперь покажу метод составных квадратов. Этот метод уже был подробно описан в статье “Построение пар ортогональных диагональных латинских квадратов методом составных квадратов” (http://www.natalimak1.narod.ru/aspekty5.htm ). Здесь покажу построение одиночного ДЛК 24-го порядка. В качестве базового квадрата возьмём диагональный латинский квадрат 4-го порядка, а в качестве основного – диагональный латинский квадрат 6-го порядка (см. рис. 1). Готовый ДЛК 24-го порядка показан на рис. 11.

 

 

Рис. 11

 

В этом латинском квадрате тоже сумма любых двух чисел, расположенных симметрично вертикальной оси симметрии квадрата, равна одному и тому же значению – 23. Таким свойством обладают базовый и основной квадраты, с помощью которых построен этот латинский квадрат.

 

Теперь отмечу, что все совершенные латинские квадраты являются диагональными. О совершенных латинских квадратах смотрите статьи: http://www.natalimak1.narod.ru/perfect1.htm и http://www.natalimak1.narod.ru/perfect2.htm

Во второй статье построен квази-совершенный латинский квадрат 36-го порядка, который тоже является диагональным. Это понятно: он построен методом составных квадратов, в качестве базового и основного квадратов взяты совершенные латинские квадраты 4-го и 9-го порядка. Покажу здесь для примера совершенный латинский квадрат 9-го порядка (рис. 12).

 

 

Рис. 12

 

И, наконец, ещё один очень интересный метод построения диагональных латинских квадратов, который уже описан в статье “Ортогонгальные диагональные латинские квадраты” (http://www.natalimak1.narod.ru/diagon.doc ). Для этого метода подходит не любой латинский квадрат, а только латинский квадрат специальной структуры с подквадратом. При этом разность между порядком латинского квадрата и порядком подквадрата должна быть чётным числом. В указанной статье вы найдёте ссылку на статью, в которой я нашла построение пары ОДЛК 14-го порядка. Здесь покажу построение только одного квадрата пары. Исходный латинский квадрат 14-го порядка с подквадратом 4-го порядка выглядит так (рис. 13):

 

 

Рис. 13

 

На рис. 14 вы видите диагональный латинский квадрат, полученный из этого латинского квадрата.

 

 

Рис. 14

 

Как из квадрата с рис. 13 получен квадрат на рис. 14, вы поймёте по раскраске.

Таким методом я построила пары ОДЛК 15-го, 18-го и 22-го порядков. Смотрите указанную выше статью, а также статью http://www.natalimak1.narod.ru/diagon22.htm

 

***

 

Продолжила рассмотрение примера построения ДЛК 10-го порядка в статье Гергели, очень хотелось разобраться. Для порядков вида n = 2k, если k – нечётное число не кратное 3 (именно таким и является пример для n = 10), удалось разобраться быстро. Сначала приведу фрагмент из статьи, в котором показано конструирование квадратов D_i (рис. 15).

 

 

 

Рис. 15

 

Готовый ДЛК рассматриваемого примера показан на рис. 5.

Внимательно изучив этот пример, я в точной аналогии построила ДЛК 14-го (k = 7), 22-го (k = 11) и 26-го (k = 13) порядков. Вспомогательные квадраты D_i составляются методом циклического сдвига. Затем в этих вспомогательных квадратах выполняются перестановки чисел. Посмотрев следующие примеры, вы всё поймёте. На рис. 16 – 18 показаны ДЛК порядков 14, 22 и 26. В латинском квадрате 14-го порядка выделены зелёным цветом переставленные числа. В квадратах 22-го и 26-го порядка числа переставляются точно так же.

 

 

Рис. 16

 

 

Рис. 17