Н. Макарова

 

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

 

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

Напомню определение диагональных латинских квадратов. Классический латинский квадрат порядка 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

 

 

Рис. 18

 

Это первый диагональный латинский квадрат 26-го порядка, который мне удалось построить. О паре ОДЛК  26-го порядка пока ничего не знаю, кроме того, что она построена (например, в статье: А. В. Назарок. “Пары ортогональных дважды диагональных латинских квадратов порядков 15, 18 и 26”; статью я не видела).

 

Думаю, что этих примеров вполне достаточно даже для того, чтобы реализовать алгоритм; здесь всё чётко и для каждого следующего порядка совершенно аналогично.

 

Сложнее дело с чётными k и с нечётными k кратными 3, сложнее потому, что в статье нет ни одного подобного примера. Вполне возможно, что алгоритм описан в тексте статьи, но я не понимаю английский текст. Так что пришлось додумывать самой. Рассмотрим пример k = 4, порядок ДЛК будет равен 8. На рис. 19 вы видите ДЛК 8-го порядка. В квадрате выделены зелёным цветом переставленные числа. Здесь есть одна особенность: D₁ = D₃ и D₂ = D₄. Всё остальное выполняется по той же самой схеме.

 

 

Рис. 19

 

Точно так же строю ДЛК 12-го порядка (рис. 20). Это первый диагональный латинский квадрат 12-го порядка, который вижу. Пару ОДЛК 12-го порядка тоже пока не видела и как её построить, не знаю.

 

 

Рис. 20

 

Пожалуй, покажу ещё один пример – построение ДЛК 16-го порядка, хотя ДЛК данного порядка хорошо известны, они имеются в стандартной группе MOLS. Готовый ДЛК 16-го порядка изображён на рис. 21.

 

 

Рис. 21

 

Здесь всё аналогично двум предыдущим примерам. Диагональный латинский квадрат 8-го порядка для построения этого ДЛК взят из основной группы MOLS.

А теперь проверим “преемственность” алгоритма Гергели, то есть построим ДЛК 20-го порядка, используя построенный данным методом ДЛК 10-го порядка. Для построения возьмём нормализованный ДЛК 10-го порядка (см. рис. 8). Готовый ДЛК 20-го порядка вы видите на рис.  22.

 

 

Рис. 22

 

Всё получилось! Значит, точно так же можно взять ДЛК 12-го порядка, построенный данным методом (см. рис. 20), и построить ДЛК 24-го порядка, а с помощью ДЛК 16-го порядка (см. рис. 21) построить ДЛК 32-го порядка и так далее. Посмотрим ещё один пример: возьмём ДЛК 8-го порядка, построенный методом Гергели (см. рис. 19), и построим на его основе ДЛК 16-го порядка. Предварительно приведём ДЛК с рис. 19 к нормализованному виду (рис. 23):

 

 

Рис. 23

 

На рис. 24 показано построение ДЛК 16-го порядка на основе этого ДЛК 8-го порядка.

 

 

Рис. 24

 

Осталось показать построение ДЛК методом Гергели для случая, когда k нечётное число кратное 3. Рассмотрим пример построения ДЛК 18-го порядка, в этом случае k = 9. Здесь уже D₁ ≠ D₃ и D₂ ≠ D₄. Как и в случае нечётных k не кратных 3, квадраты D₃ и D₄ получаются из квадратов D₁ и D₂ преобразованием тождественной перестановки чисел. Кроме того, квадраты D₁ и D₃ конструируются на основе одного ДЛК 9-го порядка, а квадраты D₂ и D₄ – на основе другого ДЛК 9-го прядка (оба ДЛК 9-го порядка берутся из стандартной группы MOLS). На рис. 25 вы видите готовый ДЛК 18-го порядка.

 

 

Рис. 25

 

Следует отметить, что алгоритм построения ДЛК для случаев, когда k чётное число или нечётное число кратное 3, не так прост для реализации, как в случае k нечётных и не кратных 3.

 

На этом я пока завершаю рассмотрение метода Гергели. Напомню, что остались ещё порядки вида n = 2k + 1. В статье Гергели показан пример построения ДЛК порядка 11 (см. рис. 7). Я пока не разобралась с порядками данной серии. Замечу, что если порядок n является нечётным числом не кратным 3, то построение ДЛК такого порядка не вызывает никаких затруднений. Таким образом, осталось рассмотреть метод построения ДЛК порядков вида n = 3(2k + 1), k = 2, 3, 4, … При этом можно исключить все порядки, являющиеся степенью числа 3, так как для таких порядков ДЛК имеются в стандартных группах MOLS. Наконец, в этой серии есть порядки, для которых работает метод составных квадратов, например, порядок 45. Первый проблемный порядок в указанной серии – это порядок 15. Предлагаю читателям прямо сейчас попробовать построить ДЛК 15-го порядка методом Гергели.

 

