Головоломки, снежинки и перестановки - Троицкий вариант — Наука

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

Сама математика так, конечно, не работает: нарратив тут важен, но формализм и точные формулы он не заменяет. Но, с другой стороны, почему бы не попробовать дать уважаемым читателям способ увидеть кусочек математики не вполне формальным образом? Для рассказа о теории групп (и мотивации самого понятия группы) я выбрал три разных сюжета: кубик Рубика (у этой головоломки, кстати, много вариантов, некоторые из них — на рис. 1), правильные многоугольники и снежинки, и сортировки массивов (да, это из программирования).

Темы, на первый взгляд, совершенно разные, но оказывается, что при переводе их на математический язык фигурирует один и тот же формализм: группы, действие групп на множествах и понятие образующих. Я задействую в рассказе некоторые сюжеты, связанные с графами Кэли, и тут позволю себе отослать читателя к другой моей статье, опубликованной в ТрВ-Наука [4].

Если читателя заинтересует теория групп, то рекомендую великолепную книгу [1], в которой есть вполне доступное (для мотивированного читателя) погружение в теорию групп и начала комплексного анализа. А сама книга представляет собой, по сути, разбитое на элементарные шаги доказательство теоремы Абеля о том, что уравнения выше четвертой степени неразрешимы в радикалах. Это, кстати, было тем истоком, из которого и родилась теория групп.

1. Кубик Рубика и его математика

Наверное, все держали кубик Рубика в руках. Некоторые избранные даже умеют его собирать (в [5] описан один из способов). Сразу признаюсь, что собирать кубик Рубика не умею, зато могу объяснять, почему его собрать можно. И это объяснение оказывается достаточно полезным для мотивировки многих понятий теории групп.

1.1. Группа кубика Рубика

Вот есть у нас кубик Рубика [2], самый обычный, 3×3. Далее будем пользоваться стандартными названиями, как на рис. 2. Элементарные действия для сборки — это вращения слоев кубика на 90° по часовой стрелке. Имея в виду, что, например, повернуть слой на 90° против часовой стрелки — то же самое, что и три раза по часовой.

• В каждой грани по 3 слоя.
• У кубика 3 координаты вращения.
• Итого 9 вариантов.Всевозможные комбинации элементарных вращений образуют множество допустимых вращений, обозначим его для краткости S. Каждый элемент s ∈ S — некое допустимое вращение кубика Рубика, в том числе и тривиальное id (т. е. когда ничего не происходит). Элементов в этом множестве очень много, но всё же конечно.Элементы множества S можно умножать 1 в следующем смысле: берем первое допустимое вращение, затем делаем второе допустимое вращение, получается третье допустимое вращение. Для умножения допустимых вращений a, b ∈ S будем писать a ⋅ b.Отметим несколько свойств этого умножения.
• Композиция с тривиальным вращением id на вращение не влияет. То есть a ⋅ id = id ⋅ a = a.
• Каждое вращение обратимо: если проделать элементарные вращения в обратном порядке — вернемся в то состояние кубика, с которого начали. Вращение, обратное к a, мы будем обозначать a-1.
• Свойство обратимости в терминах операции можно записать так: a ⋅ a-1 = id = a-1 ⋅ a.
• Чуть сложнее проверить, что эти вращения ассоциативны: a(bc) = (ab)c. В это просто поверим.

Выполнение перечисленных свойств для данного множества и заданной на этом множестве операции на математическом языке значат, что вращения кубика Рубика образуют группу. Согласно строгому определению, группа — это множество, на котором определена операция, которая удовлетворяет трем свойствам: имеется нейтральный элемент (умножение на который ничего не меняет), у каждого элемента группы есть обратный элемент (умножение на который дает нейтральный) и операция умножения является ассоциативной.Легко проверить (взяв в руки кубик Рубика), что умножение не коммутативно: важно, какое вращение делаем первым, а какое вторым. Так что группа вращений кубика не коммутативна. Кстати, в качестве упражнения стоит проверить, что обратный элемент единственен. Надо, конечно, учитывать, что во множество S входят именно сами вращения, а не их запись через элементарные вращения. То есть a ⋅ a-1 это id.

Каждое допустимое вращение есть произведение какого-то (возможно, очень большого) числа элементарных вращений. В теории групп такие элементы, из которых можно собрать всю группу, называются образующими. То есть группа вращений кубика Рубика — группа с 9 образующими (образующие = элементарные вращения слоев).

Мы можем заметить, что каждое элементарное вращение имеет, как говорят, степень 4. То есть a4 = a ⋅ a ⋅ a ⋅ a = id. В самом деле, если четыре раза прокрутить данный слой, то он вернется на место.

Другое соотношение между образующими можно вывести из того, что вращения слоев, лежащих в одной грани, друг на друга не влияют. Пусть e1, e2 — два таких вращения (двух параллельных слоев, например среднего и верхнего). Тогда они коммутируют: e1 ⋅ e2 = e2 ⋅ e1.
При этом, конечно, вращения в разных гранях друг с другом уже не коммутируют.

