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

 

Часть 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.

 

 

Рис. 23

 

 

Рис. 24

 

 

Рис. 25

 

Эти пары диагональных ОЛК строятся уже совсем иначе, квадраты не получаются один из другого перестановкой строк. Кроме того, в первых строках квадратов стоит не тождественная перестановка чисел 0, 1, 2, … 9. Зато тождественная перестановка стоит в одной из главных диагоналей (во всех  шести квадратах). Покажу на примере ОЛК 10-го порядка, как выполняется трансформация тождественной перестановки. Произведём такую замену тождественной перестановки чисел:

 

0  1  2  3  4  5  6  7  8  9

0  4  8  9  2  6  3  5  7  1

 

В результате такой замены получим следующую пару диагональных ОЛК (рис. 26):

 

 

Рис. 26

 

Точно так же можно выполнить любую другую трансформацию тождественной перестановки и получить другие пары диагональных ОЛК 10-го порядка.

В другой статье (Stenson) нашла интересные не диагональные ОЛК 10-го порядка. При этом задана схема составления пары ОЛК в таком виде (рис. 27):

 

 

Рис. 27

 

Здесь переменные a₁, a₂, a₃ принимают значения 7, 8, 9 в любой комбинации. Это значит, что можно составить шесть пар ОЛК. На рис. 28 показана пара ОЛК при таких значениях переменных: a₁ = 7, a₂ = 8, a₃ = 9.

 

 

Рис. 28

 

Другие пары ОЛК по данной схеме предлагается составить читателям.

 

Расскажу ещё об одной паре ОЛК, найденной в указанной выше книге М. Гарднера. Эта пара получается из известного греко-латинского квадрата, построенного Э. Т. Паркером в 1958 г. Открытие Паркера подвергло серьёзному сомнению гипотезу Эйлера о том, что не существует ОЛК для порядков n = 4k + 2. Эта гипотеза оказалась верной только для порядка 6. Доказательство гипотезы Эйлера для порядка 6 опубликовал в 1901 г. французский математик Гастон Тарри.

Читатели, знакомые с моими прежними работами, знают, что греко-латинский квадрат получается из пары ОЛК простым объединением латинских квадратов. На рис. 29 приведён греко-латинский квадрат Э. Т. Паркера.

 

 

Рис. 29

 

Вот что рассказывает М. Гарднер в своей книге: “На обложке ноябрьского номера журнала Scientific American за 1959 год была помещена репродукция с картины работающей в журнале художницы Эми Казе. На картине изображён греко-латинский квадрат десятого порядка Паркера. Художница взяла десять красок вместо десяти цифр и каждую клетку раскрасила в два цвета так, чтобы на картине не было двух одинаковых клеток. Картина Эми Казе была куплена у художницы и подарена Паркеру его институтом”.

 

Попробую воспроизвести картину Эми Казе (рис. 30).

 

 

Рис. 30

 

Одна читательница журнала вышила по картине Эми Казе коврик Паркера.

 

Вернёмся от художеств к математике. Разложим греко-латинский квадрат Паркера с рис. 29 на два ортогональных латинских квадрата (рис. 31):

 

 

Рис. 31

 

Посмотрев внимательно на эту пару ОЛК, предположила, что её можно задать точно так же, как это сделал Stenson (см. рис. 27). Проверяю своё предположение (рис. 32):

 

 

Рис. 32

 

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

 

a₁ = 8, a₂ = 9, a₃ = 7

 

Пара ОЛК, составленная для данных значений переменных, изображена на рис. 33.

 

 

Рис. 33

 

Всё получилось! Таким образом, с помощью формы, изображённой на рис. 32,  мы можем составить 6 пар ОЛК 10-го порядка Паркера.

 

Вот только непонятно, почему Stenson берёт перестановки только трёх чисел, если можно переставлять все 10 чисел. Выше было показано на примере ОЛК Брауна, как можно выполнить любую трансформацию тождественной перестановки чисел 0, 1, 2, … 9. Покажу ещё один интересный результат, полученный в ходе экспериментов с парами ОЛК Брауна. Первый латинский квадрат из пары ОЛК, изображённой на рис. 23, преобразован с применением такой трансформации тождественной перестановки чисел:

 

0  1  2  3  4  5  6  7  8  9

1  2  3  4  5  6  7  8  9  0

 

Здесь выполнена циклическая перестановка, переставлены все 10 чисел. В результате такого преобразования получен следующий латинский квадрат (рис. 34):

 

 

Рис. 34

 

А второй латинский квадрат в этой паре не преобразовывала. Тем не менее, новый латинский квадрат с рис. 34 оказался ортогональным второму латинскому квадрату этой пары.

Дальше вы увидите ещё более интересный случай: оба латинских квадрата из пары ОЛК преобразованы с применением разных трансформаций тождественной перестановки чисел, тем не менее, они остались по-прежнему ортогональными.

 

 

Продолжение читайте  здесь:

 

http://www.natalimak1.narod.ru/aspekty1.htm

 

27 – 28 декабря 2008 г.

г. Саратов

 

Статья редактировалась 7 января 2009 г. Удалены черновые наброски.

 

       Пишите мне!

Приглашаю всех на форум!

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