Л.А. Калужнин, В.И. Сущанский - Преобразования и перестановки (1127096), страница 26
Текст из файла (страница 26)
пенные для подходящих граней, позволяют одновременно менять ориентацию любых двух из средних кубиков (почему?). Выполняя совместную переориентацию пар средних кубиков, можно все их расположить на своих местах так, как оии располагаются в начальном состоянии куба. Это следует из того, что состояние, в котором все средние кубики, кроме одного, правильно располо- ' жены на своих местах, не может быть допустимым. Эта п 3. Расстановка на своих местах угловых кубиков. Степень ряс. 48 (ХУХ лУ-')л (4) Рис. 47 коммутатора вращений Х, г' соседних граней х, у осуществляет одновременную перестановку пар угловых кубиков, которые принадлежат граням, имеющим с х, у два общих ребра.
Например (рис. 47), третья степень коммутатора ФПФ-'П л переставляет угловые кубики так: фвл-л.фвп, )' пнф-л пнт, фвп-~фал, ( пнт -л. пнф. .Произведение степеней коммутаторов (ХгХ- г-л) ()'- Х- уХ)л (5) осуществляет перестановку трех угловых кубиков, принадлежащих грани х.
Например, серия вращений (ФВФ-лВ-л)л (П-'Ф-'ПФ)' перемещает угловые кубики фасадной грани следующим образом: фнл-л'фвл л.фнп-л фнл. После выполнения каждой из серий поворотов (4), (5) средние кубики не меняют своего положения; остаются на своих местах также угловые кубики, которые не учитывались при рассмотрении серии. Иб С помощью последовательностей вращений вида (4), (5) все угловые кубики можно расставить по своим местам (проверьте!).
Прн этом надо учитывать, что вдопустимом состоянии не может случиться так, чтобы все средние кубики были расположены как в начальном состоянии, а все угловые, кроме двух, стояли на своих местах: если не все угловые кубики стоят на своих местах, то их не меньше чем 3. Этап 4. Переориентация угловых кубиков, стоящих на своих местах. Последовательность вращений о = [(Х- гХЛ-') (г- Уг)'- ) (У'-*ХУХ-')1 (б) одновременно поворачивает каждый из трех угловых кубиков, принадлежащих грани х, вокруг соответствующей диагонали куба на угол 2п/3 по часовой стрелке.
А послздовательность вращений а-' поворачивает эти кубики вокруг тех же осей на угол 4п(3 по часовой стрелке. Например, вращения а, составленные для граней ф; в, п, поворачивают угловые кубики фвл, фвп, фнп (рис. 481. При этом расположение и ориентация других кубиков не изменяются., Понятно, что с помощью последовательностей вращений о и и-' можно переориентировать любые 3 угловых кубика. Если учесть, что вдопустимом состоянии не может случиться так, чтобы все средние кубики были расположены как в начальном состоянии, все угловые кубики были на своих местах и лишь один из них был бы неправильно повернут, то закончить этап 4, а следовательно, и сборку кубика в целом не составляет труда. Описанный здесь алгоритм — далеко не самый экономный. Сборка кубика с его помощью может быть весьма длительным процессом, требующим большого числа ходов.
Существуют более экономные алгоритмы, в частности, описанные в отмеченных выше статьях. Однако приведенный алгоритм поможет нам построить математическую теорию игры, после чего читатель сам сможет разрабатывать такие алгоритмы. 3. Опишем группу перестановок, которая «управляет» состояниями кубика Рубика. Полностью описать состояние куба можно, указав место, которое занимает каждый маленький кубик в нем и, ориентацию кубика на этом месте.
Средние кубики могут быть ориентированы на каждом месте двумя способами, а угловые — тремя. Пус|ь кубик Рубика находится в начальном состоянии. Занумс1зг руем его угловые кубики в каком-либо порядке числами 1, 2, ..., 8, а средние числами 9, 10, ..., 20. Этими же числами занумеруем места, на которых стоят маленькие кубики. Любое состояние куба после этого можно характеризовать перестановкой, указывающей номера угловых и средних кубиков, стоящих при этом состоянии на местах 1 — 20. Если в состоянии 5 на месте с номером 1 стоит кубик с номером 1; (1==1~20), то этому состоянию однозначно ставится в соответствие перестановка ! 2 3 ... 20 'В = й й 1з " )»о) Перестановка ч>з определяет только места, занимаемые маленькими кубиками, состояние 5 ею однозначно не определяется — нужно определить еще ориентацию кубиков.
Для задания ориентйции угловых кубиков фикс ир у е м две противоположные грани куба — например, верхнюю и нижнюю. Предположим, что эти грани окрашены в красный (верхняя) и желтый (нижняя) цвета. Любой угловой кубик имеет либо красную, либо желтую грань. Угол, на который нужно повернуть угловой кубик вокруг вершины куба, чтобы эта его грань заняла положение вверху (красная) либо внизу (желтая), и определяет ориентацию углового кубика. Этот угол может равняться О, 2п~3, 4п)3.
Условимся обозначать ориентацию углового кубика, соответствующую повороту на О, символом <0», повороту на 2п)3 — символом <1», а повороту на 4п(3 — символом «2». После этого при любом состоянии куба расположение углового кубика с учетом его ориентации описывается парой чисел (», з), 1 (1«8, 0(»=-2, где 1 — номер места, на котором он стоит, з — его ориентация. При передвижениях кубика эта пара изменяется — как первая координата, так и вторая. Для того чтобы указать ориентацию среднего кубика, на каждом ребре куба фиксируем направление (укажем стрелку) и <нарисуем» такое же направление на среднем кубике так, чтобы в начальном состоянии оба направления совпадали.
После этого при любом состоянии куба положение среднего кубика с учетом его ориентации описывается парой чисел (1, 1), 9(1 ( 20, 1= 0,1, где 1' — номер места, на котором стоит кубик, а «=О, если ориентации кубика и ребра, на котором он расположен, совпадают, и 1=1, если они противоположны. Таким образом, состояния куба однозначно характеризуются перестановками 133 множества К=(1, 2, ..., 8) х(0, 1, 2) () (9, !О, ..., 20) х(0, Ц.
Каковы же эти перестановки? Поскольку при вращениях граней средние кубики могут передвигаться только иа место средних, а угловые — на место угловых, то любая перестановка аз множества К, задающая некоторое состояние куба 5, определяет .некоторую перестановку кз' из множества (1, 2,;., 8) х(0, 1, 2) — перестановку угловых кубиков с учетом ориентации — и некоторую перестановку аз' из мнох«ества (9, !О, ..., 20) х(0, Ц вЂ” перестановку средних кубиков с учетом ориентации. Эти перестановки действуют на непересекающихся множествах, объединение которых совпадает с К.
Поэтому, согласно определению прямой суммы перестановок, получаем аз = с!а' Я аУ'. Посмятрим теперь, как же устроены перестановки множесгв угловых и средних кубиков с учетом ориентации. Задать перестановку аз' означает указать место каждого из угловых кубиков (чему соответствует перестановка ~рз' множества (1, 2, ..., 8), являющаяся ограничением перестановки ~рз на это множество) и указать ориентацию каждого из угловых кубиков (чему будет соответствовать задание для каждого из кубиков «своей» перестановки на множестве (О, 1, 2), которая является с~слепые цикла длины 3). Итак, перестановке аУ сопоставляется набор 1<рз', ти т»? ., т»1, где т; определяет ориентацию(-го кубика (1 (1(8).
Иными словами, перестановка и3' является сплетением перестановок т„т, ..., т, множества (О, 1, 2), содержащихся в циклической группе С, этого множества, с помощью некоторой перестановки" из симметрической группы 5». Аналогично, задать перестановку а7 означает указать место каждого среднего кубика (чему соответствует ограничение Ч~»в пеРестановки «Рз на множество (9, 1О, ..., 20)) и его ориентацию (чему соответствует задание для каждого из кубиков «своей» перестановки т; на множестве (О, Ц). Это означает, ч го перестановка аз1' является сплетением перестановок т„т»„..., т, множества (О, Ц с помощью некоторой перестановки из симметрической группы 5»», действующей на множестве (9, !О, ..., 20!.
Таким образом, можно сказать, что любое состояние кубика Рубика однозначно описывается перестановкой 139 множества К, имеющей вид [~р 1 т1! тм Р1 тз]®[Ф 1 та т10 ' ° '> тВО]~ (7) где ~р~м ен 5„~р<ю ~ 5м (5м действует на множестве (9, 1О, ..., 20)), т; еи Са при 1=1, 2, ..., 8 и т; я 5, при 1=9, 10, ..., 20. А множеству всех состояний соответствует группа перестановок Н =(5вгСе) Я(5мг5з), действующая на множестве К. Отсюда сразу получаем, что общее число состпяний кубика Рубика равно (8! 3') (121 2"). Опишем теперь перестановки, которыми задаются допустимые состояния волшебного кубика.
Они, очевидно, будут образовывать группу, поскольку произведение перестановок, отвечающих допустимым Состояниям, тоже задает некоторое допустимое состояние (почему?). Покажем, что эта группа состоит из тех перестановок группы Н вида (7), для которых выполняются следующие три условия: а) Ч~Ф" я ~р<ю — четная перестановка; б) т, т, ... тз — — е †тождественн перестановка множества (О, 1, 2); в) та тм ...*т„=е — тождественная перестановка множества [О, Ц. Проверим сначала, что условия а), б), в) необходимы. Вращение любой из граней на угол и/2 определяет циклическую перестановку на множествах угловых и средних кубиков этой грани. Пусть при таком вращении куб переходит из состояния 5 в состояние 5'. Если состояние 5 описывается перестановкой И т ° ° тв] С+) [тз ~ т " ° тра].
а состояние 5' — перестановкой [ЧУ; оь "., оз]®[<рУ' па " ом] то фз =Чз' ° и, ~рзч =<рз' ° и, где и — циклические перестановки множеств угловых и средних кубиков этой грани. Это циклы длины 4, т. е. нечетные перестановки. Поэтому перестановки К' и щУ, 9~3' и ~р2! имеют соответственно противоположные четности. Следовательно, четности перестановок ~рзп Я ~р3' и <рзп Я «рзч совпадают.
Если состояние 5-допустимое, то от него можно перейти к начальному состоянию с помощью серии вращений граней. Р)а каждом шаге. при этом будет появляться новое состоя- ыо ние Я', четность подстановки Д~ (1) Ч~зп длЯ котоРого совпадает с четностью ~рК О+~рХ. Поэтому четность подстановки срз'® рЯ' для допустимого состояния 5 совпадает с четностью такой подстановки для начального состояния, а ему соответствует четная подстановка.
Итак, условие а) необходимо. Далее, легко проверяется, что перестановки, определяющие ориентацию угловых кубиков, не изменяются при произвольных вращениях верхней и нижней граней куба и при вращениях остальных граней на угол и. При вращениях одной из граней ф, п, л, т на углы п(2, Зя/2 две перестановки, задающие ориентацию кубиков противоположных вершин, умножаются на цикл (О, 1, 2), а две другие — на цикл (О, 1, 2)'=(О, 1, 2)-'. Следовательно, произведение всех таких перестановок ть т;, ..., т, для каждого допустимого состояния такое же, как и для начального, для которого оно, очевидно, равно е. Перестановки, определяющие ориентацию средних кубиков, либо не изменяются при поворотах грани, либо все изменяются на противоположные (т. е.
умножаются на транспозицию (О, 1)). Поэтому нх произведение остается прежним, т. е. выполняется условие в). Описывая алгоритм сборки кубика, мы использовали трн совсем неочевидных утверждения: 1) состояние, в котором все средние кубики, кроме рдного, правильно расположены на своих местах, не может быть допустимым; 2) состояние, в котором все средние кубики правильно расположены на своих местах и все угловые, кроме двух, стоят на своих местах, не может быть допустимым; 3) состояние, в котором все средние кубики правильно расположены на своих местах, все угловые -тоже, но один из них неправильно повернут, не может быть допустимым. Правильность утверждений 1) — 3) следует из необходимости условий а) — в) для того, чтобы перестановка множества К определяла допустимое состояние кубика.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
