Латинский квадрат

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Лати́нский квадра́т n-го порядка — таблица L=(lij) размеров n × n, заполненная n элементами множества M таким образом, что в каждой строке и в каждом столбце таблицы каждый элемент из M встречается в точности один раз. Пример латинского квадрата 3-го порядка:


\begin{bmatrix}
A & B & C \\
C & A & B \\
B & C & A \\
\end{bmatrix}

В настоящее время в качестве множества M обычно берется множество натуральных чисел {1,2,…,n} или множество {0,1,…,n-1}, однако Леонард Эйлер использовал буквы латинского алфавита, откуда латинские квадраты и получили своё название.[1]

Латинские квадраты существуют для любого n, достаточно взять таблицу Кэли аддитивной группы кольца \mathbb{Z}_n: lij= (i+j-1) mod n.

История исследований латинских квадратов[править | править исходный текст]

Окно в честь Фишера с латинским квадратом 7-го порядка. Кембридж

Впервые латинские квадраты (4-го порядка) были опубликованы в книге «Шамс аль Маариф» («Книга о Солнце Гнозиса»), написанной Ахмадом аль-Буни в Египте приблизительно в 1200 году.

Пары ортогональных латинских квадратов впервые были упомянуты J. Ozanam в 1725 году.[2] В книге, представляющей собой сборник задач по физике и математике, приведена следующая задача:

Необходимо разместить 16 игральных карт из тузов, королей, дам и валетов всех четырёх мастей в виде квадрата так, чтобы все масти и карты всех достоинств встречались в каждой строке и в каждом столбце ровно один раз.

Эта задача имеет 6192 решения (если дополнительно потребовать, чтобы и диагонали квадрата удовлетворяли тому же условию, то число решений уменьшится в 6 раз и станет равным 1152).

Важной вехой в истории исследований латинских квадратов стала работа Эйлера.[1] Он занимался в ней методами построения магических квадратов и предложил метод, основанный на паре ортогональных латинских квадратов. Исследуя такие пары, Эйлер выяснил, что проблема их построения подразделяется на три случая в зависимости от остатка от деления числа n на 4. Он предложил способы построения пар ортогональных квадратов для n, делящихся на 4 и для нечетных n. Очевидно, что при n = 2 таких пар не существует. Ему не удалось построить пары ортогональных латинских для n = 6, 10 и он высказал гипотезу о том, что не существует пар ортогональных квадратов для n = 4t+2. Для n = 6 он сформулировал «задачу о 36 офицерах»:

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

В 1890 году Кэли вывел формулу для числа латинских прямоугольников из двух строк (частный случай классической комбинаторной «задачи о встречах», поставленной P. Montmort в 1708 году).[3]

В 1900 году гипотеза Эйлера для n = 6 была подтверждена G. Tarry.[4] Он построил все 9408 нормализованных латинских квадратов, разбил их на 17 типов и показал, что при любом их сочетании невозможно построить пару ортогональных квадратов. Таким образом, он отрицательно решил «задачу о 36 офицерах».

В 1922 году MacNeish впервые применил теоретико-групповой подход к решению задач относительно латинских квадратов.[5] В частности, он предложил метод конструирования латинских квадратов порядка n1•n2 из латинских квадратов порядков n1 и n2, при этом свойство ортогональности сохраняется.

В 1925 году Fisher предложил использовать ортогональные латинские квадраты для планирования сельскохозяйственных экспериментов.[6]

В 1920—1930 годы стали интенсивно изучаться неассоциативные алгебраические структуры, что привело, в частности, к созданию теории квазигрупп, тесно связанной с изучением латинских квадратов, так как между латинскими квадратами и таблицами Кэли квазигрупп существует взаимно-однозначное соответствие.

В 1959 году Bose и Shrikhande построили 2 ортогональных латинских квадрата для n = 22, а в 1960 году они же и Parker построили с использованием ЭВМ минимальный контрпример для n = 10. Таким образом, спустя 177 лет гипотеза Эйлера была опровергнута.[7]

Число латинских квадратов[править | править исходный текст]

