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

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

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

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

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

Пример

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=4k+2$ не существует (например, порядка 6, 10, 14 и т. д.). В 1901 году гипотеза Эйлера была доказана для $N=6$ французским математиком Гастоном Тарри, который перебрал все возможные варианты такого квадрата. Однако в 1959 году гипотеза была опровергнута двумя индийскими математиками — Р. К. Боузом и С. С. Шриханде, обнаружившими при помощи ЭВМ квадрат порядка 22, и американским математиком Э. Т. Паркером, который нашёл квадрат 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 и т. д. порядков. В совместной статье (апрель 1959 года) трое названных выше первооткрывателей показали, что существуют греко-латинские квадраты любого порядка, кроме 2-го и 6-го.

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

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

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

Другая задача звучит так:

нужно разложить 16 карт (валеты, дамы, короли и тузы разных мастей) так, чтобы в каждом ряду и столбце было по одной карте каждой масти и значения. Эта задача была известна ещё до Эйлера. Её решением будет любой греко-латинский квадрат порядка 4. Для этой задачи также есть варианты, в которых дополнительно требуется, чтобы на главных диагоналях выполнялись те же требования. В другом варианте требуется, чтобы цвета мастей шли в шахматном порядке. Все эти задачи имеют решения.

Применение греко-латинских квадратов

Если есть система, на которую действуют 4 различных параметра (например воздействие N различных рекламных роликов на население N различных возрастных, социальных и этнических групп), которые могут принимать по N значений, нужно рассмотреть греко-латинский квадрат порядка N. Тогда параметры будут соответствовать ряду, столбцу, первому и второму числу. Таким образом можно провести $N^{2}$ экспериментов, вместо $N^{4}$ (в случае полного перебора вариантов)

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.