Remove ads

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

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

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

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

Пример

abcd
badc
cdab
dcba
αβγδ
γδαβ
δγβα
βαδγ
Подробнее aα, bβ ...
Греко-латинский квадрат, полученный наложением двух латинских квадратов выше
Закрыть
Remove ads

История

Занимаясь греко-латинскими квадратами, Эйлер без труда выяснил, что квадратов второго порядка не существует, затем он построил квадраты порядков 3, 4, и 5. Квадрата 6-го порядка ему обнаружить не удалось, и Эйлер высказал гипотезу, что квадратов с порядком вида не существует (например, порядка 6, 10, 14 и т. д.). В 1901 году гипотеза Эйлера была доказана для французским математиком Гастоном Тарри, который перебрал все возможные варианты такого квадрата. Однако в 1959 году гипотеза была опровергнута двумя индийскими математиками — Р. К. Боузом и С. С. Шриханде, обнаружившими при помощи ЭВМ квадрат порядка 22, и американским математиком Э. Т. Паркером, который нашёл квадрат 10-го порядка.

00471876299385346152
86115728703994450263
95802267387149561304
59968133074872602415
73699082441758013526
68740991835527124630
37087519928466235041
14253640516203778899
21324354650610899778
42536405162031987987

Позднее были обнаружены квадраты 14, 18 и т. д. порядков. В совместной статье (апрель 1959 года) трое названных выше первооткрывателей показали, что существуют греко-латинские квадраты любого порядка, кроме 2-го и 6-го.

Remove ads

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

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

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

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

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

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

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

Remove ads

Wikiwand in your browser!

Seamless Wikipedia browsing. On steroids.

Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.

Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.

Remove ads