Точная формула для числа L(n) латинских квадратов n-го порядка неизвестна. Наилучшие оценки для L(n) дает формула

 \prod_{k=1}^n \left(k!\right)^{n/k}\geq L(n)\geq\frac{\left(n!\right)^{2n}}{n^{n^2}}[8]

Каждому латинскому квадрату можно поставить в соответствие нормализованный (или редуцированный) латинский квадрат, у которого первая строка и первый столбец заполнены в соответствии с порядком, заданном на множестве M. Пример нормализованного латинского квадрата:


\begin{bmatrix}
A & B & C \\
B & C & A \\
C & A & B \\
\end{bmatrix}

Число R(n) нормализованных латинских квадратов n-го порядка в n!(n-1)! раз меньше, чем L(n).

Точные значения величины L(n) известны для n от 1 до 11:[9]

Число латинских квадратов
n R(n) L(n) Автор и год
1 1 1
2 1 2
3 1 12
4 4 576
5 56 161280 Euler (1782)
6 9408 812851200 Frolov (1890)
7 16942080 61479419904000 Sade (1948)
8 535281401856 108776032459082956800 Wells (1967)
9 377597570964258816 5524751496156892842531225600 Bammel и Rothstein (1975)
10 7580721483160132811489280 9982437658213039871725064756920320000 McKay и Rogoyski (1995)
11 5363937773277371298119673540771840 776966836171770144107444346734230682311065600000 McKay и Wanless (2005)

Отношения эквивалентности на множестве латинских квадратов[править | править исходный текст]

Два латинских квадрата называют изотопными, если один из них может быть получен из другого в результате изотопии – композиции из перестановки строк, перестановки столбцов и замены элементов множества M по подстановке из симметрической группы S(M).

Изотопия является отношением эквивалентности, поэтому множество латинских квадратов n-го порядка разбивается на непересекающиеся изотопические классы. Из одного латинского квадрата можно получить с помощью изотопии (n!)3 эквивалентных, но некоторые из них при этом могут совпасть с исходным, это называется автопаратопией. Доля латинских квадратов с нетривиальной группой автопаратопий стремится к нулю с ростом n.[9]

Латинский квадрат можно рассматривать как ортогональный массив. Меняя порядок элементов в каждой упорядоченной тройке этого массива, можно получить 6 латинских квадратов, которые называются парастрофами. В частности, парастрофом является латинский квадрат, полученный в результате транспонирования.

Композиция изотопии и парастрофии называется изострофией. Это ещё одно отношение эквивалентности, его классы называются главными классами. Каждый главный класс содержит 1, 2, 3 или 6 изотопических классов. В случае совпадения исходного латинского квадрата и изострофного ему, говорят об автострофии. С ростом n почти все латинские квадраты имеют тривиальную группу автострофий.[10]

Число классов эквивалентности
n Число главных классов Число изотопических классов
1 1 1
2 1 1
3 1 1
4 2 2
5 2 2
6 12 22
7 147 564
8 283657 1676267
9 19270853541 115618721533
10 34817397894749939 208904371354363006
11 2036029552582883134196099 12216177315369229261482540

Ортогональные латинские квадраты[править | править исходный текст]

Два латинских квадрата L=(lij) и K=(kij) n-го порядка называются ортогональными, если все упорядоченные пары (lij,kij) различны. Пример двух ортогональных латинских квадратов и соответствующие им упорядоченные пары:


\begin{bmatrix}
1 & 2 & 3 \\
2 & 3 & 1 \\
3 & 1 & 2 \\
\end{bmatrix}
\quad\quad
\begin{bmatrix}
1 & 2 & 3 \\
3 & 1 & 2 \\
2 & 3 & 1 \\
\end{bmatrix}
\quad\quad
\begin{bmatrix}
(1,1) & (2,2) & (3,3)\\
(2,3) & (3,1) & (1,2)\\
(3,2) & (1,3) & (2,1)\\
\end{bmatrix}

Эйлер называл такие квадраты "полными". В его честь в научной литературе их раньше называли "эйлеровыми" или "греко-латинскими" (так как Эйлер использовал буквы греческого алфавита для квадрата, ортогонального латинскому).

