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

 

Глава 1. ЛАТИНСКИЕ КВАДРАТЫ (часть II)

 

Данная страница является продолжением страницы

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

 

В предыдущей части статьи были показаны различные группы и пары ОЛК до порядка 10 включительно. Продолжу рассмотрение вопроса об ОЛК для чётно-нечётных порядков. В книге М. Гарднера “Математические досуги” (М.: Мир, 1972) говорится, что после того, как Э. Т. Паркер в 1958 году построил греко-латинский квадрат 10-го порядка, Боус нашёл некоторые общие правила построения греко-латинских квадратов. Паркер, Боус и Шрикхенд (говорится в книге) составили греко-латинские квадраты порядков 10, 14, 18, 22 и так далее. Однако  греко-латинские квадраты порядков 14 и 18 я нигде не встречала. Неизвестны мне и общие правила построения греко-латинских квадратов любого чётно-нечётного порядка, хотя очень хочется узнать эти правила.

В статье “Three mutually orthogonal idempotent Latin squares of orders 22 and 26” (R. J. R Abel и другие) нашла группу из трёх взаимно ортогональных латинских квадратов 22-го порядка. Хотя в названии статьи говорится о порядках 22 и 26, однако квадратов 26-го порядка я не увидела. Может быть, в статье приводится метод составления таких ОЛК для порядков 22 и 26, а квадраты приведены только порядка 22. Покажу эту группу взаимно ортогональных латинских квадратов 22-го порядка (рис. 1 – 3).

 

 

Рис. 1

 

 

Рис. 2

 

 

Рис. 3

 

Примечание: в указанной статье латинские квадраты заполнены числами от 1 до 22. Я буду придерживаться традиционного заполнения латинских квадратов порядка n числами от 0 до n - 1.

 

Обратите внимание: в каждом латинском квадрате этой группы в одной из главных диагоналей стоит тождественная перестановка чисел 0, 1, 2, … 21. На рис. 1 эта главная диагональ выделена.

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

 

***

 

Итак, я рассказала о тех ОЛК, которые мне известны. Как я уже говорила, доказано существование ортогональных пар диагональных латинских квадратов любого порядка, кроме 2, 3 и 6 (см. статью “Completion of the Spectrum of Orthogonal Diagonal Latin Squares”). Однако таких пар я видела очень мало. Вот, например, для порядка 22 нашла пары ОЛК, но эти латинские квадраты не диагональные.

Заинтересовавшимся читателям предлагаю заняться исследованием вопроса составления диагональных ОЛК любого порядка (кроме 2, 3, 6). По этому вопросу существует несколько статей, большинство из которых относятся к 70-м годам прошлого века. Вот, например, список литературы по данной теме из указанной выше статьи:

 

              

 

 

***

 

Придумала очень простую схему составления латинских квадратов порядка n = 4k + 2. Кажется, схема работает для любого порядка данной серии. Однако построить второй латинский квадрат ортогональный данному мне не удалось.

Покажу первые латинские квадраты. Начну с минимального порядка данной серии – 6-го (рис. 4).

 

 

Рис. 4

 

Ну, для этого латинского квадрата не надо и пытаться искать ортогональный квадрат, так как такого квадрата точно не существует. Можно попытаться построить обобщённый ортогональный квадрат, такой квадрат может существовать, а может и не существовать.

Далее на рис. 5 показан первый латинский квадрат 10-го, построенный по такой же схеме.

 

 

Рис. 5

 

И ещё покажу латинский квадрат 14-го порядка, построенный по этой схеме (рис. 6):

 

 

Рис. 6

 

Вот такие латинские квадраты очень легко строятся по придуманной мной схеме. Но вот как строить ортогональные квадраты к этим квадратам? Если бы это удалось, то мы имели бы пару ОЛК для любого порядка n = 4k + 2 (k>1).

Следует отметить, что не к каждому латинскому квадрату (имеются в виду порядки отличные от 2 и 6) можно построить ортогональный латинский квадрат. Вот пример латинского квадрата 4-го порядка, для которого не существует ортогонального латинского квадрата (пример из статьи Stenson “Latin Squares”) [рис. 7]:

 

 

