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

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

Лати́нский квадра́т — таблица n × n, заполненная n различными символами таким образом, чтобы в каждой строке и в каждом столбце встречались все n символов (каждый по одному разу). Ниже приводятся два примера:

$\begin{bmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \\ 3 & 1 & 2 \\ \end{bmatrix} \quad\quad \begin{bmatrix} a & b & d & c \\ b & c & a & d \\ c & d & b & a \\ d & a & c & b \end{bmatrix}$

Латинские квадраты существуют для любого n. Любой латинский квадрат является таблицей умножения (таблицей Кэли) квазигруппы.

Название "латинский квадрат" берёт начало от Леонарда Эйлера (Leonhard Euler), который использовал латинские буквы вместо цифр в таблице.

Содержание

1 Ортогональные латинские квадраты
2 Использование латинских квадратов для планирования экспериментов
3 Задача о заполнении латинского квадрата
4 См. также

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

Два латинских квадрата называются ортогональными, если различны все пары символов (a,b), где a — символ в некоторой клетке первого латинском квадрата, а b — символ в той же клетке второго латинского квадрата. Пример пары ортогональных латинских квадратов:

$\begin{bmatrix} 2 & 3 & 1 \\ 1 & 2 & 3 \\ 3 & 1 & 2 \\ \end{bmatrix} \quad\quad \begin{bmatrix} 3 & 2 & 1 \\ 2 & 1 & 3 \\ 1 & 3 & 2 \\ \end{bmatrix}$

Ортогональные латинские квадраты существуют для любого порядка n кроме 2 и 6. Для n являющихся степенью простого числа есть набор n-1 взаимно ортогональных латинских квадратов. Это следует из теоремы о том, что набор n-1 взаимно ортогональных латинских квадратов порядка n существует тогда и только тогда, когда существует конечная проективная плоскость порядка n.

[править] Использование латинских квадратов для планирования экспериментов

Предположим, что нужно провести несколько экспериментов, зависящих от 3 параметров 1≤a,b,c≤n, так чтобы для каждой пары параметров были опробованы все n² вариантов. Тогда нужно взять любой латинский квадрат порядка n и провести n² экспериментов с параметрами a = номер строки, b = номер столбца, c = значение в клетке латинского квадрата.

[править] Задача о заполнении латинского квадрата

Пусть дана таблица n × n, в которой некоторые ячейки пусты, а в некоторых стоят числа от 1 до n. Задача о заполнении латинского квадрата формулируется так: существует ли способ вписать числа в пустые ячейки так, чтобы полученная таблица стала латинским квадратом.

Задача о заполнении латинского квадрата NP-полна.