Магические и латинские квадраты. Латинские квадраты

9. Сомнительные квадраты Учитель черчения задал школьнику работу: начертить два равных квадрата и заштриховать их. Школьник выполнил работу так, как показано на рис. 5. Он был уверен, что это квадраты и притом равные.Почему он так

Квадраты смерти

Квадраты смерти Для уничтожения военной машины сербов в Косово специалистам оперативного центра пришлось разработать новую систему обнаружения и идентификации целей на театре военных действий с быстро и хаотически меняющейся обстановкой. Америки операторы центра не

6. ПЛАНЫ ДЛЯ ОЦЕНКИ ВЛИЯНИЯ ФАКТОРОВ

6.1. Планы на латинских квадратах

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

Таким образом, существует параметры (характеристики), принимающие некоторое ограниченное количество значений, задаваемых в количественной или качественной шкале измерений. Необходимо в условиях воздействия других факторов оценить влияние таких параметров на показатель качества системы или определить их значимость. Полный перебор возможных сочетаний параметров системы потребует чрезмерно большого количества опытов. С целью рационального сокращения экспериментальных исследований применяют специальный вид планов – планы на латинских квадратах.

Латинский квадрат характеризуется особым расположением некоторого числа символов в ячейках, сгруппированных в строки и столбцы так, что каждый символ встречается один раз в каждой строке и в каждом столбце. Пример латинского квадрата, размером n ×n , для n = 3 представлен в табл. 6.1.

Таблица 6.1

Для любого n > 2 существует множество вариантов построения латинских квадратов. Количество вариантов латинских квадратов с ростом n быстро увеличивается и определяется формулой

N (n , n ) = n !(n – 1)!L (n ).

Некоторые значения L (n ) представлены в табл. 6.2.

Таблица 6.2

Латинскому квадрату можно сопоставить план эксперимента, в котором строки соответствуют различным значениям одного фактора, столбцы – значениям другого, а латинские буквы – значениям третьего фактора, т.е. латинский квадрат позволяет исследовать влияние не более чем трех факторов. Пример представления латинского квадрата для факторов L , P , Z , каждый из которых варьируется на четырех уровнях (n = 4) приведен в табл. 6.3.

Таблица 6.3

Применение плана, построенного на основе латинского квадрата, позволяет оценить дифференциальный (разностный) эффект пар уровней, но не дает информации о взаимодействии между факторами (иначе говоря, факторы не зависят друг от друга). Так, сумма результатов экспериментов, соответствующих столбцу j , будет оценивать эффект P j , усредненный по всем L и Z . Тогда дифференциальный эффект увеличения значения фактора P от уровня 1 до уровня 2, усредненный по всем L и Z , можно оценить по разности между суммой значений функции отклика столбца 2 и столбца 1. Порядок перечисления уровней факторов роли не играет.

В частности, рассмотренный план позволяет оценить влияние размера видеопамяти графического адаптера (P ) на скорость вывода видеоизображений при различном быстродействии (L ) процессора компьютера и разном разрешении дисплея (Z ). Применительно к рассмотренному примеру для трех факторов при четырех уровнях варьирования ПФЭ требует 4 3 = 64 опытов, а с применением латинского квадрата – только 16. Экономия достигается за счет потери информации о взаимодействии факторов.

В условиях применения латинского квадрата все факторы должны варьироваться на одинаковом количестве уровней. Можно ослабить это требование путем приравнивания какого-либо уровня другому.

Приведенный пример является одним из возможных расположений уровней факторов, позволяющих получить несмещенные оценки главных эффектов. Латинские квадраты можно накладывать друг на друга, образуя греко-латинские квадраты . Например, два латинских квадрата 3´3 можно преобразовать в греко-латинский квадрат

Здесь латинские буквы образуют один латинский квадрат, а греческие буквы – другой латинский квадрат. Каждая латинская буква встречается в паре с конкретной греческой буквой только один раз. С помощью этого греко-латинского квадрата можно оценить главные эффекты четырех 3-х уровневых факторов (фактора строк, фактора столбцов, римских букв и греческих букв) проведя только 9 опытов.

Если наложить друг на друга три различных варианта латинских квадратов, то получится план гипер-греко-латинского квадрата . С его помощью можно оценить главные эффекты пяти факторов (фактора строк, столбцов и трех расположений квадратов). В частности, для пяти трехуровневых факторов потребуется провести только 9 опытов вместо 243 опытов при переборе всех возможных сочетаний факторов.

