Л.А. Калужнин, В.И. Сущанский - Преобразования и перестановки (1127096), страница 23
Текст из файла (страница 23)
38). На восьми фишках выписаны буквы х, а, м, е, л, е, о, и. Фишки в случайном порядке расставя лены на клетках, расположенных в вершинах многоугольяика. Цель игры з состоит в том, .чтобы, передвигая фишки по соединительным отрезкам, Рис. 38 разместить их в правильном порядке, т. е. так, чтобы при чтении по часовой стрелке, начиная с клетки 1, получилось слово чхамелеонэ. Докажите, что прийти к правильному размещению фишек можно при любом их начальном расположении. О,Доказать, что теория игры ев пятналцатьэ остается в силе и для игры чв восемьэ, правила которой такие же, как и при игре чв пятнадцатьэ, но здесь 8 фишек с номерами.
1, 2, 3, 4, 5, 6, 7, 8 перемещаются в квадрате с 9 клетнами. 9. Пусть на фишках для игры «хамелеона вместо букв выписаны числа 1, 2, 3, 4, 5, 6, 7, 8. Правила игры остаются прежними. Доказать; что полученная таким образом игра в точности совпадает с игрой эп восемьэ. 10. По аналогии с игрой чв 15э проведите исследование игры эз двадцать четыреэ. 120 й !9 певестАИОВОчные коистРукйии Нам понадобится в этом параграфе операция прямого произведения множеств.
Прямым произведением мкожеств Мь М» называется множество всевозможных упорядоченных пар вида (п»ь т»), первая компонента которых является элементом множества Мь а вторая — элементом множества М,. Прямое произведение множеств М, и М» обозначается символом М,хм,. Например, имеем (1, 2, 3) х )а, Ь) = ((1, а), (1, Ь), (2, а), (2, Ь), (3,'а), (3, Ь)), (1, 2) х(2, 3, 4) =1(1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4)).
Понятно, что для конечных множеств М» и М, имеет место равенство . ) м хм»(=)м,)х~м«~. Наглядно прямое произведение множеств удобно изображать в виде прямоугольной решетки: элементам множеств М, и М, ставятся в соответствие точки на «координатных осях» М„' М, (рис.
39), через эти точки проводят соответственно горизонтальные и вертикальные прямые, образующие « прямоугольную решетку, и узлам этой решетки соответствуют элементы прямого произведения. »«( Мы уже использовали такой способ изображения, например, Рис. 39 в 9 12 (рис 32). Будем рассмат. ривать только прямые произведения множеств натуральных чисел.
Условимся располагать элементы прямого про. извед ния (1, 2, ..., Ц х(1,2,..., () вследующем порядке: (1, 1), (1, 2), ..., (1, 1), (2, 1), (2, 2), ... ...,. (2, 1), ..., (й, 1), (й, 2), ..., (Ь, 1), (1) т. е. упорядочим по возрастанию вначале первые компоненты, а при равных первых' компонентах — вторые, и тоже по возрастанию. (Такой порядок называется лексикографическим,) Рассмотрим теперь конструкции, которые позволяют по перестановкам на множествах М, и М» строить перестановки на множествах Л(,()м, и М,хм,.
Самая простая среди них -это так называемая сумма перестановок. И1 "='12 4 ! 3)' !)=(8 7 6 6)' 71 2 3 4 5 6 7 81 ®~ 12 4 1 3 8 7 6 57' Тогда 2. Согласно доказанной в 2 5 теореме, любую перестановку можно разложить в произведение взаимно нро. етых циклов. Понятие циклической перестановки мы рассматривали в двух различных смыслах — это собственно циклические перестановки и их расширения на ббльшне множества.
В формулировке теоремы понятие цикла употребляется во втором смысле, т. е. все циклические перестановки в разложении %=т1 $з" 'тю перестановки <р в произведение взаимно простых циклов— это перестановки на множестве М, являющиеся расширениями циклов ~„~р„..., ~р„которые действуют на непересекающихся подмножествах Мм Мм ..., М, множества М. Применяя з — 1 раз конструкцию прямой суммы к циклам щ, ф„..., <р„получим равенство ч= р В р'.9" С+ч' Из 'этого примера понятно, что сумму перестановок а, )) можно получить также следующим образом: рассмотреть расширения и и р этих перестановок на множество М,() М, и перемножить их.
Итак, а(+))) =й р. Ь Рассмотрим теперь несколько более сложную конструкцию, которая называется прямым произведением пере- 122 Пусть множества Мг и Мз не имеют общих элементов, т. е. М,ПМз — — ф, и а — некоторая перестановка на множестве М„, а р — перестановка на множестве Мз. Суммой (прямой) перестановок а и р называется перестановка на множестве М1() М„которая на элементы М, действует так, как а, а на элементы М, — так, как р.
Мы будем обозначать эту перестановку символом а®~. Согласно определению имеем, что а~+)р действует на произвольный элемент и ен М,()М, так: ( (т)а, если ш ен Мь 4 Примеры. 1. Пусть М,= (1, 2, 3, 4), М,= (5, 6, 7, 8! и на множествах М„М, заданы соответственно переста- новки становок. С помощью этой конструкции по перестанов- кам а и р на множествах М, и М, соответственно строится перестановка на прямом произведении М,хМ,. Эта пере. становка действует на произвольный элемент (тп и,) из прямого произведения М4ХМ, так, что перестановка а изменяет первую компоненту пары, а перестановка () — ее вторую компоненту.
Мы будем обозначать так построен- ную перестановку символом ах р. Таким образом, для произвольной пары (ть и!з) ~ МсхМа (спп сп,) (ах (1) = ((!и!)а, (т~)(1). ~ Примеры. 3. Пусть (2 !)' ~ (2 3 1)' Тогда ахр — перестановка на множестве ((1, !), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3)). Согласно определению, имеем (1, 1) (а х р) = ((1)а, (1) р) = (2, 2), (1, 2) (ахр) =((1)а, (2)р) =(2, 3), (1, 3) (ахр) =((1)а, (3)р) =(2, !), (2, 1) (я х ()) = ((2)сс, (1) Р) = (1, 2), (2, 2) (ссх()) =((2)а, (2ф) =(1, 3), (2, 3) (ссх р) =((2)а, (3)р) =(1, !). Таким образом, перестановка ах() имеет следующую таблицу значений: (: (1, 1) (1, 21, (1, 3! (2, !1 (2, 21 (2, 3)1 (2, 2) (2, 3), (2, 11 (1, 2) (1, 3) (1, 1)/ ' Легко понять, как построить эту таблицу непосредственно по таблицам перестановок сс и ().
Ранее мы оговорили, что все' перестановки будут рассматриваться над началь- ными отрезками натуральных чисел. Перестановке ссх(1 можно поставить в соответствие перестановку на множе- стве (1, 2, 3, 4, 5, 6», занумеровав элементы прямого произведения следующим образом.' 1 2 3 4 5 б (1, 1) !1, 21 (1, 3) (2, 1) (2, 2) (2, 31 Получим следующую перестановку: ) (5 6 4 2 3 !)' Эту перестановку можно сконструировать в два этапа. А именно: разбиваем множество (1, 2, 3, 4, 5, б) на две !23, одинаковые части «1, 2, 3) «4, б, 6) и на каждой из этих частей производим такую же перестановку, как и Получим перестановку (1 2 3 4 5 6) Затем переставляем эти части во второй строке таблицы, не изменяя порядок элементов в них.
Конечно, переход от записи акр в виде (2) к записи (3) зависит от выбора нумерации. Но если нумерацию считать фиксированной, то любая из этих таблиц однозначно восстанавливается по другой. Поскольку приходится использовать как одну из них, так и другую, условимся элементы множества М, х М, нумеровать согласно порядку (1). 4. Перестановку !1 2 3 4 5 6 7 8 9! (8 9 7 5 6 4 2 3 1/ естественно сопоставлять произведению перестановок 2 3~ „ (! 2 З~ В самом деле, перестановка ях«) задается таблицей (:::::::::) (1, 1) (1, 2) (1, 3) (2, 1) (2, 2) (2, 3) (3, 1) (3, 2) (3, 3)1 (3, 2) (3, 3) (3, 1) (2, 2) (2, 3) (2, 1) (1, 2) (1, 3) (1, 1)) ' которой при задании нумерации элементов прямого произведения «1, 2, 3) х «1, 2, 3) соответственно упорядочению (1) отвечает как раз таблица у.
!ь С помощью второй конструкции можно строить перестановки на прямом произведении М,хМ! множеств М„ М„ применяя ее не к двум перестановкам, а к (й+ 1), где й = ~М~~. Пусть а — некоторая перестановка на множестве М„а «)ь ~„..., «)„— перестановки на множестве М,. Множество М~ХМ, разбивается на й непересекающихся частей следующим образом: М,х М,= «(1, 1), (1, 2), ..., (1, Ц () «(2, 1), (2, 2), ... '...', (2', 1И ..'.
() «(й, 1)', (й' ,2),' ...', (й, !)) (! = «М,~). Преобразование, определяемое элементами о!, рь Р„..., Ры ДействУет на пРоизвольнУю паРУ (1, )) на М,хМ, так, что на первую компоненту пары действует перестановка а, а на вторую — перестановка р! (1 (1(й). Иными словами, на первые координаты всех пар из М~хМэ действует, перестановка аг на вторые координаты пар из 124 множества ((1, 1), (1, 2), ..., (1, Ц вЂ” перестановка [)и на вторые координаты пар из множества [(2, 1), (2, 2), ...
..., (2, Ц вЂ” перестановка ()» и т, д. Будем называть так построенную перестановку сплетением перестановок [)„(1„..., й» с помощью перестановки а и обозначать символом [а; ()„[)», ..., [)»]. Игак, согласно определению, действие сплетения перестановок рь р», ..., р» с помощью перестановки а на , произвольный элемент (1, 1) ~ М, х М, определяется равенством (1, ))[а; [)„()„..., р»]=((1)и, (1)й»).
То, что прямая сумма н прямое произведение перестановок — снова перестановка, вполне понятно и не требует дополнительных проверок. Для сплетения это совсем яе очевидно. Поэтому покажем, что для произвольных перестановок а, ()„й„..., (1» сплетение [я; ()„р„..., й»] является перестановкой на множестве М»хМ». Поскольку М, и М,— конечные множества, то достаточно проверить, что преобразование [оп Рь Р»,'", Р»] инъективно. Пусть (1,')), (1', /') — различные пары из прямого произведения М»хМ». Зто означает, что выполнено по крайней мере одно из неравенств (~Г или )чь)'. Если (чьГ, то (1)явь(1')а и, независимо от того равны между собой числа ), )' или нет, пары ((1)а, ())(3;) и (((')с», (1')р;) между собой различны. Пусть теперь (=Г.
Тогда )чь/' и пары ((1)а, (1)~Д, ((1)а, (1'ф) между собой различны, поскольку ())р;чь()')~ь Итак, для произвольных различных пар (1, 1),(»', )') из М,хМ, имеем (1, )) [а; [)и р», ", [)»]чь(~', 1')[пп рм ()», "., [)»], т. е. сплетение перестановок [пп рп р»,"..., ()»] снова будет перестановкой. 4 Примеры. 5. Пусть М»=(1, 2), М»=(1, 2, 3), "=(2 1) — перестановка на множестве М„ (2 ! 3)' (» (3 2 1) — перестановки на множестве М,. Сплетение [оп ()ь р»] нррестановок р», р» с помощью а действует на множестве !23 МдхМ, так: (1, 1) (а; ()д, Я= ((1)сд, (1)~д) =(2, 2), (1, 2) [а; ()ь рд] = ((1)а (2) рд) = (2. ! ) (1, 3) [а; ()„()д] = ((1)а, (3) Рд) = (2, 3), (2, 1)[сд; р„рд]=((2)а, (1)рд) =(1, 3), (2, 2)[а; Дд, !)д]= ((2)а, (2)!)д) =(1, 2), (2, 3)[а; [)д, [)д]=((2)а, (3)рд) =(1, 1) Таким образом, перестановка [а; [)„рд] имеет таблицу значений (::::::) (1, 1) (1, 2) (1, 3) (2, 1) (2, 2) (2, 3)) (2, 2) (2, 1) (2, з) (1, з) (1, 2) 6, 1)) ' При принятой нами нумерации множества Мд х М, ей сопоставляется следующая таблица: (1 2 3 4 5 6) 6.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
