Рассмотрим два дростых примера, иллюстрирующих возможности применения леммы Бернсайда при решении комбинаторных задач на перечисление. Ряд примеров читатель найдет также в упражнениях к этому параграфу.
1. Раскраска вершин куба.
Сколькими способами можно раскрасить вершины куба в три цвета (например, красный, синий и зеленый)?
На первый взгляд может показаться, что задача совсем простая. Поскольку каждую из восьми вершин куба можно раскрасить тремя способами, причем независимо от того, как раскрашены другие вершины, то множество всех вершин куба можно раскрасить различными способами. Однако при таком подходе к решению задачи молчаливо предполагается, что мы умеем различать вершины куба перед окраской, т. е., скажем, куб жестко закреплен или его вершины занумерованы.
При этом полученный ответ можно интерпретировать следующим образом: можно так раскрасить абсолютно одинаковых, жестко закрепленных кубов, что все они будут различаться. Для кубов этого сделать уже нельзя.
Ситуация существенно меняется, если мы откажемся от предположения о том, что кубы жестко закреплены, так как по-разному окрашенные кубы можно повернуть так, что в новом положении их окраски совпадут (рис. 33).
Естественно считать, что два куба раскрашены одинаково, если их раскраски совпадают после некоторого вращения одного из кубов в пространстве. Будем говорить, что такие раскраски кубов геометрически неотличимы. Поэтому естественным уточнением задачи о раскраске является следующая задача:
Сколькими геометрически различными способами можно раскрасить вершины куба в три цвета.
Переформулируем теперь эту задачу так, чтобы стала понятной ее связь с леммой Бернсайда. Пусть М — множество всевозможных по-разному раскрашенных кубов одного размера, положение которых в пространстве фиксировано, , G — группа всех вращений куба, состоящая из 24 перестановок. Группа G естественным образом определяет группу перестановок на множестве М. Именно: если а — некоторое вращение, то каждому кубу из М можно сопоставить некоторый, вообще говоря, другой куб, который получается из первого при вращении а. Это соответствие является, очевидно, перестановкой на множестве которую будем обозначать а. Группу всех таких перестановок множества М, определяемых перестановками из G, мы будем обозначать G. Ясно, что
То, что два куба из М раскрашены геометрически одинаково, означает, что один из них можно перевести вращением в такое положение, в котором они неразличимы. Иными словами, существует такая перестановка что содержатся в одной орбите группы G, действующей на множестве М. Таким образом, для того чтобы определить число геометрически различимых способов раскраски вершин куба, нужно найти количество орбит группы G на множестве М.
Считая вершины кубов занумерованными числами 1,2, 3, 4, 5, 6, 7, 8, раскраску каждого из 38 кубов можно однозначно охарактеризовать «словом» из 8 букв, каждая из которых есть либо к, либо с, либо з. То, что i-я буква слова равна к (или с, или з), означает; что i-я вершина при выбранной нумерации окрашена в красный цвет (или в сцний, или в зеленый соответственно). Например, для куббв, изображенных на рис. 33, имеем соответственно последовательности . Перестановки из группы G переставляют такие последовательности. Например, если то перестановка а слово переводит в , слово ссззсскк переводит в слова оставляет неизменными и т. д. Выписать всю таблицу значений для перестановки а затруднительно, поскольку она состоит из строк!
Для того чтобы применить лемму Бернсайда, необходимо определить число неподвижных точек каждой перестановки из G. Последовательность букв будет неподвижной для перестановки тогда и только тогда, когда при разложении соответствующей перестановки в произведение «Циклов вершины куба, номера которых входят один и тот же цикл, окрашены одним цветом. Например, если , то неподвижными относительно а будут слова, составленные целиком из одной буквы, и слова, составленные из двух разных букв, причем одна из них стоит на первых четырех местах в слове, а вторая — из четырех последующих. Поэтому имеется 9 неподвижных точек перестановки на множестве М. Уже на этом примере видно, что подсчет числа неподвижных точек перестановок из G сильно упрощается, если извесгны разложения в произведение циклов соответствующих перестановок из G. Если перестановка разложена в произведение циклов, то число ее неподвижных точек равно
Поэтому сначала мы опишем разложения в произведение циклов для всех перестановок из группы G вращений куба.
а) Вокруг каждой из трех осей, соединяющих центры противоположных граней, имеется три нетождественных вращения. Им соответствуют перестановки
б) Вокруг каждой из четырех диагоналей, т. е. осей, соединяющих противоположные вершины куба, имеется по два нетривиальных вращения. Им соответствуют перестановки
в) Вокруг каждой из шести осей, соединяющих середины противоположных ребер, имеется одно нетривиальное вращение. Им соответствуют перестановки
Вместе с тождественной получаем 24 перестановки. Итак, в группе G вращений куба имеется
Перестановка первого типа имеет неподвижных точек, любая из перестановок второго типа третьего и четвертого типов — неподвижных точек. Поэтому согласно лемме Бернсайда имеем
Таким образом, число геометрически различимых способов раскраски вершин куба в три цвета равно 333.
2. Составление ожерелий.
Сколько различных ожерелий из семи бусин можно составить из бусин двух цветов — красного и синего?
Для того чтобы стала понятной аналогия этой задачи с предыдущей, переформулируем ее следующим равносильным образом:
Сколькими геометрически различными способами можно раскрасить вершины правильного семиугольника в два цвета?
Здесь два способа раскраски неотличимы, если один из них можно получить из другого, применяя к семиугольнику либо преобразования вращений, либо симметрии относительно осей, т. е. перестановки из группы диэдра Если вершины семиугольника пронумерованы, имеется различных вариантов их раскраски, так как каждую вершину независимо от других можно раскрасить двумя способами.
Снова будем описывать раскраски словами длины 7, составленными из букв к (вершина окрашена в красный цвет) и с (вершина окрашена в синий цвет). На множестве N всех таких слов действует группа перестановок, задаваемых перестановками из Например, если, , то перестановка а последнюю букву каждого слова переставляет в его начало, а остальные буквы не изменяет. Для того чтобы определить число орбит группы на множестве N, необходимо найти типы перестановок из Эта задача гораздо проще аналогичного вопроса для группы G из примера 1.
Группа состоит из 14 перестановок множества которые распределены по возможным типам так:
Слово неподвижно относительно перестановки тогда и только тогда, когда буквы, стоящие на местах с номерами из одного цикла в перестановке а, совпадают. Поэтому тождественная перестановка имеет 27 неподвижных точек на N, перестановки второго типа — по 2, а перестановки третьего типа — по 24. Применяя лемму Бернсайда, получаем
Итак, из бусин двух цветов можно составить 18 семибусенных ожерелий.
Упражнения
1. Грани куба можно раскрасить: а) все в белый цвет; б) все в черный цвет; в) часть в белый, а остальные в черный. Сколько имеется разных способов раскраски?
2. Сколько различных ожерелий можно составить из двух синих, двух белых и двух красных бусин?
3. Сколькими геометрически различными способами три абсолютно одинаковые мухи могут усесться в вершинах правильного пятиугольника?
4. Сколько существует различных ориентированных графов с тремя вершинами?
5. Сколько существует различных неориентированных графов с четырьмя вершинами?
6. Сколькими способами можно раскрасить вершины куба в два цвета так, чтобы вершин каждого цвета было поровну?
7. Сколькими различными способами можно грани куба раскрасить в четыре цвета?
Что такое куб перестановки
В 1975 г. венгерский архитектор профессор Э. Рубик создал математическую головоломку, которая получила в последующие годы широкое распространение во всем мире и является сейчас, пожалуй, наиболее популярной математической игрой. Математический анализ этой игры гораздо сложнее, чем анализ игры «в пятнадцать», вопросы и задачи, которые можно ставить в связи с ней, куда более разнообразны, хотя с точки зрения теории групп перестановок это игры одного типа.
1. Опишем вкратце головоломку Э. Рубика. Она представляет собой пластмассовый куб, разбитый на 27 одинаковых кубиков плоскостями, параллельными граням куба; 26 кубиков являются наружными, а один — внутренний. Внутренний кубик удален, а наружные кубики, на который изнутри имеются специальные выступы, с помощью крестовины сцеплены так, что любая из плит, образованных девятью кубиками, грани которых параллельны некоторой грани куба, может свободно вращаться вокруг центра в любом направлении. При повороте одной из плит на углы 90°, 180° или 270° свобода вращений системы полностью сохраняется: любую из плит снова можно вращать вокруг центра в любую сторону. Внешние грани каждого из 26 маленьких кубиков окрашены в шесть разных цветов: красный, оранжевый, желтый, зеленый, синий, белый (по 9 граней каждого цвета).
Общий вид куба изображен на рис. 40 а, на рис. 40 б, в указаны возможные повороты плит — внешних и внутренней. В начальном положении маленькие кубики расположены так, что все грани большого куба окрашены в один цвет. Затем с помощью нескольких последовательных вращений грани куба приобретают пеструю окраску. Цель игры состоит в том, чтобы, получив в руки такой пестро окрашенный кубик, с помощью поворотов плит перейти к начальной раскраске, т. е. добиться такой расстановки кубиков, при которой все грани большого куба окрашены в один цвет.
Эта головоломка получила название «венгерский шарнирный кубик» или «кубик Рубика». Исследованию задач, с ней связанных, посвящено большое число научно-популярных статей, опубликованных в разных странах, и даже несколько книг (например, книга В. Хинце «Венгерский волшебный кубик» на немецком языке, вышедшая в 1982 г. в берлинском издательстве «VEB Deutscher Verlag der Wissenschaftem).
Из публикаций в отечественных журналах отметим статьи И. Константинова «Венгерский кубик» («Наука и жизнь», 1981, № 3; 1982, № 2), В. Залгаллера, С. Залгаллера «Венгерский шарнирный кубик» («Квант», 1980, № 12), М. Евграфова «Механика волшебного кубика» («Квант», 1982, № 2), В. Дубровского «Алгоритм волшебного кубика» («Квант», 1982, № 7), «Математика волшебного кубика» («Квант», 1982, № 8), «Кубик в картинках» («Квант», 1983, № 9), Ю. Демкова «Поворачиваем кубики» («Квант», 1981, № 12) и некоторые другие.
Уже из названий некоторых из этих публикаций видно, какими вопросами интересуются при рассмотрении кубика Рубика. В первую очередь, хочется узнать, как же он устроен, каков механизм, позволяющий осуществлять такие вращения. Во-вторых, естественно возникает желание научиться переходить к начальной окраске кубика из любого возможного его «пестрого» состояния. Конечно, если «пестрая» раскраска получена из начальной с помощью ряда вращений плит, то перейти от такого состояния к начальному всегда можно. Поэтому хочется иметь набор правил — алгоритм, который обеспечит достижение начального состояния из любого возможного. Для выработки такого алгоритма строят математическую модель решаемой задачи. В этой-то модели и возникает группа перестановок, связанная с кубиком Рубика. Вспомогательные задачи, которые необходимо решить, — это научиться строить системы образующих возникающей группы перестановок и раскладывать ее элементы в произведение образующих элементов. Обе задачи упрощаются, если заметить, что группа перестановок, связанная с кубиком Рубика, строится из уже известных читателю групп с помощью рассмотренных в предыдущем параграфе конструкций.
Вначале рассмотрим, как устроен волшебный кубик. В нем 27 основных деталей: крестовина (рис. 41 а), 12 боковых кубиков (рис. 416), 8 угловых кубиков (рис. 41 в) и 6 центральных кубиков (рис. 41 г).
На самом деле, как видно из рис. 41, «кубики» — это совсем не кубики, а более сложные тела. В большой куб они сложены так, что извне кажутся кубиками. Кубики, расположенные в центре каждой из граней (поэтому мы их будем называть центральными), крепятся на крестовину. У них окрашейа одна сторона (внешняя); Средние кубики, у которых раскрашены 2 внешние стороны, расположены в середине каждого ребра, а угловые кубики, у которых раскрашены 3 внешние грани, расположены в; вершинах куба. Расположение кубиков в кубе хорошо видно на рис. 42, на котором куб изображен со снятыми передней плитой и одним средним кубиком. Внутренние выступы на средних и угловых кубиках сделаны так, что при составлении куба из этих выступов образуется почти цилиндрическое тело, а на средне слое образуется кольцеобразное углубление. При повороте плиты цилиндрическое тело вращается в кольцеобразном углублении. Вот и весь механизм кубика Рубика, не считая мелких второстепенных деталей.
2. Остановимся теперь на описании алгоритма приведения кубика Рубика из «пестрого» состояния в начальное. Условимся вначале о следующих удобных сокращениях.
Поскольку при вращениях плит мы интересуемся лишь взаимным расположением маленьких кубиков в большом кубе, можно считать расположение куба в пространстве фиксированным, т. е. считать его крестовину жестко закрепленной, а центральные кубики — неподвижными. Это означает, что возможны лишь вращения шести внешних плит куба. Обозначим грани куба буквами (рис. 43) «ф» (фасад), «т» (тыл), «в» (верх), «н» (низ), «л» (левая сторона), «п» (правая сторона).
Маленькие кубики молено теперь определять наборами букв: центральным кубикам соответствует одна буква (например, кубику фасада — буква «ф»), средним кубикам — две буквы (например, кубику, принадлежащему фасадной и левой грани, — буквы «фл»), угловым кубикам — три буквы (например, кубику, принадлежащему фасадной, левой и верхней граням, — буквы «флв»).
Прописными буквами Ф, Т, В, Н, Л, П будем обозначать вращения соответствующей грани (плиты) наугол по часовой стрелке. Вращения против часовой стрелки обозначаются этими же буквами в степени —1. Это оправдано, поскольку каждое из вращений осуществляет некоторую перестановку множества маленьких кубиков с учетом раскраски и, следовательно, можно говорить об обратной перестановке. Понятно, что обратной к перестановке будет перестановка и аналогично для других типов вращений. Последовательностям вращений граней будут отвечать «слова», составленные из букв Ф, Т, В, Н, Л, П в степенях Например, словом
описывается следующая последовательность вращений:
а) фасадную грань повернуть на угол по часовой стрелке;
б) тыловую грань дважды повернуть на угол или, что то же самое, повернуть на угол я по часовой стрелке;
в) нижнюю грань повернуть на угол против часовой стрелки;
г) левую грань повернуть на угол против часовой стрелки.
Каждому из этих вращений соответствует некоторая перестановка маленьких кубиков с учетом их раскраски, а всей последовательности — произведение таких перестановок. В результате выполнения серии вращений а) —г) маленькие кубики «пропутешествуют» и займут новые места в кубе.
Будем называть расположения кубиков внутри большого куба его состояниями. Если от состояния S к состоянию S можно перейти серией вращений то будем записывать это так: Различные серии вращений могут переводить куб, вообще говоря, в одно и то же состояние.
Например, имеем для любого состояния
Читатель без труда продолжит этот список.
Состояние куба назовем допустимым, если его можно получить из начального вращениями граней куба. Понятно, что из любого допустимого состояния можно перейти к начальному — для этого нужно просто обратить последовательность вращений. Например, если состояние куба S получено из начального состояния в результате серии вращений (1), то, применяя к кубу в состоянии S последовательность вращений
перейдем к состоянию
Опишем теперь один из возможных алгоритмов сборки кубика Рубика, т. е. укажем правила, руководствуясь которыми от любого допустимого состояния можно рейти к начальному. В большинстве алгоритмов вращения граней, осуществляемые при сборке кубика Рубика, группируются в стандартные комбинации из двух вращений :
а) комбинация — сопряжение вращения Y с помощью вращения X;
б) комбинация — коммутатор вращений
Можно рассматривать также сопряжения и коммутаторы степеней основных вращений, например:
а) — сопряжение вращения с помощью вращения
Легко проверяется, что коммутатор основных вращений прилегающих граней переставляет три средних кубика циклически. Например, коммутатор действует на кубики, стоящие на местах следующим образом (рис. 44):
При этом некоторые кубики остаются неподвижными, а угловые также перемещаются.
Процесс сборки кубика Рубика осуществляется в 4 этапа.
К выполнению следующего этапа нужно приступать лишь тогда, когда предыдущий этап полностью закончен.
При описании этапов сборки буквами х, будем обозначать какие-то из граней куба, имеющие общую вершину, а символами X, Y, Z — основные вращения граней х, соответственно.
Этап 1. Расстановка на своих местах средних кубиков.. Серия вращений
граней куба ху переставляет два средних кубика, принадлежащие грани х, и оставляет неподвижными остальные средние кубики. Применяя эту серию к некоторому состоянию S куба, получим новое состояние S, отличающееся от S расположением угловых и двух средних кубиков. Например, для серии имеем (рис. 45)
Серии вращения вида (2) позволяют переставить любые два из средних кубиков. Для этого нужно с помощью вспомогательных ходов поставить переставляемые кубики на соответствующие места в одной из граней куба, применить серию вращений (2) и, выполняя обратную последовательность ходов, перейти к требуемому состоянию.
Этап 1 закончен, если все средние кубики расположены на своих местах. Однако при этом они могут оказаться неправильно ориентированными (цвет среднего кубика грани не соответствует цвету ее центрального кубика).
Этап 2. Правильная ориентация средних кубиков, стоящих на своих местах. Произведение трех коммутаторов
одновременно поворачивает на своих местах два из кубиков, принадлежащих грани не меняя при этом расположения других средних кубиков.
поворачивает на своих местах средние кубики (рис. 46). Последовательности вращений вида (3), выполненные для подходящих граней, позволяют одновременно менять ориентацию любых двух из средних кубиков (почему?). Выполняя совместную переориентацию пар средних кубиков, можно все их расположить на своих местах так, как они располагаются в начальном состоянии куба. Это следует из того, что состояние, в котором все средние кубики, кроме одного, правильно расположены на своих местах, не может быть допустимым.
Этап 3. Расстановка на своих местах угловых кубик Степень
коммутатора вращений X, Y соседних граней осуществляет одновременную перестановку пар угловых кубиков, которые принадлежат граням, имеющим с у два общих ребра. Например (рис. 47), третья степень коммутатора переставляет угловые кубики так:
Произведение степеней коммутаторов
осуществляет перестановку трех угловых кубиков, принадлежащих грани . Например, серия вращений
перемещает угловые кубики фасадной грани следующим образом:
После выполнения каждой из серий поворотов (4), (5) средние кубики не меняют своего положения; остаются на своих местах также угловые кубики, которые не учитывались при рассмотрении серии.
С помощью последовательностей вращений вида (4), (5) все угловые кубики можно расставить по своим местам (проверьте!). При этом надо учитывать, что в допустимом состоянии не может случиться так, чтобы все средние кубики были расположены как в начальном состоянии, а все угловые, кроме двух, стояли на своих местах: если не все угловые кубики стоят на своих местах, то их не меньше чем 3.
Этап 4. Переориентация угловых кубиков, стоящих на своих местах. Последовательность вращений
одновременно поворачивает каждый из трех угловых кубиков, принадлежащих грани вокруг соответствующей диагонали куба на угол по часовой стрелке. А последовательность вращений Поворачивает эти кубики вокруг тех же осей на угол по часовой стрелке. Например, вращения а, составленные для граней ф, в, п, поворачивают угловые кубики (рис. 48). При этом расположение и ориентация других кубиков не изменяются.. Понятна, что с помощью последовательностей вращений а и можно переориентировать любые 3 угловых кубика. Если учесть, что в допустимом состоянии не может случиться так, чтобы все средние кубики были расположены как в начальном состоянии, все угловые кубики были на своих местах и лишь один из них был бы неправильно повернут, то закончить этап 4, а следовательно, и сборку кубика в целом не составляет труда.
Описанный здесь алгоритм — далеко не самый экономный. Сборка кубика с его. помощью может быть весьма длительным процессом, требующим большого числа ходов. Существуют более экономные алгоритмы, в частности, описанные в отмеченных выше статьях. Однако приведенный алгоритм поможет нам построить математическую теорию игры, после чего читатель сам сможет разрабатывать такие алгоритмы.
3. Опишем группу перестановок, которая «управляет» состояниями кубика Рубика. Полностью описать состояние куба можно, указав место, которое занимает каждый маленький кубик в нем и, ориентацию кубика на этом месте. Средние кубики могут быть ориентированы на каждом месте двумя способами, а угловые — тремя. Пусть кубик Рубика находится в начальном состоянии.
Занумеруем его угловые кубики в каком-либо порядке числами 1, 2, 8, а средние числами Этими же числами занумеруем места, на которых стоят маленькие кубики. Любое состояние куба после этого можно характеризовать перестановкой, указывающей номера угловых и средних кубиков, стоящих при этом состоянии на мгестах 1—20. Если в состоянии S на месте с номером i стоит кубик с номером (1 20), то этому состоянию однозначно ставится в соответствие перестановка
Перестановка определяет только места, занимаемые маленькими кубиками, состояние S ею однозначно не определяется — нужно определить еще ориентацию кубиков. Для задания ориентации угловых кубиков фиксируем две противоположные грани куба — например, верхнюю и нижнюю. Предположим, что эти грани окрашены в красный (верхняя) и желтый (нижняя) цвета. Любой угловой кубик имеет либо красную, либо желтую грань. Угол, на который нужно повернуть угловой кубик вокруг вершины куба, чтобы эта его грань заняла положение вверху (красная) либо внизу (желтая), и определяет ориентацию углового кубика. Этот угол может равняться Условимся обозначать ориентацию углового кубика, соответствующую повороту на 0, символом «0», повороту на — символом «1», а повороту на — символом «2». После этого при любом состоянии куба расположение углового кубика с учетом его ориентации описывается парой чисел , где i — номер места, на котором он стоит, s — его ориентация. При передвижениях кубика эта пара изменяется — как первая координата, так и вторая. Для того чтобы указать ориентацию среднего кубика, на каждом ребре куба фиксируем направление (укажем стрелку) и «нарисуем» такое же направление на среднем кубике так, чтобы в начальном состоянии оба направления совпадали. После этого при любом состоянии куба положение среднего кубика с учетом его ориентации описывается парой чисел где — номер места, на котором стоит кубик, а если ориентации кубика и ребра, на котором он расположен, совпадают, и если они противоположны.
Таким образом, состояния куба однозначно характеризуются перестановками множества
Каковы же эти перестановки?
Поскольку при вращениях граней средние кубики могут передвигаться только на место средних, а угловые — на место угловых, то любая перестановка множества К у задающая некоторое состояние куба S, определяет некоторую перестановку из множества — перестановку угловых кубиков с учетом ориентации — и некоторую перестановку из множества — перестановку средних кубиков с учетом ориентации. Эти перестановки действуют на непересекающихся множествах, объединение которых совпадает с . Поэтому, согласно определению прямой суммы перестановок, получаем
Посмотрим теперь, как же устроены перестановки множеств угловых и средних кубиков с учетом ориентации. Задать перестановку означает указать место каждого из угловых кубиков (чему соответствует перестановка множества , являющаяся ограничением перестановки на это множество) и указать дриентацию каждого из угловых кубиков (чему будет соответствовать задание для каждого из кубиков «своей» перестановки на множестве , которая является степенью цикла длины 3). Итак, перестановке a s сопоставляется набор где определяет ориентацию кубика , Иными словами, перестановка является сплетением перестановок множества содержащихся в циклической группе этого множества, с помощью некоторой перестановки» из симметрической группы
Аналогично, задать перестановку означает указать место каждого среднего кубика (чему соответствует ограничение перестановки на множество ) и его ориентацию (чему соответствует задание для каждого из кубиков «своей» перестановки множестве ). Это означает, что перестановка является сплетением перестановок множества с помощью некоторой перестановки из симметрической группы действующей на множестве
Таким образом, можно сказать, что любое состояние кубика Рубика однозначно описывается перестановкой множества К, имеющей вид
где действует на множестве при . А множеству всех состояний соответствует группа перестановок
действующая на множестве К. Отсюда сразу получаем, что общее число состояний кубика Рубика равно .
Опишем теперь перестановки, которыми задаются допустимые состояния волшебного кубика. Они, очевидно, будут образовывать группу, поскольку, произведение перестановок, отвечающих допустимым состояниям, тоже задает некоторое допустимое состояние (почему?). Покажем, что эта группа состоит из тех перестановок группы И вида (7), для которых выполняются следующие три условия:
а) — четная перестановка;
б) — тождественная перестановка множества
— тождественная перестановка множества .
Проверим сначала, что условия а), б), в) необходимы. Вращение любой из граней на угол определяет циклическую перестановку на множествах угловых и средних кубиков этой грани. Пусть при таком вращении куб переходит из состояния S в состояние S. Если состояние S описывается перестановкой
а состояние S — перестановкой
то , где — циклические перестановки множеств угловых и средних кубиков этой грани. Это циклы длины 4, т. е. нечетные перестановки. Поэтому перестановки и имеют соответственно противоположные четности. Следовательно, четности перестановок совпадают. Если состояние S — допустимое, то от него можно перейти к начальному состоянию с помощью серии Вращений граней. На каждом шаге при этом будет появляться новое состояние S, четность подстановки для которого совпадает с четностью
Поэтому четность подстановки для допустимого состояния S совпадает с четностью такой подстановки для начального состояния, а ему соответствует четная подстановка. Итак, условие а) необходимо.
Далее, легко проверяется, что перестановки, определяющие ориентацию угловых кубиков, не изменяются при произвольных вращениях верхней и нижней граней куба и при вращениях остальных граней на угол . При вращениях одной из граней на углы две перестановки, задающие ориентацию кубиков противоположных вершин, умножаются на цикл (0, 1,2), а две другие — на цикл Следовательно, произведение всех таких перестановок для каждого допустимого состояния такое же, как и для начального, для которого оно, очевидно, равно е.
Перестановки, определяющие ориентацию средних кубиков, либо не изменяются при поворотах грани, либо изменяются на противоположные (т. е. умножаются на транспозицию . Поэтому их произведение остается прежним, т. е. выполняется условие в).
Описывая алгоритм сборки кубика, мы использовали три совсем неочевидных утверждения:
1) состояние, в котором все средние кубики, кроме Одного, правильно расположены на своих местах, не может быть допустимым;
2) состояние, в котором все средние кубики правильно расположены на своих местах и все угловые, кроме двух, Стоят на своих местах, не может быть допустимым;
3) состояние, в котором все средние кубики правильно расположены на своих местах, все угловые — тоже, но один из них неправильно повернут, не может быть допустимым.
Правильность утверждений 1) — 3) следует из необходимости условий а) — в) для того, чтобы перестановка множества К определяла допустимое состояние кубика. Действительно, для состояний кубика Рубика, не удовлетворяющих требованию 1), очевидно, не выполняется условие б), а для состояний, не удовлетворяющих требованию 3), — условие в). Состояние S, не удовлетворяющее условию 2), не может быть допустимым, поскольку соответствующая ему подстановка — нечетная. В самом деле, так как все средние кубики стоят на своих местах, то — тождественная подстановка, а — транспозиция.
Поэтому — нечетная, как прямая сумма нечетной подстановки с четной.
Убедимся теперь, что условия являются также и достаточными. Пусть S — некоторое состояние кубика Рубика, которое характеризуется перестановкой из группы Я, удовлетворяющей условиям Применим к этому состоянию описанный нами алгоритм сборки кубика. Первый этап алгоритма выполняется беспрепятственно, поскольку его можно применить к любому состоянию и получить нужный результат. Второй этап алгоритма можно провести всегда, если состояние S удовлетворяет условию 1). Но это так и есть, пцскольку условие 1) следствие условия б). После осуществления второго этапа все средние кубики правильно расположены на своих местах и полученному состоянию куба отвечает перестановка множества К вида
где — тождественная перестановка множества х . Отсюда следует, что перестановка Ф—четная. А четную перестановку можно либо разложить в произведение циклов длины 3 (см. упражнение 7 к § 15), либо разбить на произведение пар транспозиций. Поэтому можно осуществить третий этап сборки волшебного — кубика. Заметим, что описывая ранее этот и следующий этап, мы намеренно опустили некоторые подробности; теперь читатель легко их восполнит.
После третьего этапа сборки состояние куба будет характеризоваться перестановкой — множества К вида
где — тождественная перестановка множества — циклические или тождественная перестановка множества причем . Последнее равенство, как было сказано, означает, что это состояние удовлетворяет условию 3), т. е. к этому состоянию можно применить четвертый этап сборки кубика.
Таким образом, группа перестановок G множества К, характеризующая допустимые состояния кубика, является собственной подгруппой группы Н. Для любой перестановки из Н вида (7) может быть выполнено одно из следующих условий:
а) — либо четная, либо нечетная (2 возможности);
б) перестановка равна либо , либо (0, 1,2), либо (0, 2, 1) (3 возможности);
в) перестановка равна либо , либо (1,0) (2 возможности).
Всего можно составить 12 комбинаций этих возможностей, т. е. перестановка из Н вида (7) может удовлетворять одному из 12 наборов условий. Этими условиями как раз описываются классы смежности группы G по подгруппе Н (почему?), т. е. G — подгруппа индекса 12 в Я.
После всего сказанного становится понятно, как формулировать задачи, связанные с кубиком Рубика на языке теории групп перестановок:
В группе G фиксирована система образующих перестановок, которые соответствуют вращениям граней кубика Рубика. Требуется указать алгоритм, руководствуясь которым любую перестановку можно было бы разложить в произведение образующих.
При этом важна оценка длины разложения, а она может существенно зависеть от выбранного алгоритма (из предыдущих примеров уже известно, что разложение подстановки в произведение образующих не однозначно).
По мере исследования свойств группы G такие оценки существенно понижались. В соответствии с одним из первых алгоритмов любую перестановку из группы G можно было бы разложить в произведение не более чем 277 образующих из указанной системы, т. е. «пестрый» кубик можно было бы перевести в начальное состояние не более чем за 277 поворотов граней. После более детального анализа был разработан алгоритм, позволяющий раскладывать перестановки из G в произведение образующих длины не более 52, причем высказано мнение, что можно ограничиться произведениями длины не более 23.
На самом деле оценку длины возможных разложений можно исследовать независимо, без рассмотрения алгоритмов, позволяющих такое разложение осуществлять
Упражнения
1. Как действуют на угловые кубики серии вращений а) , б) в) г) ?
2. Каков порядок перестановок из группы G, определяемых сериями вращений
3. Проверить, что серия вращений осуществляет циклическую перестановку трех средних кубиков, расположенных на трех гранях «буквой Т».
4. Указать последовательность вращений граней куба, меняющую местами угловые кубики, расположенные по диагонали (с изменением ориентации),
5. Проверить, что последовательность вращений ПОДЛПВ циклически переставляет средние кубики, принадлежащие одной грани, а все другие кубики оставляет на местах.
6. «Кубик без раскраски». Маленькие кубики в кубе занумерованы: угловые числами , а средние — числами 9, 10, 20, Куб не раскрашен. Если пронумеровать места, которые первоначально ванимают маленькие кубики, теми же числами, то любое состояние такого куб однозначно описывается некоторой перестановкой множества Какие перестановки этого множества соответствуют допустимым состояниям куба?
7. Проверить, что любой цикл (I, ) длины 3 над некоторым множеством является коммутатором транспозиций над этим множеством.
8. Подгруппа некоторой группы G, порожденная всевозможными коммутаторами элементов из G, называется коммупкнтом Найти коммутант группы
9. Предположим, что волшебный кубик окрашен в 3 цвета так, что в начальном состоянии противоположные грани окрашены одинаково, Описать допустимые состояния такого кубика,
10. Кубик Рубика был разобран и заново сложен так, что в «начальном» состоянии ему отвечает перестановка вида (7), для которой — нечетная,
Можно ли от любого состояния с такими же свойствами перейти к «начальному»?
накладываемые на перестановки вида (7), характеризующие состояния кубика, не зависят от способа определения ориентации угловых и средних кубиков,
12. Алгоритм «послойной сборки кубика Рубика состоит в следующем:
Этап 1, Устанавливаем на свойх местах правильно ориентированные средние кубики нижней грани.
Этап 2, Устанавливаем на своих местах правильно ориенти рованные угловые кубики нижней грани,
Этап 3, Устанавливаем на свои места средние кубики серединной плиты (параллельной нижней грани),
Этап 4. Переориентируем средние кубики верхней грани; средние кубики установим так, чтобы цвет их верхней грани совпал с цветом центрального кубика верхней грани.
Этап 5, Переставляем верхние реберные кубики.
Этап 6, Переориентируем верхние угловые кубики.
Этап 7. Переставляем верхние угловые кубики.
Попробуйте разработать этот алгоритм подробно и дать его детальное описание,