***

 

ДЛК 15-го порядка я построила по аналогии с ДЛК 11-го порядка, приведённым в статье. Вот этот ДЛК (рис. 26):

 

 

Рис. 26

 

Однако ДЛК 21-го порядка с ходу не получился. Надо подумать.

 

***

 

Подумав над веткой алгоритма Гергели для порядков вида n = 2k + 1, пришла к выводу, что здесь тоже надо рассматривать три случая: а) k – нечётное число не кратное 3; б) k – нечётное число кратное 3; в) k – чётное число. Показанный выше пример для n = 15, а также приведённый в статье Гергели пример для n = 11, относятся к случаю а). В этом случае всё очень просто. И вот вам ещё один подобный пример: для n = 23 (k = 11). Готовый ДЛК 23-го порядка показан на рис. 27.

 

 

Рис. 27

 

Реализацию этой ветви алгоритма тоже очень просто выполнить.

 

Теперь рассмотрим случай в). Начнём с самого простого примера: k = 4, n = 9. Здесь тоже всё оказалось просто. Берём ДЛК 8-го порядка с рис. 19 и помещаем составляющие его квадраты 4х4 в матрицу для латинского квадрата 9-го порядка, как показано на рис. 28.

 

 

Рис. 28

 

В центральную ячейку квадрата пишем число 8, числа в зелёных ячейках тоже заменяем числом 8, а числа из зелёных ячеек выносим в центральный горизонтальный ряд. Центральный вертикальный ряд после этого заполняется элементарно. На рис. 29 вы видите готовый ДЛК 9-го порядка, построенный методом Гергели.

 

 

Рис. 28

 

Следующий порядок в этой серии порядков равен 13 (k = 6). Всё выполняем совершенно аналогично: берём ДЛК 12-го порядка с рис. 20 и размещаем его в матрице для латинского квадрата 13-го порядка, а затем выполняем замены и перестановки чисел (рис. 29).

 

 

Рис. 29

 

ДЛК порядка 17 пропускаю, сразу покажу построение ДЛК 21-го порядка (k = 10). Смотрите это построение на рис. 30.

 

 

Рис. 30

 

Всё аналогично двум предыдущим примерам. Основной момент - правильно определить те числа, которые заменяются числом 20 [в общем случае – числом (n – 1)]. Ячейки, в которых заменяются числа, во всех трёх квадратах выделены зелёным цветом.

 

Осталось рассмотреть всего один случай: k – нечётное число кратное 3. Рассмотрим построение ДЛК порядка 19, в этом случае k = 9. Будем действовать точно так же, возьмём ДЛК 18-го порядка с рис. 25 и поместим его в матрицу для латинского квадрата 19-го порядка (рис. 31).

 

 

Рис. 31

 

И вот тут загвоздка вышла: никак не могу определить те числа, которое надо заменить числом 18. Опять надо думать. Совсем немного осталось!

 

***

 

Так ничего и не придумала для последнего случая. Ну, ДЛК 19-го порядка очень просто построить и без метода Гергели. Для данного порядка, поскольку он является простым числом, существует полная группа MOLS, состоящая из 18 латинских квадратов, из них 16 будут диагональные.

 

Покажу реализацию алгоритма для самого простого случая: n = 2k, где k – нечётное число не кратное 3.

 

 

 

В программу надо ввести значение k. При этом не забывайте, что k в этом случае должно быть нечётным и не кратным 3. Программа работает для k ≥ 5.

На рис. 32 показан диагональный латинский квадрат 34-го порядка, построенный по данной программе. В этом примере k = 17.

 

 

 

Рис. 32

 

На основе предложенной программы легко составить программу построения ДЛК порядков вида n = 2k + 1, где  k – нечётное число не кратное 3. Смотрите примеры построения ДЛК порядков 15 и 23 (рис. 26 – 27). На основе показанного выше ДЛК 34-го порядка очень просто построить ДЛК 35 порядка.

 