На самом деле знание образующих и соотношений (т. е. нетривиальных произведений образующих, равных нейтральному элементу) равносильно знанию структуры группы. Соответствующий раздел математики называется комбинаторной теорией групп, и о нем написано немало учебников. Тем не менее отметим, что на множестве S можно задать граф. В качестве вершин мы возьмем элементы S, а рёбра (графа, а не исходного кубика Рубика), проиндексированные элементарными вращениями (иногда говорят, что ребро имеет цвет) по следующей схеме: $a\overset{\epsilon}{\underset{}{\to}}b$, если ϵ — элементарное вращение и b = a ⋅ ϵ, то есть вращение b получается так: сначала делаем a, затем ϵ. Получившийся граф называется графом Кэли, и о нем уже рассказано в [4].

1.2. Допустимые состояния

Теперь рассмотрим множество R всех допустимых состояний кубика Рубика. (Это не то же самое, что вращения!) Превратим это множество в направленный цветной граф.

• Граф R имеет в качестве вершин множество допустимых состояний.
• Из состояния A в состояние B нарисуем стрелку цвета e (где e — элементарное вращение), если e переводит A в B.

Сразу понятно, что граф связен: из любого допустимого состояния можно попасть в любое другое. На то оно и допустимое.Каждое допустимое вращение w ∈ S кодирует преобразование графа, переведя состояние A в w(A). Например, тривиальное вращение оставит все вершины на месте. Легко понять, что при этом вершины, которые были соседними раньше, таковыми и останутся. На этом месте математик скажет (и мы скажем), что группа S действует на графе R.

Заметим два свойства этого действия:

• Транзитивность: допустимое состояние можно перевести в любое другое.
• Свобода: разные вращения действуют на граф по-разному.

Из этого следует (тут нужна теорема Сабидусси [3], это не самоочевидно), что граф состояний равен графу Кэли [4] группы допустимых вращений. Но и без этого можно понять, что граф вершинно-транзитивен: любую вершину можно перевести в другую единственным образом. Два дармовых следствия:

• Нет волшебного алгоритма, состоящего из фиксированного набора действий, механическое повторение которых соберет кубик из произвольного состояния. Однако при достаточном количестве повторений мы вернемся в то состояние, из которого начали.
• Нет плохих или хороших состояний: если мы умеем собирать граф в одно состояние не более чем за N элементарных действий, то и в любое другое состояние тоже сможем.

Это число N называют «числом Бога» (God number). Для обычного кубика Рубика, как в 2010 году выяснила корпорация Google, это число равно 202. А еще в этом графе есть гамильтонов цикл (проявление гипотезы Ловаса [6]). Гамильтоновым путем называется такой путь по графу, что он содержит в себе все вершины графа ровно по одному разу.С точки зрения кубика Рубика это значит, что, совершая элементарные вращения, можно «пробежать» по всем допустимым состояниям, побывав в каждом из них ровно один раз, и вернуться в исходное состояние.

Подытожим

• Кубик Рубика из любого положения можно собрать не более чем за 20 элементарных вращений, и улучшить эту оценку нельзя. Задача поиска такого алгоритма очень сложная, фактически равносильная полному перебору.
• Существует алгоритм, который позволяет элементарными вращениями побывать в каждом допустимом состоянии. Задача поиска такого алгоритма очень сложная… Ну вы поняли.
• Для кубика Рубика реальные алгоритмы сборки [7] содержат за сотню элементарных вращений.

2. Симметрии

А теперь давайте посмотрим на правильный n-угольник (на рис. 3 изображен шестиугольник, нарисовать аналогичные для любого желаемого n считайте за упражнение). Давайте зададимся вопросом о том, сколько есть движений плоскости, которые переведут его в себя. То есть сколькими способами можно наложить этот многоугольник (вырезанный, к примеру, из бумаги) на себя?

Заметим несколько моментов:

• Если два движения плоскости оставляют шестиугольник на месте, то их композиция тоже. К примеру два поворота вокруг точки O на π/3.
• Есть тривиальное движение id (никто никуда не двигается).
• Есть обратное движение.
• Движения ассоциативны (поверим).

Значит, множество интересующих нас движений, которые оставляют данный многоугольник на месте, являются группой, которую называют диедральной группой Dn. Понять, сколько в ней элементов, кстати, не очень сложно. Достаточно сообразить, что всякое движение кодируется тем, куда переходит одно ребро. Чтобы это понять, нужно определить образ одной вершины (n вариантов) и выбрать вариант, куда переходит ребро: по часовой или против (еще два варианта). Итого получаем, что |Dn| = 2n. И тут не то важно, что каждый из n поворотов и n симметрий (относительно разных прямых) являются движениями, а то, что других нет.

Тут еще можно заметить, что такая же группа симметрий есть не только у правильного n-угольника. Такая же группа симметрий (можно говорить «гексагональная группа»), как у шестиугольника, будет и у снежинок (рис. 4). Уместно сказать, что помимо обычных снежинок есть еще и фрактал, называемый снежинкой Коха (рис. 5). Больше о ней можно почитать в книгах о фракталах. Мы же отметим, что и у снежинки Коха тоже группа симметрий D6.

