Греко-латинський квадрат

Греко-латинський квадрат - квадрат N N в кожній клітині якого стоять 2 числа від 1 до N так, що виконуються наступні умови:

  1. У кожному рядку і стовпці кожна цифра зустрічається один раз на першому місці в парі, і один раз на другому
  2. Кожна цифра стоїть в парі з кожної іншою цифрою і з самою собою по одному разу

Такі квадрати, як видно і з назви, тісно пов'язані з латинськими квадратами, для яких виконується лише перше правило, і в кожному осередку якого стоїть тільки одне число. Сама назва і тих і інших квадратів пішло від Ейлера який використовував замість цифр грецькі і латинські літери.

Греко-латинський квадрат можна розглядати як накладання двох ортогональних латинських квадратів.

Приклад

a b c d
b a d c
c d a b
d c b a
α β γ δ
γ δ α β
δ γ β α
β α δ γ
Греко-латинський квадрат, отриманий накладенням двох латинських квадратів вище

Історія

Займаючись греко-латинськими квадратами Ейлер довів, що квадратів другого порядку не існує, зате були знайдені квадрати 3, 4, і 5 порядків. Квадрата 6 порядку виявити не вдалося, але довести, що їх не існує, Ейлеру не вдалося. Але їм була висловлена ​​гіпотеза, що не існує квадрата порядку N, якщо N - парне число, не ділиться на 4 (тобто 6, 10, 14 і т. д.). В 1901 гіпотеза була підтверджена для N = 6 математиком Гастоном Террі. Це було зроблено перебором всіх можливих варіантів квадрата. А в 1959 гіпотеза була спростована Е. Т. Паркером, Р. К. Боус і С. С. Шрікхердом, що виявили квадрат порядку 10

00 47 18 76 29 93 85 34 61 52
86 11 57 28 70 39 94 45 02 63
95 80 22 67 38 71 49 56 13 04
59 96 81 33 07 48 72 60 24 15
73 69 90 82 44 17 58 01 35 26
68 74 09 91 83 55 27 12 46 30
37 08 75 19 92 84 66 23 50 41
14 25 36 40 51 62 03 77 88 99
21 32 43 54 65 06 10 89 97 78
42 53 64 05 16 20 31 98 79 87

Після були виявлені квадрати 14, 18 і т. д. порядків.


Задачі про греко-латинських квадратах

Сам Ейлер поставив завдання про знаходження квадрата 6 порядку так:

У 6 полицях є 36 офіцерів 6 різних звань. Потрібно так розмістити їх в каре щоб всі офіцери в кожній колоні і шерензі були різних звань і з різних полків. Як вже було зазначено таке завдання нерозв'язна.

Інше завдання звучить так:

потрібно розкласти 16 карток (валети, дами, королі і тузи різних мастей) так щоб в кожному ряду і стовпці було по одній карті кожній масті і значення. Ця задача була відома ще до Ейлера. Її рішенням буде будь греко-римський квадрат порядку 4. Також для цієї задачі є варіанти в яких вимагається, щоб на головних діагоналях виконувалися ті ж вимоги. В іншому варіанті потрібно щоб кольори мастей йшли в шаховому порядку. Всі ці завдання мають рішення.

Застосування греко-латинських квадратів

Якщо є система, на яку діють 4 різних параметра (наприклад вплив N різних рекламних роликів на населення N різних вікових, соціальних та етнічних груп), які можуть приймати по N значень потрібно розглянути греко-латинську квадрат порядку N. Тоді параметри будуть відповідати ряду, стовпцю, першого і другого числа. таким чином можна провести N ^ 2 експериментів, замість N ^ 4 (У разі повного перебору варіантів)