WikiSort.ru - Не сортированное

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

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

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

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

Пример

История

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

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

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

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

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

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

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

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

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

Это заготовка статьи по математике. Вы можете помочь проекту, дополнив её.