Из сказанного легко получить рецепт построения всевозможных фигур с такой симметрией: берем множество, действуем на него группой D6, объединяем что получилось — это и будет множеством, инвариантным относительно действия группы D6. Тут возникает еще один сюжет, связанный с действием группы на множестве. Итак, пусть у нас есть множество, инвариантное относительное действия группы. Выберем такое его минимальное (по включению) замкнутое подмножество, что из него можно получить всё множество.

Это называется фундаментальной областью. В предыдущем примере про кубик Рубика ситуация такая: любое допустимое состояние является фундаментальной областью в пространстве допустимых состояний. А вот если мы посмотрим на граф всевозможных состояний кубика Рубика (в том числе и недопустимых раскрасок), то вопрос о фундаментальной области становится гораздо труднее. Одной точкой тут не обойтись.

Например, есть старый пранк: поменять местами два цвета на каком-нибудь боковом кубике, всё перемешать и предложить для сборки. Пробовать не советую: можно этим кубиком и по голове получить.

3. Сортировка

Теперь давайте применим групповую логику к задаче сортировки массива. Имеем неупорядоченный массив M целых чисел (расставленные в произвольном порядке числа от 1 до m без повторов). Зафиксируем элементарное сортировочное действие: если пара элементов i, i+1 находятся в беспорядке, т. е. i + 1 стоит в массиве слева от i, то их нужно поменять местами. Повторяя эти элементарные действия, мы отсортируем массив.

Теперь переведем эту идею на язык теории групп. Рассмотрим элементарные транспозиции (перестановки двух элементов i и i + 1) и множество всевозможных перестановок (т. е. любого числа последовательных применений элементарных транспозиций), которое мы обозначим через Sm. Здесь m — это размер массива M. Операция на этом множестве вводится как и раньше: композиция. Все слова, сказанные выше про кубик Рубика, можно дословно повторить и тут, так что Sm является группой.

Пусть M — множество всевозможных перестановок элементов массива. Зададим действие группы Sm на графе M естественным (т. е. как для кубика Рубика) образом: перестановка s ∈ Sm действует на элементах множества M по правилу s: m |→ s(m).

У нас та же самая конструкция, что и для кубика Рубика. В качестве элементарных вращений — транспозиции, в качестве допустимых состояний КР — всевозможные варианты сортировки массива. Какие можем сделать выводы?

• Диаметр графа M — это минимальное достаточное число действий, нужных для сортировки.
• Сам алгоритм сортировки — нахождение пути в графе M.
• Ну а граф M — граф Кэли группы перестановок Sm с системой образующих из транспозиций.

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

Еще несколько мыслей:

• Минимальное достаточное число действий (число Бога) — это идеальная реализация способа сортировки.
• Конкретный алгоритм — построение пути в графе.
• Таких алгоритмов для одной системы образующих может быть несколько.
• Самый плохой из них — движение по гамильтоновому циклу «в неправильную сторону» (если он есть, т. е. если гипотеза Ловаса верна).
• Самый лучший (который еще поди найди) — движение по «алгоритму Бога».

Итоги

Теория групп дает хорошую оптику, чтобы работать с самыми разными сюжетами, которые сводятся к последовательным преобразованиям. Еще одна большая тема, углубляющая этот сюжет, связана с действием групп на разных пространствах. К примеру, она дает глубокое понимание разных геометрических сюжетов. И этот очень глубокий геометрический сюжет связан со знаменитой Эрлангенской программой Клейна. Подробнее об этом можно почитать в [8]. Но и без геометрии теория групп — это один из способов смотреть на многие не только теоретические, но и прикладные задачи.

1. Алексеев В. Б. Теорема Абеля в задачах и решениях. —М.: МЦНМО, 2001. old.mccme.ru/free-books/pdf/alekseev.pdf

2. Симулятор кубика Рубика. dedfoma.ru/kubikrubika/cube-simulator.htm

3. Sabidussi G. Graph and Group Theory. math.uni-hamburg.de/home/hamann/Lehre/GeoGrTh/GeoGrThEn.pdf

4. Как правильно гулять по графам Кэли. www.trv-science.ru/2022/05/kak-pravilno-gulyat-po-grapham-cayley/

5. Как собрать кубик Рубика? naked-science.ru/article/media/kubik-rubika-kak-sobrat-n

6. Lov’asz conjecture. en.wikipedia.org/wiki/Lov%C3%A1sz_conjecture

7. Пример алгоритма сборки кубика Рубика. share.google/IBcREFDjETrBs4maU

8. Прасолов В. В., Тихомиров В. М. Геометрия. — М.: МЦНМО, 1997. mathedu.ru/text/prasolov_tihomirov_geometriya_2007/p13/

Андроник Арутюнов,
докт. физ.-мат. наук, профессор ВШМ МФТИ

---

1 Термин «умножение» нужно понимать как традиционное обозначение операции, а не в контексте умножения чисел.

2 В метрике Face Turn Metric, где поворот грани на 180° считается за один ход). В метрике поворотов на 90° (Half Turn Metric) число Бога равно 26.