Рис. 7

 

Глава 2. МЕТОД ЛАТИНСКИХ КВАДРАТОВ. НОВЫЕ АСПЕКТЫ

 

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

 

2.1. ВАРИАНТ МЕТОДА ДЕЛАИРА

 

Метод Делаира применяется для построения магических квадратов любого нечётного порядка n = 2k + 1. Он подробно изложен в статье “Методы построения магических квадратов”. В данном методе оба вспомогательных латинских квадрата не диагональные.

Предлагается новый вариант метода Делаира, основанный на использовании диагональных ОЛК. Начну с квадратов 5-го порядка. Возьмём следующую пару диагональных ОЛК (рис. 8):

 

 

Рис. 8

 

Из этой пары ОЛК получаем такой магический квадрат (рис. 9):

 

 

Рис. 9

 

Если взять вторую пару диагональных ОЛК 5-го порядка (как уже отмечалось в первой части статьи, существует всего две пары диагональных ОЛК 5-го порядка), построенный из этой пары магический квадрат будет эквивалентен магическому квадрату, построенному методом Москопула (методом коня). Квадрат на рис. 9 оригинален, то есть не эквивалентен квадрату, построенному методом коня.

Теперь возьмём пару диагональных ОЛК 7-го порядка из группы взаимно ортогональных квадратов, построенной в Maple (рис. 10).

 

 

Рис. 10

 

На рис. 11 показан магический квадрат, построенный из данной пары ОЛК. Этот квадрат тоже эквивалентен магическому квадрату, построенному методом Москопула.

 

 

Рис. 11

 

Как уже отмечалось в первой части статьи, из приведённых нормализованных пар диагональных ОЛК можно получить целую группу подобных пар ОЛК, варьируя перестановку чисел 0, 1, 2, … n-1.

А теперь покажу другую пару диагональных ОЛК 7-го порядка. В первой части статьи было сказано, что такие пары легко составляются для любого нечётного порядка не кратного 3. Составление таких пар ОЛК подробно описано в статье

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

 

 

Рис. 12

 

Обратите внимание: если смотреть на эти латинские квадраты как на нетрадиционные магические квадраты, они являются не просто магическими, но ещё и ассоциативными, и пандиагональными.

Из данной пары диагональных ОЛК строится идеальный магический квадрат 7-го порядка, который вы видите на рис. 13.

 

 

Рис. 13

 

Итак, с составлением пары диагональных ОЛК и применением метода Делаира для построения магических квадратов нечётных порядков не кратных 3 всё ясно.

Для нечётных порядков, являющихся степенью числа 3, группу взаимно ортогональных латинских квадратов можно построить в Maple. В такой группе, как правило, есть диагональные латинские квадраты.

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

В заключение покажу построение магического квадрата 9-го порядка описанным методом (с использованием пары диагональных ОЛК). В качестве пары ОЛК возьму следующую пару (рис. 14):

 

 

Рис. 14

 

Эта пара взята из группы взаимно ортогональных латинских квадратов, составленной в Maple (см. в первой части статьи рис. 20).

На рис. 15 изображён магический квадрат, построенный из данной пары диагональных ОЛК. Это оригинальный магический квадрат.

 

 

Рис. 15

 

В первой части статьи говорилось, что группа из 8 взаимно ортогональных латинских квадратов 9-го порядка, составленная в Maple, содержит 6 диагональных латинских квадратов. Из 6 квадратов можно составить 15 пар диагональных ОЛК. Кроме того, из каждой нормализованной пары можно получить 9! = 362880 вариантов, варьируя перестановку чисел 0, 1, 2, … 8. Посчитайте, сколько магических квадратов можно построить данным методом. Не забудьте ещё, что первый и второй латинские квадраты при построении магического квадрата можно менять местами.