Ортогональные латинские квадраты существуют для любого n, не равного 2 и 6.

Латинский квадрат L n-го порядка имеет ортогональный ему квадрат тогда и только тогда, когда в L существует n непересекающихся трансверсалей.

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

При n, стремящемуся к ∞, величина N(n) тоже стремится к ∞.

Для n, являющегося степенью простого числа, всегда существует полное множество попарно ортогональных латинских квадратов, его можно взаимооднозначно сопоставить с конечной проективной плоскостью порядка n. Для его построения применяется метод Боуза, использующий для заполнения квадратов значения многочленов вида fa(x,y)=ax+y при ненулевом a над полем \mathrm{GF}(n).[11] Пример построения полного множества попарно ортогональных латинских квадратов 4-ого порядка (d – корень примитивного многочлена x2+x+1 над \mathrm{GF}(2)):


\begin{bmatrix}
0 & 1 & d & d+1\\
1 & 0 & d+1 & d\\
d & d+1 & 0 & 1\\
d+1 & d & 1 & 0\\
\end{bmatrix}
\quad\quad
\begin{bmatrix}
0 & 1 & d & d+1\\
d & d+1 & 0 & 1\\
d+1 & d & 1 & 0\\
1 & 0 & d+1 & d\\
\end{bmatrix}
\quad\quad
\begin{bmatrix}
0 & 1 & d & d+1\\
d+1 & d & 1 & 0\\
1 & 0 & d+1 & d\\
d & d+1 & 0 & 1\\
\end{bmatrix}

Если n ≡ 1 (mod 4) или n ≡ 2 (mod 4) и свободная от квадрата часть числа n содержит хотя бы один простой множитель p ≡ 3 (mod 4), то для таких n полного множества попарно ортогональных латинских квадратов не существует.

Известные нижние оценки числа N(n) при n < 33 приведены в следующей таблице (выделены оценки, которые могут быть улучшены):

Нижние оценки числа N(n)
n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
N(n)≥ 2 3 4 6 7 8 2 10 5 12 3 4 15 16 3 18 4 5 3 22 6 24 4 26 5 28 4 30 31

Построение ортогональных квадратов – сложная комбинаторная задача. Для её решения применяются как алгебраические конструкции, так и комбинаторные (трансверсали, ортогональные массивы, дизайны, блок-схемы, тройки Штейнера и др.) Существует несколько подходов к решению этой задачи, их можно разделить на две группы. К первой группе относятся методы, основанные на выборе базового латинского квадрата, к которому отыскиваются изотопные ортогональные латинские квадраты. Например, пять попарно ортогональных латинских квадратов 12-го порядка были найдены в результате построения четырех ортоморфизмов абелевой группы, являющейся прямым произведением циклических групп порядков 6 и 2.[12]

Ко второй группе относятся методы, использующие для построения ортогональных латинских квадратов комбинаторные объекты (включая сами латинские квадраты) меньших порядков. Например, два латинских квадрата 22-го порядка были построены Bose и Shrikhande на основе двух дизайнов 15-го и 7-го порядка.

Частичные квадраты[править | править исходный текст]

Квадрат, в котором каждый элемент множества M в каждой строке и в каждом столбце встречается не более одного раза, называется частичным.

Задача распознавания того, может ли частичный квадрат быть дополнен до латинского, является NP-полной.

Введено понятие критического множества, соответствующего частичному квадрату, который однозначно может быть дополнен до латинского, причем никакое его подмножество условию однозначности не удовлетворяет.[13] Мощность C(n) критического множества для квадратов размеров n × n известна для n < 7:

Мощность критического множества
n 1 2 3 4 5 6
С(n) 0 1 3 7 11 18

Нерешенные задачи[править | править исходный текст]

