Л.А. Калужнин, В.И. Сущанский - Преобразования и перестановки (1127096), страница 27
Текст из файла (страница 27)
Действительно, для состояний кубика Рубика, не удовлетворяющих требованию 1), очевидно, не выполняется условие б), а для состояний, не удовлетворяющих требованию 3), — условие в). Состояние 3, не удовлетворяющее условию 2), не может быть допустимым, поскольку соответствующая ему подстановка ~рз' ® срыл — нечетная. В самом деле, так как все средние кубики стоят на своих местах, то ~рая — тождественная подстановка, а Ч>ьн — транс1Ф1 позиция. Поэтому ч~з' Я ~рз' — нечетная, как прямая сумма нечетной подстановки с четной. Убедимся теперь, что условия а) — в) являются также и достаточными. Пусть 5 — некоторое состояние кубика Рубика, которое характеризуется перестановкой из группы Н, удовлетворяющей условиям а) — в).
Применим к этому состоянию описанный нами алгоритм сборки кубика. Первый этап алгоритма выполняется беспрепятственно, поскольку его можно применить к любому состоянию и получить нужный результат. Второй этап алгоритма можно провести всегда, если состояние 5 удовлетворяет условию 1). Но это так и есть, поскольку условие 1) — следствие условия б). После осуществления второго этапа все средние кубики правильно расположены на своих местах и полученному состоянию куба отвечает перестановка множества К вида [я~2" т т " тв1 9 а~'~, где епо — тождественная .
перестановка множества (9, 10, ..., 201'к10, 1). Отсюда следует, что перестановка ~р)' — четная. А четную перестановку можно либо разложить в произведение циклов длины 3 (см. упражнение 7 к З 15), либо разбить на произведение пар транспозиций. Поэтому можно осуществить третий этап сборки волшебного кубика. Заметим, что описывая ранее этот и следующий этап, мы намеренно опустили некоторые подробности„теперь читатель легко их восполнит. После третьего этапа сборки состояние куба будет характеризоваться перестановкой множества К вида 1а~»; ть т, . ° ., та)9 а~ 1, где апп — тождественная перестановка множества 11, 2, ..., 8), а т; — циклические или тождественная перестановка множества 10, 1, 2), причем тг тз"" ° та=а. Последнее равенство, как было сказано, означает, что это состояние удовлетворяет условию 3), т.
е. к этому состоянию можно применить четвертый этап сборки кубика. Таким образом, группа перестановок б множества К, характеризующая допустимые состояния кубика, является собственной подгруппой группы Н. Для любой перестановки из Н вида (7) может быть выполнено одно из следующих условий: а) Ч <'~ (~3 ~рпп — либо четная, либо нечетная (2 возможности); 142 б) перестановка т,"с, ...° т, равна либо в, либо (О, 1, 2), либо (О, 2, 1) (3 возможности); в) перестановка т, ° тю ... т„равна либо г, либо (1, О) (2 возможности). Всего можно составить 12 комбинаций этих возможностей, т. е.
перестановка из Н вида (7) может удовлетворять одному из 12 наборов условий. Этими условиями как раз описываются классы смежности группы 6 по подгруппе Н (почему)), т. е. 6 — подгруппа индекса 12 в Н. После всего сказанного становится понятно, как формулировать задачи, связанные с кубиком Рубика на языке теории групп перестановок: В группе 6 фиксирована система образующих перестановок, которые соответствуют вращениям граней кубика -Рубика.
Требуептся указать алгоритм, руководствуясь которым любую перестановку можно было бы разложить .в произведение образующих. При этом важна оценка длины разложения, а она может существенно зависеть от выбранного алгоритма (из предыдущих примеров уже известно, что разложение подстановки в произведение образующих не однозначно). По мере исследования свойств группы 6 такие оценки существенно понижались. В соответствии с одним из первых алгоритмов любую перестановку из группы 6 можно было бы разложить в произведение не более чем 277 образующих из указанной системы, т. е.
«пестрый» кубик можно было бы перевести в начальное состояние не более чем за 277 поворотов граней. После более детального анализа был' разработан алгоритм, позволя!ощий раскладывать перестановки из 6 в произведение образующих длины не более 52, принмм высказано мнение, что можно ограничиться произведениями длины не более 23. На самом деле оценку длины возможных разложений можно исследовать независимо, без рассмотрения алгоритмов, позволяющих такое разложение осуществлять Упражмения !.
Как действуют на угловые кубики серии вращений а)(Ф'П"г", б) (ФПФ-'П-»)», в) ФН»Ф 'Н ', г) Л 'В 'П »ВЛВ 'ПВ? 2. Каков порядок перестановок из группы «», определяемых се- риями вращений Н'П', ВЛВ »Л-х» 3. Проверить, что серия вращений В»ЛП 'Ф»ПЛ-'В ' осущест- вляет пиклнческую переставовку трех средних кубиков, расположен- ных на трех гранях «буквой Т». 4. Указать последовательность вращений граней куба, меняю- щую местами угловые кубики, расположенные по диагонали (с изме- нением ориентации), )43 б.
Проверить, что последовательность вращений П»НщЛ-»ПВз лп-цв»нП» циклически переставляет средние кубики, принадлежащие одной грани, а все другие кубики оставляет на местах, О. «Кубик без раскраски». Маленькие кубики в кубе занумерованы: угловые †числа 1, 2, ...., 8„ а средние †чнсла 9, 1О, ..., 20, Куб не раскрашен. Если пронумеровать места, кото- рые первоначально занимают маленькие кубики. теми же числами, то любое состояние такого куба однозначно описывается некоторой переставовкой множества (1, 2; .;., 20). Какие перестановки этого а~нож«став соответствуют допустимым состояниям куба? 7.
Проверить, что любой цикл (й /, й) длины 3 над некоторым множеством является коммутатором транспозиций над этим мно. жеством. В. Подгруппа некоторой группы С, порожденная всевозможными коммутаторами элементов из б, называется коммун)знаол О, Найти коммутант группы бю О. Предположим, что волшебный йубнк окрашен в 3 цвета так, что в начальцом состоянии противоположные грани окрашены оди- наково, Описать допустимые состояния такого кубика, 10. Кубик Рубика был разобран и заново сложен тзк, что в «начальном» состоянии ему отвечает перестановка вида (7), для которой йц' йэ~р<з' †нечетн, ч» тз " " тз = (О.
1, 2)г *» 'гтв ° ° ° тзэ= (О, 1). Можно ли от любого состояния с такими же свойствами перейти к «начальному»? 11. Докажите, что условия «1 т»1.- т»=а п тз тте ° ° . тзэ В, накладываемые на перестановки. вида (7), характеризую|цие состоя- ния кубика, не зависят от способа определения ориентации угловых и средних кубиков. 12. Алгоритм «послойной» сборки кубика Рубика состоит в следующем: Этап 1. Устанавливаем на своях местах правильно ориенти- рованные средние кубики нижней грани. Эт а п 2, Устанавливаем на своих местах правильно ориентк.
роввнные угловые кубика нижней грани, Этап 3. Устанавливаем на свои места средние кубики сере. динной плиты (параллельной нижней грани), Э т в п 4. Переоряентируем средние кубики верхней грани: средние кубики установим так, чтобы цвет нх верхней грани совпал с цветоы центрального кубика верхней грани. Э т а'п 3, Переставляем верхние реберные кубики. Эт а п б. ГГереориентируем верхние угловые кубики, Э та п 7. Переставлаем верхние угловые кубики. Попробуйте разработать этот алгоритм подробно и дать его детальное описание, й 21. ДРУГИЕ ИГРЫ Кроме игры в «пятнадцатьз и кубика Рубика известны и другие занимательные головоломки, математический анализ которых приводит к рассмотрению перестановок 144 и групп перестановок.
Некоторые из них указаны в упражнениях к 5 18 как обобщение игры «в пятнадцать». Приведем краткое описание нескольких типов игр без подробного рассмотрения их математической теории. Пользуясь рассмотренными здесь образцами, читатель сам смо. жет дать полный анализ той или иной игры. 1. Игры типа игры «хамелеон». Игра «хамелеон», описанная в упражнении 7 к $ !8, совпадает с игрой в «восемь» (упражнение 9 к $18). Однако первоначальная формулировка этой игры допускает различные обобщения, которые можно условно назвать перестановочиыми играми на графах.
Опишем такую игру в общем случае (рис. 49). Пусть имеется некоторый неориентироваиный граф, вершины которого обозначены кружочками и занумерованы. Предположим, что на фишках такой же величины б~н ) выписаны буквы из слов, составляющих определенную 4© фразу. В начальном положении фишки с буквами расположены в вершинах графа так, что если обходить вершины в порядке возрастания »Гх~ номеров, то получим после- з довательность букв в фразе, а вершина с наибольшим г~~ ~г номером останется свободной. Рас.
49 Предположим, что фишки в случайном порядке расставлены в вершинах графа. Цель игры заключается в том, чтобы,- передвигая фишки вдоль ребер графа на свободное место, разместить их в первоначальном порядке, т. е. так, чтобы они образовали выбранную фразу при обходе вершин графа в порядке возрастания их номеров. Конечно, игры такого типа представляют интерес не при всех графах. Одним из естественных условий, скажем, является то, что граф должен быть связным.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
