Л.А. Калужнин, В.И. Сущанский - Преобразования и перестановки (1127096), страница 25
Текст из файла (страница 25)
Из публикаций в отечественных журналах отметим статьи И. Константинова «Венгерский кубик» («Наука и жизны, 1981, № 3; 1982, № 2), В. Залгаллера, С. Залгаллера «Венгерский шарнирный кубик» («Квант», 1980, № 12), М. Евграфова «Механика волшебного кубика» («Квант», 1982, № 2), В. Дубровского «Алгоритм волшебного кубика» («Квант», 1982, № 7), «Математика волшебного кубика» («Квант», 1982, № 8), «Кубик в картинках» («Квант», 1983, № 9),, Ю. Демкова «Поворачиваем кубики» («Квант», 1981, № 12) и некоторые другие. Рис. 4! Уже нз названий некоторых из этих публикаций видно, какими вопросами интересуются при рассмотрении кубика Рубика.
В первую очередь, хочется узнать, как же он устроен, каков механизм, позволяющий осуществлять такие вращения. Во-вторых, естественно возникает желание научиться переходить к начальной окраске кубика из любого возможного его «пестрого> состояния. Конечно, если «пестрая» раскраска получена из начальной с помощью ряда вращений плит, то перейти от такого состояния к начальному всегда можно. Поэтому хочется иметь набор правил — алгоритм, который обеспечит достижение начального состояния из любого возможного. Для выработки такого алгоритма строят математическую модель решаемой задачи.
В этой-то модели и возникает группа перестановок, связанная с кубиком Рубика. Вспомогательные задачи, которые необходимо решить,— это научиться строить системы образующих возникающей группы перестановок и раскладывать ее элементы в произведение образующих элементов. Обе задачи упрощаются, если заметить, что группа перестановок, связанная с кубиком Рубика, строится из уже известных читателю групп с помощью рассмотренных,в предыдущем параграфе конструкций. Вначале рассмотрим, как устроен волшебный кубик.
В нем 27 основных деталей: крестовина (рис. 41 а), 12 боковых кубиков (рис. 41 б), 8 угловых кубиков (рис, 41 в) 1З1 и б центральных-кубиков (рис. 41 г). На самом деле, как видно из рис. 41, «кубики» вЂ” это совсем не кубики, а более сложные тела. В большой куб они сложены так, что извне кажутся кубиками. Кубики, расположенные в центре -каждой из граней (поэтому мы их будем называть центральными), крепятся на крестовину. У них окрашейа одна сторона (внешняя).' Средние кубики, у которых раскрашены 2 внешние стороны, расположены в середине каждого ребра, а угловые кубики, у которых раскрашены '3 внешние грани, расположены в. вершинах куба. Расположение кубиков в кубе хорошо видно на рис.
42, на котором куб изображен со снятыми передней плитой и одним средним кубиком. Внутренние выступы па средних и угловых кубиках сделаны так, что при составлении куба из этих выступов образуется почти цилиндрическое тело, а на среднем слое образуется кольцеобразное углубление. При повороте плиты цилиндрическое тело вращается в кольцеобразном углублении. Вот и весь механизм кубика Рубика, не считая мелких второстепецных деталей. Рас. 42 ис. 43 2. Остановимся теперь на описании алгоритма приведения кубика Рубика из'«пестрого» состояния в начальное. Условимся вначале о следующих удобных сокращениях.
Поскольку при вращениях плит мы интересуемся лишь взаимным расположением маленьких кубиков в большом кубе, можно считать расположение куба в пространстве фиксированным, т. е. считать его крестовину жестко закрепленной, а центральные кубики — неподвижными. Это означает, что возможны лишь вращения шести внешних плит куба. Обозначим грани куба буквами (рис. 43) 132 «ф» (фасад), «чъ (тыл), «в» (верх), «н» (низ), «л» (левая сторона), «п> (правая сторона). Маленькие кубики можно теперь определять наборами букв: центральным кубикам соответствует одна буква (например, кубику фасада— буква «ф»), средним кубикам †д буквы (например, кубику, принадлежащему фасадной и левой грани,-- буквы «фл»1, угловым кубикам — три буквы (например, кубику, принадлежащему фасадной, левой и верхней граням, — буквы «флв»).
Прописными буквами Ф, Т, В, Н, Л, П будем обозначать вращения соответствующей грани (плиты) иаугол л/2 по часовой стрелке. Вращения против часовой стрелки обозначаются этими же буквами в степени — 1. Это оправдано, поскольку каждое из вращений осуществляет некоторую перестановку множества маленьких кубиков с учетом раскраски и, следовательно, можно говорить об обратной перестановке. Понятно, что обратной к перестановке Ф будет перестановка Ф-', и аналогично для других типов вращений. Последовательностям ' вращений граней будут отвечать «слова», составленные из букв Ф, Т, В, Н, Л, П в степенях .+ 1. Например, словом ФТ'Н-'Л-' = ФТТН-'Л-'Л-'Л-' описывается следующая последовательность вращений: а) фасадную грань повернуть на угол и/2 по часовой стрелке; б) тыловую грань дважды повернуть на угол и/2, или, что то же самое, повернуть на угол и по часовой стрелке; в) нижнюю грань повернуть на угол и/2 против часовой стрелки; г) левую грань повернуть на угол Зл12 против часовой стрелки.
Каждому из этих вращений соответствует некоторая перестановка маленьких кубиков с учетом их раскраски, а всей последовательности — произведение таких перестановок. В результате выполнения серии вращений а) — г) маленькие кубики «пропутешествуют» и займут новые места в кубе. Будем называть расположения кубиков внутри большого куба его состояниями. Если от состояния 5 к состоянию 5' можно перейти серией вращений а, то будем записывать это так: 5' =(5) и. Различные серии вращений могут переводить куб, вообще говоря, в одно и то же 133 состояние. Например, имеем для любого состояния 5: (5)Ф'= (5)Ф-' (5)Т = (5)Т-з (5)Нз = (5)Н-' (5)П'=5, (5)Л Л-'=5.
Читатель без труда продолжит этот список. Состояние куба назовем допустимым, если его можно получить из начального вращениями граней куба. Понятно, что из любого допустимого состояния можно перейти к начальному †д этого нужно просто обратить последовательность вращений. Например, если состояние куба 5 получено из начального состояния 5, в результате серии вращений (1), то, применяя к кубу в состоянии 5 последовательность вращений ЛЛЛНТ-зТ-зФ-з ЛзНТ-зФ-з перейдем к состоянию 5з, т. е.
(5)Л'НТ-'Ф-'=5,. Опишем теперь один из возможных алгоритмов сборки кубика Рубика, т. е. укажем правила, руководствуясь которыми от 'любого допустимого состояния можно пе- . рейти к начальному. В большинстве алгоритмов враще- ния граней, осуществляемые при сборке кубика Рубика, группируются в стандартные комбинации нз двух враще- нийХ, У(Х, У~(Ф,П,Л, В, Н,Т)): а) комбинация Х-'УХ вЂ” сопряжение вращения У с по- мощью вршцения Х; б) комбинация Х-'У-'ХУ вЂ” коммутатор вращений Х, У. Можно рассматривать также сопряжения н коммута- торы степеней основньпг вращений, например: а) Ф-'В'Ф'=Ф'В'Ф' — сопряжение вращения В' с по- мощью вращения Ф'=Ф-', б) ПзВзП зВ з = ПзВ'П'В' — коммутатор вращений и-'(= и ), в-*(= в ). Легко проверяется, что коммутатор основных враще- ний прилегающих граней переставляет три средних кубика циклически.
Например, коммутатор П-'Ф-'ПФ действует на кубики, стоящие на местах фн, фп, пв следующим образом (рис. 44): .фн — з- пв -з- фп. 1 ! При этом некоторые кубики остаются неподвижными, а угловые также перемещаются. Процесс сборки кубика Рубика осуществляется в 4 этапа. К выполнению следующего этапа нужно приступать лишь тогда, когда предыдущий этап полностью закончен. При 1Э4 описании этапов сборки буквами х, у, г будем обозначать какие-то из граней куба, имеющие общую вершину, а символами Х, У, Я вЂ” основные вращения граней х, у, г соответственно. Этап 1. Расстановка на своих местах средних кубиков..Серия вращений ' Х 'Л' '1'-'Х-'УХЕ (2) граней куба х, у, г переставляет два средних кубика, принадлежащие грани х, и оставляет неподвижными остальные средние кубики. Применяя эту серию к некоторому состоянию 5 куба, получим новое состояние 5', отличающееся от 5 расположением угловых и двух средних кубиков.
Например, для серии Ф-'В-'П-'Ф 'ПФВ имеем (рнс. 45) фл -и фв, фв -и фл. Серии вращения вида (2) позволяют переставить любые два из средних кубиков. Для этого нужно с помощью вспомогательных ходов поставить переставляемые кубики на соответствующие места в одной из граней куба, применить серию вращений (2) и, выполняя обратную последовательность ходов, перейти к требуемому состоянию. Рис. 46 Рис.
45 Рис. 44 Этап 1 закончен, если все средние кубики расположены на своих местах. Однако при этом они могут оказаться неправильно ориентированными (цвет среднего кубика грани не соответствует цвету ее центрального кубика). Этап 2. Правильная ориентация средних кубиков, стоящих на своих местах. Произведение трех коммутаторов (Х) -'Х-Ч ) (Ы- )' — Л) (гХ- г-'Х) (з) одновременно поворачивает на своих местах два из кубиков, принадлежащих грани х, не меняя при этом рас- 435 положения других средних кубиков. Например,' серия (ФП-'Ф-'П) (ПВ-'П-'В) (ВФ-'В-'Ф) поворачивает на своих местах средние кубики фв и фп (рис. 46). Последовательности вращений вида (3), выпол.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
