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

 

Часть I

 

 

Глава 1. ЛАТИНСКИЕ КВАДРАТЫ

 

Прежде чем излагать новые аспекты метода латинских квадратов, остановлюсь подробно на теме латинских квадратов. Эта тема оказалась очень интересной и мало исследованной.  Даже в Википедии статья “Латинский квадрат” не завершена. Так что к читателям, хорошо знающим данную тему, большая просьба: сделайте свои добавления в указанную статью в Википедии.

 

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

Замечу, что все определения, касающиеся латинских квадратов, были даны в моих прежних статьях, поэтому не буду их повторять. Смотрите статью в Википедии, а также тему “Латинские квадраты” на научном форуме:

 

http://dxdy.ru/topic15897.html

 

 

***

 

Начну с ОЛК нечётного порядка. Доказано, что не существует диагональных ОЛК 3-го порядка. На рис. 4 вы видите пару не диагональных ОЛК 3-го порядка.

 

 

 

Рис. 4

 

Для любого нечётного порядка n = 2k + 1 пару ОЛК легко построить таким простым приёмом (на этом приёме и основан метод Делаира): в нижней строке первого квадрата записывается любая перестановка чисел 0, 1, 2, … n-1, оканчивающаяся числом k. Далее квадрат заполняется снизу вверх, каждая следующая строка получается из предыдущей циклическим сдвигом с шагом 1. Рассмотрим конкретный пример для n = 7. Выберем такую перестановку: 0, 1, 2, 4, 5, 6, 3. На рис. 5 показан первый латинский квадрат.

 

 

Рис. 5

 

Второй латинский квадрат заполняется аналогично с той разницей, что произвольная перестановка, которая тоже должна оканчиваться числом k, записывается в верхней строке квадрата, и квадрат заполняется сверху вниз. На рис. 6 показан второй латинский квадрат. Выбрана та же самая перестановка чисел.

 

 

Рис. 6

 

Очевидно, что латинские квадраты, построенные таким способом, не диагональные. Однако они являются нетрадиционными магическими квадратами с магической константой 21 и потому пригодны для построения магического квадрата.

Если построить данным способом ОЛК 3-го порядка, получится такая пара (рис. 7):

 

 

Рис. 7

 

А теперь покажу  диагональные ОЛК. Начну с квадратов 5-го порядка. Первая пара диагональных ОЛК 5-го порядка найдена в книге М. Гарднера “Математические досуги” (М.: Мир, 1972). На рис. 8 вы видите эту пару.

 

 

Рис. 8

 

Участник форума (ссылка на форум дана выше) М. Алексеев установил, что существует всего две пары диагональных ОЛК 5-го порядка, и нашёл вторую пару. Вот эта пара (рис. 9):

 

 

Рис. 9

 

Замечание: следует отметить, что обе пары ОЛК нормализованные, то есть в первых строках квадратов стоит тождественная перестановка чисел 0, 1, 2, 3, 4. Варьируя эту перестановку, можно составить для каждой пары 120 вариантов. Точнее можно сказать так: существует две группы пар диагональных ОЛК 5-го порядка по 120 пар в каждой группе.