Итак, планы латинских (греко-латинских) квадратов используются в тех случаях, когда требуется оценить влияние факторов, варьируемых более чем на двух уровнях и заранее известно, что между факторами нет взаимодействий или этим взаимодействиями можно пренебречь. Имеются таблицы латинских и греко-латинских квадратов различных размеров, за исключением одного практически важного случая – не существует греко-латинского квадрата для 6 уровней факторов.

Лати́нский квадра́т n -го порядка - таблица L=(l ij) размеров n × n , заполненная n элементами множества M таким образом, что в каждой строке и в каждом столбце таблицы каждый элемент из M встречается в точности один раз. Пример латинского квадрата 3-го порядка:

Впервые латинские квадраты (4-го порядка) были опубликованы в книге «Шамс аль Маариф» («Книга о Солнце Гнозиса»), написанной Ахмадом аль-Буни в Египте приблизительно в 1200 году.

Пары ортогональных латинских квадратов впервые были упомянуты Жаком Озанамом в 1725 году . В книге, представляющей собой сборник задач по физике и математике, приведена следующая задача:

Эта задача имеет 6912 решений (если дополнительно потребовать, чтобы и диагонали квадрата удовлетворяли тому же условию, то число решений уменьшится в 6 раз и станет равным 1152).

Важной вехой в истории исследований латинских квадратов стала работа Эйлера . Он занимался в ней методами построения магических квадратов и предложил метод, основанный на паре ортогональных латинских квадратов. Исследуя такие пары, Эйлер выяснил, что проблема их построения подразделяется на три случая в зависимости от остатка от деления числа n на 4. Он предложил способы построения пар ортогональных квадратов для n , делящихся на 4 и для нечётных n . Очевидно, что при n = 2 таких пар не существует. Ему не удалось построить пары ортогональных латинских квадратов для n = 6, 10 и он высказал гипотезу о том, что не существует пар ортогональных квадратов для n = 4t +2. Для n = 6 он сформулировал «задачу о 36 офицерах»:

В 1920-1930 годы стали интенсивно изучаться неассоциативные алгебраические структуры, что привело, в частности, к созданию теории квазигрупп , тесно связанной с изучением латинских квадратов, так как между латинскими квадратами и таблицами Кэли квазигрупп существует взаимно-однозначное соответствие.

Точная формула для числа L (n ) латинских квадратов n -го порядка неизвестна. Наилучшие оценки для L (n ) дает формула

Каждому латинскому квадрату можно поставить в соответствие нормализованный (или редуцированный) латинский квадрат, у которого первая строка и первый столбец заполнены в соответствии с порядком, заданном на множестве M . Пример нормализованного латинского квадрата:

Число R(n) нормализованных латинских квадратов n -го порядка (последовательность A000315 в OEIS) в n!(n-1)! раз меньше, чем L(n) (последовательность A002860 в OEIS).

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

Латинский квадрат можно рассматривать как ортогональный массив . Меняя порядок элементов в каждой упорядоченной тройке этого массива, можно получить 6 латинских квадратов, которые называются парастрофами. В частности, парастрофом является латинский квадрат, полученный в результате транспонирования.

Композиция изотопии и парастрофии называется изострофией. Это ещё одно отношение эквивалентности, его классы называются главными классами. Каждый главный класс содержит 1, 2, 3 или 6 изотопических классов. В случае совпадения исходного латинского квадрата и изострофного ему, говорят об автострофии. С ростом n почти все латинские квадраты имеют тривиальную группу автострофий.

Два латинских квадрата L=(l ij) и K=(k ij) n -го порядка называются ортогональными, если все упорядоченные пары (l ij ,k ij) различны. Пример двух ортогональных латинских квадратов и соответствующие им упорядоченные пары:

Эйлер называл такие квадраты «полными». В его честь в научной литературе их раньше называли «эйлеровыми» или «греко-латинскими» (так как Эйлер использовал буквы греческого алфавита для квадрата, ортогонального латинскому).

Ортогональные латинские квадраты существуют для любого n , не равного 2 и 6.

Латинский квадрат L n -го порядка имеет ортогональный ему квадрат тогда и только тогда, когда в L существует n непересекающихся трансверсалей .

