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

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

1. В каждой строке и столбце каждая цифра встречается один раз на первом месте в паре, и один раз на втором
2. Каждая цифра стоит в паре с каждой другой цифрой и с самой собой по одному разу

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

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

Пример

a b c d b a d c c d a b d c b a

α β γ δ γ δ α β δ γ β α β α δ γ

Греко-латинский квадрат, полученный наложением двух латинских квадратов выше

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$(в случае полного перебора вариантов)