Помимо задачи нахождения формулы для величины L(n), имеется большое количество нерешенных задач относительно латинских квадратов. Ряд таких задач был сформулирован на конференции Loops'03:

  • Оценка максимального числа трансверсалей в латинском квадрате n-го порядка
  • Характеризация латинских подквадратов в таблице умножения луп Муфанг
  • Оценка плотности частичного квадрата, удовлетворяющего свойству Блэкберна
  • Вычисление максимального t(n), при котором 2t(n) делит величину L(n)

Применение[править | править исходный текст]

Пример использования латинского квадрата в филателии

Латинские квадраты находят широкое применение в алгебре, комбинаторике, статистике, криптографии, теории кодов и многих других областях.

Игры и головоломки с латинскими квадратами[править | править исходный текст]

Существует ряд игр, в которых используются латинские квадраты. Наиболее известна из них судоку. В ней требуется частичный квадрат дополнить до латинского квадрата 9-го порядка, обладающего дополнительным свойством: все девять его подквадратов содержат по одному разу все натуральные числа от 1 до 9.

Пользуются популярностью также задачи построения латинских квадратов и на их основе магических квадратов, обладающих дополнительными свойствами (например, диагональные квадраты).

См. также[править | править исходный текст]

Примечания[править | править исходный текст]

  1. 1 2 Euler L. Recherches sur une nouvelle espèce de quarrés magiques. — Middelburg, 1782.
  2. Ozanam J. Récréations mathématiques et physiques. — Paris, 1725.
  3. Cayley A. On Latin Squares // Messenger of mathematics. — 1890. — Т. XIX. — С. 135–137.
  4. Tarry G. Le problème des 36 officiers // Comptes Rendus Assoc. France Av. Sci.. — 1900. — Т. 29, part 2. — С. 170–203.
  5. MacNeish, Harris F. Euler Squares // Annals of Mathematics. — 1922. — Т. 23. — С. 221–227.
  6. Fisher R. A. Statistical methods for research workers. — Edinburg, London: Oliver & Boyd, 1925.
  7. Bose R. C.; Shrikhande S. S. On the falsity of Euler’s conjecture about the non-existence of two orthogonal Latin squares of order 4t + 2 // Proc. Nat. Acad. Sci. U.S.A.. — 1959. — Т. 45. — С. 734–737.
  8. van Lint J. H., Wilson R. M. A Course in Combinatorics. — Cambridge University Press, 1992.
  9. 1 2 McKay B. D., Wanless I. M. On the number of Latin Squares // Ann. Combin.. — 2005. — Т. 9. — С. 335-344.
  10. Черемушкин А. В. Почти все латинские квадраты имеют тривиальную группу автострофий // Прикладная дискретная математика. — 2009. — Т. 3(5). — С. 29–32.
  11. Bose R.S. On the applications of the properties of Galois fields to the problems of construction of Hyper-Graeco-Latin squares // Indian J. Stat.. — 1938. — Т. № 3. Part. 4. — С. 323–338.
  12. Dulmage A. L., Johnson D., Mendelsohn N. S. Orthomorphisms of groups and orthogonal Latin squares I // Canad. J. Math.. — 1961. — Т. 13. — С. 356–372.
  13. Nelder J. Critical sets in latin squares // CSIRO Division of Math. and Stats. — 1977. — Т. Newsletter, 38.

Литература[править | править исходный текст]

  • Холл М. Комбинаторика, пер. с англ. М. 1970.
  • Dénes J. H., Keedwell A. D. Latin Squares and their Applications. Budapest. 1974.
  • Сачков В. Н. Комбинаторные методы дискретной математики. М. 1977.
  • Dénes J. H., Keedwell A. D. Latin squares: New developments in the theory and applications. Annals of Discrete Mathematics vol. 46. Academic Press. Amsterdam. 1991.
  • Laywine C.F., Mullen G.L. Discrete mathematics using Latin squares. New York. 1998.
  • Малых А. Е., Данилова В. И. Об историческом процессе развития теории латинских квадратов и некоторых их приложениях // Вестник Пермского Университета. 2010. Вып. 4(4). С. 95-104.
  • Тужилин М. Э. Об истории исследований латинских квадратов // Обозрение прикладной и промышленной математики. 2012. Том 19, выпуск 2. С. 226—227.