Введение

Квадратный массив с символами, каждый из которых встречается ровно один раз в каждой строке и в каждом столбце. В комбинаторике и в экспериментальном дизайне латинский квадрат представляет собой массив n × n, заполненный n различными символами, каждый из которых встречается ровно один раз в каждой строке и ровно один раз в каждом столбце. Пример латинского квадрата 3×3:

A B C
C A B
B C A

Название "латинский квадрат" было вдохновлено математическими работами Леонарда Эйлера (1707–1783), который использовал латинские символы, но можно использовать любой набор символов: в приведенном выше примере алфавитная последовательность A, B, C может быть заменена числовой последовательностью 1, 2, 3. Эйлер заложил основы общей теории латинских квадратов.

История

Корейский математик Чхве Сёк Чжон первым опубликовал пример латинского квадрата девятого порядка для построения магического квадрата в 1700 году, на 67 лет раньше, чем Леонард Эйлер.

Поперечные и радужные сочетания

Поперечный в латинском квадрате — это выбор из n ячеек, где каждая строка содержит одну ячейку, каждый столбец содержит одну ячейку, и есть одна ячейка, содержащая каждый символ. Латинский квадрат можно рассматривать как полный двудольный граф, в котором строки — вершины одной доли, столбцы — вершины другой доли, каждая ячейка — ребро (между своей строкой и своим столбцом), а символы — цвета. Правила латинских квадратов подразумевают, что это корректное раскрашивание рёбер. При этом определении латинский поперечный — это паросочетание, в котором каждое ребро имеет разный цвет; такое паросочетание называется радужным паросочетанием. Поэтому многие результаты по латинским квадратам/прямоугольникам содержатся в работах с термином «радужное паросочетание» в их названии, и наоборот. Некоторые латинские квадраты не имеют поперечного. Например, когда n чётно, латинский квадрат размера n × n, в котором значение ячейки (i, j) равно (i + j) mod n, не имеет поперечного. Вот два примера: в 1967 году Х. Дж. Райзер предположил, что, когда n нечётно, каждый латинский квадрат размера n × n имеет поперечный. В 1975 году С. К. Штейн и Бруальди предположили, что, когда n чётно, каждый латинский квадрат размера n × n имеет частичный поперечный размера n − 1. Более общая гипотеза Штейна заключается в том, что поперечный размера n − 1 существует не только в латинских квадратах, но и в любом массиве размера n × n, состоящем из n символов, если каждый символ встречается ровно n раз. Каждый латинский квадрат размера n × n имеет частичный поперечный размера n − √n. Каждый латинский квадрат размера n × n имеет частичный поперечный размера n − 11 log n. Каждый латинский квадрат размера n × n имеет частичный поперечный размера n − O(log n / log log n). Каждый достаточно большой латинский квадрат размера n × n имеет частичный поперечный размера n − 1. (Препринт)

Алгоритмы

Для небольших квадратов можно генерировать перестановки и проверять, удовлетворяют ли они свойству латинского квадрата. Для больших квадратов алгоритм Якобсона и Мэтьюса позволяет получать выборки из равномерного распределения по множеству латинских квадратов размера n × n.

Статистика и математика

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

Математические головоломки

Проблема определения того, можно ли частично заполненный квадрат дополнить до латинского квадрата, является NP-полной. Популярные головоломки Судоку являются частным случаем латинских квадратов; любое решение головоломки Судоку представляет собой латинский квадрат. Судоку накладывает дополнительное ограничение, что девять определенных смежных подквадратов 3×3 также должны содержать цифры от 1 до 9 (в стандартной версии). См. также «Математика Судоку». Более новые головоломки КенКен и Стримко также являются примерами латинских квадратов.

Настольные игры

Латинские квадраты использовались в качестве основы для ряда настольных игр, в частности, популярной абстрактной стратегической игры Kamisado.

Агрономические исследования

Латинские квадраты используются при планировании агрономических экспериментов для минимизации экспериментальных ошибок.

Геральдика

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

Обобщения

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