Давно, под влиянием книг Перельмана, Гарднера, Азимова и прочих, а также журналов вроде "Наука и жизнь" и "Квант", планировал на будущее писать собственные научно-популярные книги обо всем. Но к счастью вовремя понял, что бумажная литература в XXI веке - жанр не то чтобы вымирающий, но откровенно ретроградный, и в итоге переквалифицировался в блогеры. Многие посты из тех, что можно найти по тегу "
занимательные бредни" (и не только) - это несостоявшиеся статьи/главы. Да, в ЖЖ есть свои "научпоперы" вроде
sly2m'а с его физико-математической серией "
На пальцах", и мои работы - полнейшая неихуровня ©, зато охват тем у меня поширше будет. Настолько, что даже сам не знаю, про что будет следующий пост.
Сейчас же, отсылаясь к первой главе гарднеровских "Математических досугов", хочу написать про латинские квадраты, конечные аффинные и проективные плоскости и обобщенно-круговые турниры. Что это за звери такие, как они связаны друг с другом и зачем это всё.
Начнем по порядку.
Латинский квадрат - это матрица NxN, заполненная N различными элементами по правилам судоку - в каждой строке и в каждом столбце встречается ровно по одному экземпляру каждого из различных элементов.
Существуют также
греко-латинские квадраты - комбинации из двух латинских квадратов одного порядка, в которых каждая упорядоченная пара элементов встречается только один раз. Составляющие их латинские квадраты называют ортогональными.
Количество возможных попарно ортогональных латинских квадратов зависит от N. Эйлер, изучавший тему, показал, что при N=6 таких нет (то есть греко-латинский составить нельзя). Для остальных N>3 есть хотя бы одна пара, а теоретический максимум - N-1 - достигается при простом N (и не только, например, есть "полная группа" из 3 латинских квадратов 4х4).
Именно для простых N полная группа латинских квадратов строится алгоритмически: закрепив одну строчку/столбец, делаем копирование элементов вдоль всевозможных так называемых "ломаных диагоналей", всегда перемещаясь на X шагов по одной оси и на Y по другой, считая противоположные стороны квадрата склеенными по правилам модели тора (бублика). Полную группу из двух квадратов 3х3 можно видеть на картинке выше, группа из четырех квадратов 5х5 выглядит так (два получены ходом шахматного слона, два - ходом коня):
Добавим к полной группе еще два квадрата, уже не латинских - в нашем случае из пяти столбцов, заполненных числами 1-2-3-4-5 и из пяти строк, также заполненных 1-2-3-4-5 (процесс копирования не по диагоналям, а вдоль осей) - и держим расширенную группу из N+1=6 получившихся матриц в уме.
___
Что такое
конечная плоскость? Мы привыкли иметь дело с плоскостями бесконечными, евклидовыми; конечные же отличаются от них тем, что содержат конечное число точек, которые могут принадлежать прямым. Размерность плоскости (2 измерения) обеспечивает прописанное в "правилах игры" отсутствие скрещивающихся прямых - есть только пересекающиеся (содержащие общую точку) либо, опционально, параллельные (не содержащие ее). Обращаю внимание на то, что параллельность здесь не в евклидовом понимании, да и вообще при отображении на евклидову плоскость прямые превращаются в кривые, причем конечные.
Эта опциональность порождает два варианта:
1) Аффинные конечные плоскости. Их точки разбиваются на несколько равновеликих подмножеств, рассматривающихся как пучки параллельных прямых. При этом через каждую точку проходит несколько прямых (так, что любые две точки принадлежат одной прямой).
Простейшая аффинная плоскость топологически соответствует четырехугольнику с диагоналями (4 точки, 3 семейства по 2 параллельных прямых). Это второй порядок. Третий порядок - так называемая
конфигурация Гессе из 9 точек и 12 прямых в составе 4 семейств по 3 штуки, которую можно визуализировать, например, так:
4 семейства здесь - вертикальные прямые, горизонтальные и 2 вида диагональных (ломано-диагональных). Кто знаком с понятием определителя матрицы 3-го порядка, узнает здесь удобный метод их расчета (произведения троек вдоль главной диагонали берутся с плюсом, вдоль побочной - с минусом). Но постойте, где-то мы уже сталкивались с ломаными диагоналями... Правильно! Эти аффинные модели соответствуют расширенным полным группам латинских квадратов. А нашему примеру 5х5 соответствует 25 точек и 6 семейств по 5 параллельных прямых, каждая из которых соединяет одноименные элементы.
2) А вот конечные плоскости без параллельных прямых называются проективными. В них точки и прямые полностью двойственны - через любые две точки проходит одна прямая, но и любые две прямые проходят через одну точку. Проективная плоскость (не обязательно конечная, и бесконечная тоже) может быть получена операцией пополнения: а) каждый пучок параллельных прямых пополняется одной точкой (в случае с преобразованием евклидовой плоскости она называется бесконечно удаленной точкой); б) все бесконечно удаленные точки "объединяются" в прямую.
В итоге такая "пополненная" проективная плоскость обладает полной внутренней симметрией - все ее однотипные структуры с точки зрения топологии полностью симметричны. Собственно, название происходит из того факта, что такая плоскость позволяет уйти от противоречий и парадоксов при проекции с одной евклидовой плоскости на другую, при которых некоторые точки уходят в никуда и оттуда же (причем даже с противоположной на 180° стороны) возвращаются, делая пересекающиеся прямые параллельными и наоборот.
Так вот. В случае с конечной геометрией эти дополнения строятся аналогично: каждый пучок параллельных "прямых" продлевается до новой точки, через все новые точки проводится еще одна прямая. Конструкция из 25 точек и 30 прямых превращается в 31-31, где на каждой прямой находится ровно 6 точек. А конструкция 4-6 (четырехугольник с диагоналями) - в 7-7, известную как
плоскость Фано:
И конфигурация Гессе, и плоскость Фано принадлежат к семейству троек Штейнера - частного случая
систем Штейнера, комбинаций подмножеств определенного множества, где каждая пара элементов встречается в одном и том же количестве подмножеств. Конфигурация Гессе является еще и "тройкой Киркмана" - частным случаем систем Штейнера, когда все подмножества разбиваются на группы без перекрытий, каждая из которых содержит все элементы. 4х3 подмножеств на 9 элементов - простейшая из троек, сам Киркман изначально описал
случай из 7х5 подмножеств на 15 элементов.
___
Итак, и самое главное - зачем это всё? С практической точки зрения. А затем, что вышеописанные конструкции могут служить математической основой для турнирных схем, для которых ввожу определение обобщенные круговые турниры. От
обычных круговых турниров - дуэлей "каждый с каждым по N раз" - обобщенные турниры включают в себя игры, в которых задействовано не 2, а большее фиксированное количество игровых единиц (игроков, команд). В подвижных спортивных играх это довольно редкое явление, а вот в настольных, киберспорте, викторинах такое сплошь и рядом. Год назад писал про частные случаи
для 27 человек, играющих тройками. Скажем, конфигурация Гессе - это турнир на 9 человек, играющих тройками в 4 захода, чем я и воспользовался однажды при организации дартс-турнира на девятерых. (Мы играем чаще всего не один на один, а группами от 3 до 5 человек сразу). Играли и по плоскости Фано всемером.
Кроме того, схема обобщенного турнира может быть применена для оптимизации расписания обычного кругового турнира. Допустим, разбивка 16 человек на 20 четверок (аффинная конечная плоскость 4-го порядка) - это разбивка 120 дуэлей на группы по 6. Все игроки делятся на четыре четверки-микрогруппы, которые могут одновременно играть внутренние мини-турниры по 6 игр (как в футболе). Потом тасуются, и так 5 подэтапов. Именно такую схему даже применял в одной забаве в институтское время. А проективную плоскость из 13 игроков и игр (то есть точек и прямых) советовал кому-то в
useful_faq, когда требовалось составить расписание для игры в пинг-понг, когда было лишь два стола и время на 3 поединка на каждом столе в день.
А системы Штейнера с несколькими встречами между каждой парой игроков
весьма удачно применил Андрей Полозов для организации личных первенств в рамках командных видов спорта. Подключив фантазию, можно ввернуть эти математические схемы и еще куда-нибудь.
Да, кстати, если кто не знал, я в принципе
увлекаюсь разнообразными турнирными схемами и помогу подобрать оптимальную по вашим входным условиям. Что характерно, бесплатно :-)
Тема может быть интересна для
spamsink,
doncunita,
aaamibor,
avva и всех, кто видит прелесть в математике и может осилить вышенаписанное.