Л.А. Калужнин, В.И. Сущанский - Преобразования и перестановки (1127096), страница 28
Текст из файла (страница 28)
Если граф уже выбран, то можно исследовать, от каких случайных расположений фишек можно перейти к первоначальному, как фактически осуществить такой переход, как сделать его за наименьшее возможное число ходов и т. и. Следует отметить, что если характеризовать всевозможные случайные расположения фишек перестановками множества номеров вершин 'графа (т. е. считать, что фишки занумерованы теми же чис- 145 лами, что и вершины графа кроме последней), то всем «допустимым» расположениям фишек — таким, от которых можно перейти к первоначальному, — будут соответствовать персстановки, образующие группу (почемур). А различным «ходам» будут отвечать умножения на определенные перестановки из этой группы, которые являются ее системой образующих (почему?).
2. Игра «домино». Эта игра построена по образцу кубика Рубика. Прямоугольный параллелепипед составлен из 18 маленьких кубиков, образующих две квадратные плиты по 9 кубиков в каждой (рис. 50). Кубики скреплены так, что плиты могут свободно вращаться одна относительно другой (рис. 50). Кроме того, могут вращаться и прямоугольные плиты,.состоящие из 5 кубиков. Три таких плиты параллельны одной паре боковых (не квадратных) граней и три †друг. Параллелепипед совмещается сам с собой при вращениях квадратных плит Рис.
52 Рис. 50 Рис. 51 на углы п/2, и, Зп/2 и неквадратных плит — на угол н. После осуществления любого из вращений, при которых параллелепипед самосовмещается, снова можно выполнять произвольное вращение. Маленькие кубики, нз которых составлен параллелепипед, двух цнетов — белого и черного, по 9 каждого цвета. На кубиках, нанесены кружочки как на костяшках домино. На белых кубиках эти кружочки черные, а на черных — белые. Имеется по одному белому и черному кубику с одним кружочком, по одному — с двумя, с тремя и т.
д. до девяти. В,начальном положении квадратные плиты составлены из кубиков одинакового цвета, которые расположены в порядке возрастания числа кружочков справа налево и снизу вверх (рис. 51). Кубики черной и белой плит с одинаковым числом кружочков расположены один под другим, После случайных вращений параллелепипед при- 146 обретает пеструю окраску и нарушается порядок расположения кубиков внутри каждой из плит (по числу кружочков) и из разных плит.
Требуется путем выполнения ряда последовательных вращений привести параллелепипед в первоначальное.-состояние. Алгоритмы, переводящие параллелепипед «домино» в исходное состояние, вначале располагают на своих местах угловые кубики, а затем — кубики середин граней. Отметим, что при анализе этой игры нельзя считать серединные кубики неподвижными — то, что разрешается вращать стоящие посередине прямоугольные плиты, в случае «домино» существенно.
Группа перестановок, связанная с вращениями «домино», состоит из (4! 8!) 8Ч2 2м 3» 5» 7» 1 95. 1Ом элементов! Обобщением игры «домино и кубика Рубика является «волшебный параллелепипед». Имеется в виду параллелепипед, разбитый на'а х т х й маленьких кубиков плоскостями, параллельными его граням. Неквадратные грани можно поворачивать только на 180'. Внутренние плиты' тоже вращаются. Понятно, что анализ этого общего случая основывается на тех же идеях, однако чисто технически все сложнее. Недавно в Венгрии налажен выпуск 4 х 4 х 4 кубиков, называемых «Месть Рубика»! 3.
Волшебный тетраэдр. Тетраэдр разбит плоскостями иа части так, как показано на рис. 52. Части, находящиеся в центрах граней, можно считать неподвижными. При поворотах граней перемещается 4 угловых и б реберных элементов, форму которых читатель легко себе представит на основании рис. 52. В начальном положении каждая грань тетраэдра окрашена в один из четырех цветов. Цель игры прежняя — как перейти к начальному расположению частей, получив в руки «пестрый» тетраэдр. Группа перестановок, связанная с тетраэдром, состоит из (4! 72) (6!!2) (2«!2) (3«13) = 2"3'5 = 3 732 480 элементов.
Аналогичные игры можно образовывать и для других правильных многогранников, например для додекаэдра. Группа перестановок, получающаяся при рассмотрении игры, связанной с додекаэдром, состоит из (30172) (20!(2) (оО»«72) (За»~3) 1 01 !О«« 147 элементов. Это очень большая группа, и поэтому цепочка преобразований, которые необходимо провести, чтобы из заданного положения «волшебного» додекаэдра перейти к начальному, будет, вообще говоря, длинной.
Трудно ожидать, что «волшебный додекаэдр» получит столь широкое распространение, как «волшебный куб». 4. Волшебная пирамидка. Основой этой игрушки является урезанный конус, разбитый плоскостями, параллельными основанию, на 6 частей, которые крепятся на общей оси, совпадающей с осью симметрии конуса, и могут свободно вокруг нее вращаться. В этих частях сделано 6 вертикальных прорезей, в которых крепятся шарики одинакового диаметра. Прорези устроены так, что шарики из них не выкатываются. Шарики окрашены в 6 цветов по числу прорезей. Шарики одного цвета имеют разную тональность — от более светлых до более темных тонов.
Имеется 6 шариков каждого 'цвета, кроме одного цвета, в который окрашено на один рас Зз . шарик меньше, так что одно из 36 мест' для шариков в прорезях остается свободным. Кроме того, в одной прорези имеется внутренняя кнопка, позволяющая «утапливать» шарик, стоящий на этом месте, и ставить на его место другой шарик. «Утопленный» шарик возвращается на свое место как только оно освобождается. Общий вид волшебной пирамидки изображен на рис. 53; пирамидкой она называется потому, что конус, после того как в нем сделаны прорези, стал больше походить на пирамидку. В начальном. положении шарики расположены в прорезях так, что в каждой из прорезей лежат упорядоченные по тональности шарики одного цвета, скажем снизу темнее, а чем выше, тем светлее. Случайными вращениями шести основных частей пирамидки вокруг оси приводят ее в «пестрое» положение.
Требуется с помощью таких же вращений, перемещений шарика в одной из прорезей на свободное место, <утаплнвания» одного из шариков перевести пирамидку в начальное состояние. Игра эта интересная, однако она существенно проще игры «кубик Рубика». В заключение отметцм также, что югославский математик В.
Чепулнч в 1979 г. предложил перестановочную 1«8 модель для анализа шахматной игры. Построение такой модели требует довольно длинных выкладок, и пока неясно, может ли она применяться в шахматной теории. Поэтому, хотя сзма модель достаточно занимательна, мы ее описывать здесь не будем. Упражнения Е Неориентированный граф называется лолныл, если любые две его вершины соединены ребром. Рассмотреть игру типа «хамелеон» для полного графа.
В частности, установить, можно лн от любого расположения фишек в вершинах, такого графа перейти к начальному расположению? Если зто так, то какое наибольшее число ходов не- обходимо осуществить для перехода к начальному расположению фишек в случае полных графов с тремя, четырьмя, пятью вершинами? 2.
Построить неориентированный граф с шее надцатью верши- нами, перестановочная игра на котором совпадала бы с ,игрой «в пятнадцаты, 3. Лоха»ать, что группа перестановок, получаемых при враще- ниях «домино», состоит из (4! 8!)8!12 перестановок, 4. Какие перестановочные конструкции используются при по- строении группы перестановок для «домино». б. Разработать алгоритм, позволяющий от любого допустимого расположения кубиков в «доминоэ перейти к начальному.
6. Проверить, что группа перестановок, получаемых при враще- , ниях «волшебного тетраздраэ, состоит из (4!?2) (6(72) (2«(2) (3«/3) элементов. 7. Можно ли от любого расположения шариков в волшебной пирамидхе перейтн к начальному? ОТВЕТЫ, УКАЗАНИЯ, РЕШЕНИЯ 1. а) () й) (х) =Ох+13, (и ° 1) (х)=ба+11; б) (1 л)(х)=хэ+10хт+25хч+3, (д 7)(х)=ха+!4хз+57хз.+72! в) (7 я) (х)=хз+бхч+ 1Зхэ+11, (8 ()=хе+2хч+2хз+хэ+х+3, 14х+ 11 г) (7 д)(х)= не определена, 3 если хчь — — х~1, 2' 3 если х= — — или х=1; 2 х+1 (л ))(х)= х+2 ' не определена, если х~ — 2, х~!.
если х — 2 или х=1, 2. а) Замкнуто; б) замкнуто; в) ааюсяуто; д) незамкнуто, 150 2. При лг(л существует л(л — 1) ... (л — т+!) разных инъекций множества А в множество В. 3. Решение. Пусть В есть л-элементное множество. Зафикси. руем произвольное множество А, г А ~=т. Образ множества А при лгобом инъективном отображении А-г В будет некоторым лг-элементным подмножеством множества В.
Множество А будет иметь тот же самый образ А'<=В при разных инъекциях тогда и только тогда, когда они будут отличаться на некоторую биекцию множества А в себя. Поскольку ~ А' ~=, 'А ,'=гл, то существует лг! различных биекций А л (л — 1) ... (л — гч+ 1) на себя, А поэтому есть Сю= "' различных аь т! элементных подмножеств множества В. 5.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
