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

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

Гре́ко-лати́нский квадра́т, или э́йлеров квадра́т, — квадрат 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-го порядка ему обнаружить не удалось, и Эйлер высказал гипотезу, что квадратов с порядком вида не существует (например, порядка 6, 10, 14 и т. д.). В 1901 году гипотеза Эйлера была доказана для французским математиком Гастоном Тарри, который перебрал все возможные варианты такого квадрата. Однако в 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. Тогда параметры будут соответствовать ряду, столбцу, первому и второму числу. Таким образом можно провести экспериментов, вместо (в случае полного перебора вариантов)