Закрыть

Меню

Поиск Закрыть

Библиотека > В популярных журналах > «Троицкий вариант»

Головоломки, снежинки и перестановки

«Троицкий вариант» №3 (447), 2026 • Математика • Комментировать

Андроник Арутюнов,
доктор физико-математических наук, профессор ВШМ МФТИ
«Троицкий вариант» №3 (447), 10 февраля 2026 года

Оригинал статьи на сайте «Троицкого варианта»

Андроник Арутюнов

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

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

Рис. 1. Некоторые варианты кубика Рубика

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

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

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

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

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

Рис. 2. Кубик Рубика и его элементы. Supertoys.by

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

В каждой грани по 3 слоя.
У кубика 3 координаты вращения.
Итого 9 вариантов. Всевозможные комбинации элементарных вращений образуют множество допустимых вращений, обозначим его для краткости S. Каждый элемент s ∈ S — некое допустимое вращение кубика Рубика, в том числе и тривиальное id (т. е. когда ничего не происходит). Элементов в этом множестве очень много, но всё же конечно. Элементы множества S можно умножать¹ в следующем смысле: берем первое допустимое вращение, затем делаем второе допустимое вращение, получается третье допустимое вращение. Для умножения допустимых вращений 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. То есть a⁴ = a ⋅ a ⋅ a ⋅ a = id. В самом деле, если четыре раза прокрутить данный слой, то он вернется на место.

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

При этом, конечно, вращения в разных гранях друг с другом уже не коммутируют.

На самом деле знание образующих и соотношений (т. е. нетривиальных произведений образующих, равных нейтральному элементу) равносильно знанию структуры группы. Соответствующий раздел математики называется комбинаторной теорией групп, и о нем написано немало учебников. Тем не менее отметим, что на множестве S можно задать граф. В качестве вершин мы возьмем элементы S, а рёбра (графа, а не исходного кубика Рубика), проиндексированные элементарными вращениями (иногда говорят, что ребро имеет цвет) по следующей схеме: a→ϵ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, это число равно 20². А еще в этом графе есть гамильтонов цикл (проявление гипотезы Ловаса [6]). Гамильтоновым путем называется такой путь по графу, что он содержит в себе все вершины графа ровно по одному разу. С точки зрения кубика Рубика это значит, что, совершая элементарные вращения, можно «пробежать» по всем допустимым состояниям, побывав в каждом из них ровно один раз, и вернуться в исходное состояние.

Подытожим.

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

2. Симметрии

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

Рис. 3. Самоналожения шестиугольника

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

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

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

Тут еще можно заметить, что такая же группа симметрий есть не только у правильного n-угольника. Такая же группа симметрий (можно говорить «гексагональная группа»), как у шестиугольника, будет и у снежинок (рис. 4).

Рис. 4. Макрофото снежинки. Wikimedia Commons

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

Рис. 5. Первые шаги построения снежинки Коха

Из сказанного легко получить рецепт построения всевозможных фигур с такой симметрией: берем множество, действуем на него группой 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]. Но и без геометрии теория групп — это один из способов смотреть на многие не только теоретические, но и прикладные задачи.