Реализовать другие ветви алгоритма Гергели сложнее. Предлагаю читателям сделать это. Кроме того, надо додумать одну ветвь алгоритма: n = 2k + 1, где k –нечётное число кратное 3 (см. рис. 31).

Ещё раз напомню, что метод описан в статье Гергели, которую я могу выслать читателю, захотевшему разобраться с этим методом досконально.

 

ДОБАВЛЕНИЕ (26 мая 2011 г)

 

На форуме Портала ЕН (см. [1]) задачку предложили, связанную с латинскими диагональными квадратами. Заглянула в эту статью, вспомнила нерешённую задачу о построении ДЛК 19-го порядка методом Гергели. Предложила задачу на форуме. Участник форума А. Чернов задачу сразу решил. Он действовал по схеме, изображённой на рис. 15. Мне показал квадрат D1 и готовый диагональный латинский квадрат 19-го порядка. Вот эти квадраты:

 

D1 =

 

1 2 3 4 5 6 7 8 9

2 3 1 7 4 8 9 5 6

3 1 2 5 8 9 6 7 4

4 8 9 6 3 7 1 2 5

5 6 8 9 7 4 2 1 3

6 4 7 1 9 5 8 3 2

7 9 5 8 2 3 4 6 1

8 5 4 2 6 1 3 9 7

9 7 6 3 1 2 5 4 8

 

D =

 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 

Дальше я стала разбираться сама.

Взяла в качестве квадрата D1 такой латинский квадрат 9-го порядка (рис. 33):

 

 

Рис. 33

 

В этом латинском квадрате одна главная и одна разломанная диагональ должны состоять из различных чисел (это хорошо видно на рис. 15). На рисунке эти диагонали выделены.

На рис. 34 показан результат выполнения первого этапа – заполнение верхней половины квадрата 19-го порядка.

 

 

Рис. 34

 

Квадрат D2 получается из квадрата D1 очень просто: к каждому элементу квадрата D1 надо прибавить 9 и затем отразить квадрата относительно вертикальной оси симметрии. Сумма 18 берётся по модулю 9.

Далее переставляем разломанную диагональ 2, 1, 6, 8, 7, 3, 5, 4, 9 из D1 в D2 и заменяем числа этой диагонали в D1 на 18; диагональ, бывшая в D2, переходит в столбец, полученный результат смотрите на рис. 35.

 

 

Рис. 35

 

Осталось заполнить нижнюю половину квадрата. Здесь выполняется преобразование квадратов D1, D2 в квадраты D3, D4 (см. схему на рис. 15). Затем на место главной диагонали в квадрате D4 помещается разломанная диагональ из квадрата D2, на место главной диагонали в квадрате D3 помещается разломанная диагональ, которая была в квадрате D2 первоначально (перешедшая в столбец); числа разломанной диагонали в квадрате D3 заменятся на число 18, заменённые числа переходят в столбец. Центральная строка заполняется элементарно.

 

Готовый ДЛК 19-го порядка вы видите на рис. 36.

 

 

Рис. 36

 

Аналогично построен ДЛК 31-го порядка – следующего порядка в данной серии порядков. В качестве D1 выбран латинский квадрат 15-го порядка, показанный на рис. 37.

 

 

Рис. 37

 

Этот латинский квадрат взят из сборника статей «Анатомия магических квадратов», который был выложен на форуме dxdy.ru М. Алексеевым. Очень интересные статьи! В какой-то из своих статей, написанных позже, я прикрепила архив, в котором есть этот сборник статей.

 

Готовый ДЛК 31-го порядка показан на рис. 38.

 

 

Рис. 38

 

Теперь рассмотрены все ветви метода Гергели. Можно запрограммировать построение ДЛК любого порядка. Выше показана программа для одной из ветвей метода.

 

 

 

14 - 25 мая 2009 г. – 26 мая 2011 г.

г. Саратов

 

 

 

Читайте мою виртуальную книгу “Волшебный мир магических квадратов”:

 

http://www.klassikpoez.narod.ru/glavnaja.htm

 

Скачайте электронную версию этой книги:

 

http://narod.ru/disk/5834353000/Magic_squares.pdf.html

 

 

Заодно прихватите книгу “Позиционные системы счисления”, авось, пригодится:

 

http://narod.ru/disk/5936760000/pozic4.pdf.html

 

 

На главную страницу:

 

http://www.klassikpoez.narod.ru/index.htm

 

 

 

Контакты:

natalimak1@yandex.ru

QIP: 571-379-327