Особый интерес в связи с многочисленными приложениями вызывают множества из нескольких попарно ортогональных латинских квадратов n -го порядка. Максимально возможная мощность N(n) такого множества равна n -1, в этом случае множество называется полным.

Если n ≡ 1 (mod 4) или n ≡ 2 (mod 4) и свободная от квадрата часть числа n содержит хотя бы один простой множитель p ≡ 3 (mod 4), то для таких n полного множества попарно ортогональных латинских квадратов не существует.

Известные нижние оценки числа N(n) при n < 33 приведены в следующей таблице (выделены оценки, которые могут быть улучшены):

Построение ортогональных квадратов - сложная комбинаторная задача. Для её решения применяются как алгебраические конструкции, так и комбинаторные (трансверсали, ортогональные массивы, дизайны, блок-схемы, тройки Штейнера и др.) Существует несколько подходов к решению этой задачи, их можно разделить на две группы. К первой группе относятся методы, основанные на выборе базового латинского квадрата, к которому отыскиваются изотопные ортогональные латинские квадраты. Например, пять попарно ортогональных латинских квадратов 12-го порядка были найдены в результате построения четырех ортоморфизмов абелевой группы , являющейся прямым произведением циклических групп порядков 6 и 2.

Ко второй группе относятся методы, использующие для построения ортогональных латинских квадратов комбинаторные объекты (включая сами латинские квадраты) меньших порядков. Например, два латинских квадрата 22-го порядка были построены Bose и Shrikhande на основе двух дизайнов 15-го и 7-го порядка.

Латинский квадрат называется диагональным, если в дополнение к требованиям уникальности элементов в строках и столбцах, свойственным для латинского квадрата, добавляются требования уникальности элементов на главной и побочной диагоналях . Аналитическая оценка числа диагональных латинских квадратов неизвестна, их число для размерностей N<10 было определено в 2016 г. в проекте добровольных распределенных вычислений Gerasim@Home (последовательность A274171 в OEIS и последовательность A274806 в OEIS). Для диагональных латинских квадратов, как и для просто латинских, возможно построение ортогональных пар, часть из которых (порядка 9 и 10) была найдена в проекте добровольных распределенных вычислений A287695 в OEIS). Открытой математической проблемой является существование тройки попарно ортогональных диагональных латинских квадратов порядка 10 (на текущий момент наилучшим приближением к ее решению является тройка квадратов, в которой две пары квадратов ортогональны, а третья частично ортогональна в 74 ячейках ).

Квадрат, в котором каждый элемент множества M в каждой строке и в каждом столбце встречается не более одного раза, называется частичным.

Задача распознавания того, может ли частичный квадрат быть дополнен до латинского, является NP-полной .

Введено понятие критического множества, соответствующего частичному квадрату, который однозначно может быть дополнен до латинского, причем никакое его подмножество условию однозначности не удовлетворяет. Мощность C(n) критического множества для квадратов размеров n × n известна для n < 7:

Помимо задачи нахождения формулы для величины L (n ), имеется большое количество нерешенных задач относительно латинских квадратов. Ряд таких задач был сформулирован на конференции Loops’03:

Латинские квадраты находят широкое применение в алгебре, комбинаторике, статистике, криптографии, теории кодов и многих других областях.

Существует ряд игр, в которых используются латинские квадраты. Наиболее известна из них судоку . В ней требуется частичный квадрат дополнить до латинского квадрата 9-го порядка, обладающего дополнительным свойством: все девять его подквадратов содержат по одному разу все натуральные числа от 1 до 9.

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

Если внимательно присмотреться к числам от 1 до 16, расположенным в клетках квадрата на рис. 1, то можно заметить следующую закономерность: сумма чисел в каждом горизонтальном ряду, в каждом вертикальном ряду и по каждой из диагоналей одна и та же. Такой квадрат и все квадраты, обладающие аналогичным свойством, получили название магических.

Задачи составления и описания магических квадратов интересовали математиков с древнейших времен. Однако полного описания всех возможных магических квадратов не получено и до сего времени. Магических квадратов не существует. На рис. 2 изображен единственный магический квадрат . Единственный в том смысле, что все остальные магические квадраты получаются из него либо поворотом вокруг центра, либо отражением относительно одной из его осей симметрии.

