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

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

Греко-латинский квадрат — квадрат 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 порядка обнаружить не удалось, но доказать, что их не существует, Эйлеру не удалось. Но им была высказана гипотеза, что не существует квадрата порядка 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 96 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. Тогда параметры будут соответствовать ряду, столбцу, первому и второму числу. таким образом можно провести N2 эксперементов, вместо N4(в случае полного перебора вариантов)



Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Полезное


Смотреть что такое "Греко-латинские квадраты" в других словарях:

  • ОРТОГОНАЛЬНЫЕ ЛАТИНСКИЕ КВАДРАТЫ — пара латинских квадратов А=|| а ij||, В=||bij|| порядка птаких, что при . Квадраты Аи В наз. ортогональными соквадратами. Матрица, получаемая наложением Ана В, наз. греко латинским, или эйлеровым, квадратом, ее элементы все и 2 упорядоченных пар… …   Математическая энциклопедия

  • ГРЕКО-ЛАТИНСКИЙ КВАДРАТ — См. латинские квадраты …   Толковый словарь по психологии

  • Греко-латинский квадрат — Греко латинский квадрат  квадрат N×N в каждой клетке которого стоят 2 числа от 1 до N так, что выполняются следующие условия: В каждой строке и столбце каждая цифра встречается один раз на первом месте в паре, и один раз на втором Каждая… …   Википедия

  • Латинский квадрат — n го порядка  таблица L=(lij) размеров n × n, заполненная n элементами упорядоченного множества M таким образом, что в каждой строке и в каждом столбце таблицы каждый элемент из M встречается в точности один раз. Пример латинского квадрата 3 …   Википедия

  • Византия* — Содержание: Византия колония. Византийская империя. Византийская литература. Византийское право. Византийское искусство. Византийская монета. Византия (Βυζάντιον, Byzantium) мегарская колония, основанная в 658 г. на европейской стороне Босфора.… …   Энциклопедический словарь Ф.А. Брокгауза и И.А. Ефрона

  • Византия — Содержание: Византия колония. Византийская империя. Византийская литература. Византийское право. Византийское искусство. Византийская монета. Византия (Βυζάντιον, Byzantium) мегарская колония, основанная в 658 г. на европейской стороне Босфора.… …   Энциклопедический словарь Ф.А. Брокгауза и И.А. Ефрона

  • ВИЗАНТИЙСКАЯ ИМПЕРИЯ. ЧАСТЬ II — Право и Церковь Рецепция римского права в Византии. Понятие византийского права Правовая культура В. и. с начала ее истории вплоть до падения К поля была основана на рецепции классического римского права. Источники рим. права подразделялись на… …   Православная энциклопедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»