Переходим к латинским квадратам 7-го порядка. Построение одной пары диагональных ОЛК для данного порядка (как и вообще для всех нечётных порядков не кратных 3) описано в статье “Построение идеальных квадратов нечётного порядка с помощью латинских квадратов” (http://www.klassikpoez.narod.ru/idlat.htm  ). На рис. 10 показана пара ОЛК, построенная в указанной статье.

 

 

Рис. 10

 

Тут следует рассказать ещё о группе попарно ортогональных латинских квадратов, которая строится пакетом математических программ Maple. Этот пакет может строить такие группы ОЛК для любого порядка, являющегося простым числом или степенью простого числа. Известно, что для порядка n группа взаимно ортогональных квадратов не может содержать больше n-1 квадратов (см., например, указанную выше книгу М. Гарднера). Группа из 6 взаимно ортогональных латинских квадратов 7-го порядка, построенная в Maple, приведена ниже (рис. 11).

 

 

 

Рис. 11

 

Очевидно, что два латинских квадрата в этой группе не диагональные, остальные четыре квадрата диагональные. Из шести взаимно ортогональных квадратов можно составить 15 пар ОЛК. Обратите внимание, что все эти пары нормализованные (см. замечание выше).

 

 

Рассмотрим теперь квадраты чётно-чётного порядка n = 4k. Пару диагональных ОЛК 4-го порядка очень просто построить. Эта пара показана на рис. 12.

 

 

Рис. 12

 

Пара тоже нормализованная. Варьируя перестановку чисел 0, 1, 2, 3, можно получить 24 варианта.

 

Далее приводится группа из семи взаимно ортогональных латинских квадратов 8-го порядка, построенная в Maple (рис. 13).

 

 

 

 

Рис. 13

 

В этой группе только один латинский квадрат не диагональный. Из 7 квадратов данной группы можно составить 21 пару ОЛК. Все пары тоже будут нормализованные.

Обратите внимание: все латинские квадраты данной группы получаются друг из друга перестановкой строк.

Далее в точной аналогии с латинскими квадратами 8-го порядка я составила пару диагональных ОЛК 16-го порядка. Вот эта пара:

 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 

Одной пары диагональных ОЛК нам вполне достаточно для построения магического квадрата. Точно так же по аналогии можно составить пару диагональных ОЛК для любого порядка n = 2^p, p = 2, 3, 4 …

Для таких порядков группу ОЛК можно получить и в Maple.

 

 

А теперь покажу ещё одну группу взаимно ортогональных  латинских квадратов 8-го порядка. Эту группу я получила из знаменитого полумагического квадрата Агриппы. Вообще-то квадрат Агриппы 12-го порядка. Этому квадрату посвящена отдельная статья: http://www.klassikpoez.narod.ru/franklin5.htm

На рис. 14 показан полумагический квадрат Агриппы 12-го порядка.

 

 

                                                                      Рис. 14

 

В квадрате выделена начальная цепочка. Она имеет очень необычную форму.

Чтобы посмотреть, из каких латинских квадратов построен этот полумагический квадрат, я разложила его на два латинских квадрата. Второй латинский квадрат, к сожалению, получился обобщённый. А вот первый латинский квадрат классический и весьма гармоничен. Вы видите его на рис. 15.

 

 

Рис. 15

 

В точном соответствии с этим алгоритмом составляю первый латинский квадрат 8-го порядка (рис. 16):

 

 

Рис. 16

 

А теперь в этом латинском квадрате переставляю строки по аналогии с тем, как это делается в группе взаимно ортогональных латинских квадратов, построенной в Maple (см. рис. 13). И пара ОЛК 8-го порядка готова! Второй латинский квадрат этой пары вы видите на рис. 17.

 

 

Рис. 17

 

Предлагаю читателям произвести другие перестановки строк в латинском квадрате с рис. 16, аналогичные перестановкам строк в группе квадратов на рис. 13. Логично предположить, что в результате этого получится группа из семи взаимно ортогональных латинских квадратов 8-го порядка. Очевидно, что эта группа отличается от группы с рис. 13.

 

Таким образом, уникальная схема Агриппы даёт нам способ составления одного латинского квадрата любого чётно-чётного порядка. Вот, например, первый латинский квадрат 4-го порядка, составленный по этой схеме (рис. 18):

 

 

Рис. 18

 

Этот квадрат совпадает со вторым латинским квадратом в паре, показанной на рис. 12. Заметьте: этот латинский квадрат диагональный.

А это первый латинский квадрат 16-го порядка, построенный по схеме Агриппы (рис. 19):

 

 

Рис. 19

 

Кстати, посмотрите на пару ОЛК 16-го порядка, приведённую выше. Второй латинский квадрат в этой паре получается из первого перестановкой строк. Вполне возможно, что, аналогично переставив строки в латинском квадрате с рис. 19, мы получим латинский квадрат ортогональный данному. Попробуйте!

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

Итак, для порядков n = 4k мы умеем составить первый латинский квадрат. Задача сводится к составлению ортогонального латинского квадрата. При этом именно классического латинского квадрата. Составление обобщённого ортогонального квадрата элементарно выполняется путём разложения соответствующего магического или полумагического квадрата, построенного по алгоритму Агриппы.

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

 

 

 

 

Рис. 20

 

В этой группе два латинских квадрата не диагональные, остальные 6 диагональные. Из восьми квадратов группы можно составить 28 пар ОЛК. Интересно отметить, что каждый латинский квадрат в этой группе получается из любого другого квадрата группы перестановкой строк. При этом первая строка во всех квадратах остаётся на месте, а каждая следующая строка занимает в квадратах группы 8 разных позиций. Все пары ОЛК здесь тоже нормализованные.

Таким образом, с порядками, равными степени числа 3, вопрос составления ОЛК тоже решён. С этой задачей справляется Maple. Можно попробовать составить пару ОЛК для таких порядков по аналогии.

А вот с нечётными порядками кратными 3 уже возникают сложности. Первый такой порядок равен 15. Здесь я приведу результаты, полученные в статье “Построение идеальных квадратов 15-ого порядка с помощью двух латинских квадратов (часть I)” (http://www.natalimak1.narod.ru/id15new.htm )

В этой статье пары ОЛК получены путём разложения известных идеальных квадратов 15-го порядка, построенных методом качелей, на два латинских ортогональных квадрата. На рис. 21-22 показана одна из таких пар ОЛК.

 

 

Рис. 21

 

 

Рис. 22

 

Очевидно, что второй латинский квадрат получается из первого отражением относительно горизонтальной оси симметрии.

Поскольку методом качелей можно построить идеальный магический квадрат любого нечётного порядка, точно так же разложением готового магического квадрата может быть получена пара ОЛК.

 

Теперь посмотрим на ОЛК чётно-нечётного порядка. Порядок 6 является уникальным случаем: для латинских квадратов 6-го порядка не существует ортогональных квадратов. Поэтому минимальный чётно-нечётный порядок, с которого надо начать исследование ОЛК, равен 10.

В статье “Completion of the Spectrum of Orthogonal Diagonal Latin Squares” (J. W. Brown и другие) приведены три пары ортогональных диагональных латинских квадратов 10-го порядка. Эти пары показаны на рис. 23-25.