С увеличением размеров (числа клеток) квадрата быстро растет количество возможных магических квадратов. Так, например, различных магических квадратов уже 880, а для размера их количество приближается к четверти миллиона. Среди них есть квадраты, обладающие интересными свойствами. Например, в квадрате на рис. 3 равны между собой не только суммы чисел в строках, столбцах и диагоналях, но и суммы пятерок чисел по «разломанным» диагоналям, связанным на рисунке цветными линиями.

Латинским квадратом называется квадрат клеток, в которых написаны числа , притом так, что в каждой строке и каждом столбце встречаются все эти числа по одному разу. На рис. 4 изображены два таких латинских квадрата . Они обладают интересной особенностью: если один квадрат наложить на другой, то все пары получившихся чисел оказываются различными. Такие пары латинских квадратов называются ортогональными. Задачу отыскания ортогональных латинских квадратов впервые поставил Л. Эйлер, причем в такой занимательной формулировке: «Среди 36 офицеров поровну уланов, драгунов, гусаров, кирасиров, кавалергардов и гренадеров и, кроме того, поровну генералов, полковников, майоров, капитанов, поручиков и подпоручиков, причем каждый род войск представлен офицерами всех шести рангов. Можно ли выстроить этих офицеров в каре так, чтобы в любой колонне и любой шеренге встречались офицеры всех рангов?»

Эйлер не смог найти решения этой задачи. В 1901 г. было доказано, что такого решения не существует. В то же время Эйлер доказал, что ортогональные пары латинских квадратов существуют для всех нечетных значений и для таких четных значений , которые делятся на 4. Решение задачи Эйлера для 25 офицеров изображено на рис. 5. Чин офицера символизирует цветной кружок в углу каждой из клеток. Здесь особенно хорошо видна связь между, задачей Эйлера и латинскими квадратами: рода войск соответствуют числам одного латинского квадрата, а чины (цветные точки) – числам ортогонального ему латинского квадрата. Эйлер выдвинул гипотезу, что для остальных значений , т.е. если число при делении на 4 дает в остатке 2, ортогональных квадратов не существует. В 1901 г. было доказано, что ортогональных квадратов размером не существует, и это усиливало уверенность в справедливости гипотезы Эйлера. Однако в 1959 г. с помощью ЭВМ были найдены сначала ортогональные квадраты , потом . А затем было показано, что для любого , кроме 6, существуют ортогональные квадраты размером .

Гравюра А. Дюрера «Меланхолия»

«Часто воспроизводится магический квадрат, присутствующий на знаменитой гравюре А. Дюрера «Меланхолия».

Любопытно, что средние числа в последней строке изображают год 1514, в котором была создана эта гравюра». Д. Оре

Магические и латинские квадраты – близкие родственники. Пусть мы имеем два ортогональных латинских квадрата. Заполним клетки нового квадрата тех же размеров следующим образом. Поставим туда число , где – число в такой клетке первого квадрата, а – число в такой же клетке второго квадрата. Нетрудно понять, что в полученном квадрате суммы чисел в строках и столбцах (но не обязательно на диагоналях) будут одинаковы.

Теория латинских квадратов нашла многочисленные применения как в самой математике, так и в ее приложениях. Приведем такой пример. Пусть мы хотим испытать 4 сорта пшеницы на урожайность в данной местности, причем хотим учесть влияние степени разреженности посевов и влияние двух видов удобрений. Для этого разобьем квадратный участок земли на 16 делянок (рис. 6). Первый сорт пшеницы посадим на делянках, соответствующих нижней горизонтальной полосе, следующий сорт – на четырех делянках, соответствующих следующей полосе, и т.д. (на рисунке сорт обозначен цветом). При этом максимальная густота посевов пусть будет на тех делянках, которые соответствуют левому вертикальному столбцу рисунка, и уменьшается при переходе вправо (на рисунке этому соответствует уменьшение интенсивности цвета). Цифры же, стоящие в клетках рисунка, пусть означают: первая – количество килограммов удобрения первого вида, вносимого на этот участок, а вторая – количество вносимого удобрения второго вида. Эти числа на 1 меньше чисел в ортогональных латинских квадратах из рис. 4. Нетрудно понять, что при этом реализованы все возможные пары сочетаний как сорта, и густоты посева, так и других компонентов: сорта и удобрений первого вида, удобрений первого и второго видов, густоты и удобрений второго вида.

Использование ортогональных латинских квадратов помогает учесть все возможные варианты в экспериментах в сельском хозяйстве, физике, химии, технике.