Наконец, данная группа взаимно ортогональных латинских квадратов, составленная в Maple, не единственная. В статье “Handbook of Combinatorial Design” приведено несколько таких групп. Вот одна из них:

 

    123456789    123456789    123456789    123456789    123456789    123456789    123456789    123456789

    231564897    456789123    645978312    897231564    312645978    564897231    789123456    978312645

    312645978    789123456    897231564    645978312    231564897    978312645    456789123    564897231

    456789123    312645978    978312645    564897231    789123456    645978312    231564897    897231564

    564897231    645978312    231564897    312645978    978312645    789123456    897231564    456789123

    645978312    978312645    456789123    789123456    897231564    231564897    564897231    312645978

    789123456    231564897    564897231    978312645    456789123    897231564    312645978    645978312

    897231564    564897231    789123456    456789123    645978312    312645978    978312645    231564897

    978312645    897231564    312645978    231564897    564897231    456789123    645978312    789123456

 

Примечание: латинские квадраты записаны в нетрадиционной форме, то есть с помощью чисел 1, 2, 3 … 9. Я не стала их переводить в традиционную форму записи.

 

Интересно отметить, что в этой группе тоже два не диагональных латинских квадрата, при этом не диагональные квадраты в точности совпадают с не диагональными квадратами группы, построенной в Maple. А вот все 6 диагональных латинских квадратов отличаются от диагональных квадратов первой группы.

Возьмём для примера одну пару диагональных ОЛК из данной группы (рис. 16):

 

 

Рис. 16

 

Построим из данной пары ОЛК магический квадрат.  Этот квадрат показан на рис. 17.

 

 

Рис. 17

 

Получился новый магический квадрат. Сравните его с магическим квадратом на рис. 15. Первые три строки в этих квадратах совпадают. А в общем это совершенно разные магические квадраты.

 

2.2. МЕТОД ЛАТИНСКИХ КВАДРАТОВ ДЛЯ n = 4k

 

Применение метода латинских квадратов для построения магических квадратов чётно-чётного порядка мне нигде не встречалось. В книге Ю. В. Чебракова есть метод построения совершенных квадратов с помощью обобщённых латинских квадратов. Этот метод подробно изложен в статье “Метод построения совершенных квадратов с помощью обобщённых латинских квадратов” (http://www.klassikpoez.narod.ru/latsov.htm ).

Здесь будет рассмотрен метод латинских квадратов применительно к построению магических квадратов порядка n = 4k, k = 1, 2, …

 

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

 

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

Начну с минимального порядка данной серии – 4. На рис. 18 показана пара диагональных ОЛК 4-го порядка.

 

 

Рис. 18

 

Магический квадрат, построенный с помощью этой пары ОЛК, изображён на рис. 19.

 

 

Рис. 19

 

В этом магическом квадрате есть интересное свойство: комплементарные числа расположены симметрично относительно вертикальной оси симметрии квадрата.

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

Перехожу к следующему порядку – 8. Для данного порядка в предыдущей части статьи представлена группа из 7 взаимно ортогональных латинских квадратов. В этой группе только один латинский квадрат не является диагональным, остальные 6 диагональные. Понятно, что из 6 квадратов можно составить 15 пар диагональных ОЛК. Все эти пары нормализованные, следовательно, из каждой пары можно получить 40320 вариантов, варьируя перестановку чисел 0, 1, … 7.

Посмотрим один пример. Пара диагональных ОЛК показана на рис. 20, магический квадрат, построенный из этой пары – на рис. 21.

 

 

Рис. 20

 

 

Рис. 21

 

Как видим, в этом магическом квадрате тоже комплементарные числа расположены симметрично относительно вертикальной оси симметрии квадрата. Это свойство присуще всем магическим квадратам данной группы, так как все взаимно ортогональные латинские квадраты рассматриваемой группы обладают этим свойством.

 

Задача для читателей:

 

 

 

 

 

 

Следующий порядок – 16 – хорош тем, что является степенью числа 2. Группу взаимно ортогональных латинских квадратов можно составить в Maple. В этой группе наверняка будут диагональные латинские квадраты.

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

 

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

 

На рис. 22 показан магический квадрат, построенный из данной пары ОЛК.