Л.А. Калужнин, В.И. Сущанский - Преобразования и перестановки (1127096), страница 22
Текст из файла (страница 22)
Здесь мы приведем доказательство этого факта, использовав теорию перестановок. Сначала коротко опишем смысл игры. В плоской квадратной коробке размещены 15 одинаковых фишек квадратной формы, одно место остается свободным. Фишки занумерованы числами от 1 до 15 и размещены в определенном порядке (например, так, как на рис. 34 а). Не вынимая фишек из коробки, а лишь передвигая друг за другом нв свободное место, нужно разместить нх в порядке возрастания номеров так, как на рис. 34 б. а й Рис. 34 Оказывается, что прийти к такому размещению фишекв будем называть его стандартным — можно не всегда.
Существуют позиции, от которых этот переход осуществить нельзя. Договоримся называть начальными те размещения фишек в коробке, в которых свободное место остается в правом нижнем углу. В другом случае будем говорить просто про позицию игры. С каждым размещением фишек в коробке можно связать определенную перестановку на множестве М = =11, 2, 3, ..., 15, 161, считая, что свободное место — это фиктивная фишка с номером 16.
Для этого занумеруем места, которые могут занимать фишки, числами от 1 до 16 так, чтобы порядок нумерации совпадал с порядком стандартного размещения фишек. Следовательно, каждое размещение фишек однозначно характеризуется перестановкой на множестве М, первый ряд которой составляют номера мест, а второй — номера фишек, которые на этих местах стоят. Например, размещение фишек на рис. 34 а 11$ описывается перестановкой 123 45678 9101112131415161 96313157214 4 811101512!6!' а размещение фишек на рис.
34 б — единичной перестановкой. Начальные размещения можно однозначно описывать перестановками на множестве М,=11, 2, ..., 1б~, так как для них фиктивная фишка «стоит» на месте с номером 16. Переход от позиции, которая характеризуется перестановкой вр, к позиции, которая характеризуется перестановкой ф, если он возможен, осуществляется за несколько «ходов», причем каждый ход — это передвигание на свободное место какои-нибудь соседней фишки. Если свободным является !'-е место, а фишка, которая будет передвигаться, имеет номер ат и стоит на 1-м месте, то после перемещения эта фишка будет стоять на в-м месте, а !се место освободится.
оначит, за один ход'от размещения 1 2 ... 1 ... 1 ... 161 =(::::::: ) ав ав " 16 .. ат ... а«вl мы переходим к размещению 1 2 ... ! ... ! ... 16 врв = -( ав ав ... ав ... 16 ... авв) ' Следовательно, перестановку вр мы умножаем на транс- позицию и имеем равенство «рв=вр 6,. Если от позиции, которая описывается перестановкой врм можно перейти к новой за один ход, то найдется такая транспозиция б„что перестановка врв, которая отвечает новой позиции, будет связана с вр! равенством Допустим теперь„ что для перехода от позиции вр к позиции ф нужно сделать й ходов. Это означает, что существуют такие транспозиции бь 6„ ..., 6» вида (1, 1б), для которых справедливо равенство ф=вр.б» 6» ... 6». 1!6 На свободное место каждый раз передвигается соседняя фишка, а это накладывает определенные ограничения на произведение б, ° 6, ... 6»; Если от начального размеи(ения ~р удается перейти к стандартному, то можно подобрать такие транспозиции бь 6„..., б, отмеченного вида, чтобы вьтолнялось равенство ~р ° 6, б, ...
° б,=е, откуда ~р=6,' ° б,' ... 6,'=6, б,.... б,. Но такое произведение не может быть произвольным, так как последовательности транспозиций 6„6„..., б, отвечает последовательность ходов, причем на свободное место каждый раз передвигается соседняя фишка. Покажем сначала, что когда от начального положения»р можно пе- У рейти к стандаргпному, то перестановка»р — четная. Я (7,З Зануыеруем ряды и столбцы, составленные из фишек так, как на рис. 35. При каждом' перемещении 4 (в «) фишки на свободное место (переставлении ее с фиктивной) сумма Рвы зз номеров ряда и столбца, в которых стоит фиктивная фишка, увеличивается или уменьшается на единицу.
Действительно, место каждой фишки однозначно характеризуется парой чисел ((,!)(1, ! = 1, 2, 3, 4). Если фиктивная фишка «стонт» на месте (1, !), то очередной ход можно сделать четырьмя способами: (1, !) -» (! — 1, !) (! чь ! ), (1, !) -~ (! + 1, /) (! ~ 4), (1, !) (1, / — 1) (!' ч 1), ((, !) -~ (1, у + 1) ()' Ф 4), или лишь двумя или тремя из них, если фиктивная фишка «стоит» возле стенки коробки. В каждом из'этих случаев сумма !+! заменяется на !+)+1 или на !+/ — 1, т.
е. увеличивается или уменьшается на единицу. Пусть теперь задана некоторая начальная позиция»р. Пустое место в этой позиции по нашей нумерации имеет «номер» (4, 4). Если после некоторого количества передвижений фишек на свободное место перейдем к стандартной позиции, то фиктивная фишка вновь будет иметь такой номер. Поскольку на каждом шаге (при каждой транспозиции) четность суммы номеров ряда и столбца, !!7 в которых «стоит» фиктивная фишка, изменяется, оиа может вернуться на место (4, 4) лишь через четное число ходов. -Следовательно, перестановка ~р раскладывается в произведение четного числа транспозиций, т.
е. она четна. Оказывается, что условие четности перестановки, которая характеризует начальное расположение фишек, является и достаточным для того, чтобы от этой позиции можно было перейти к стандартной. Доказывать зто утверждение для всех четных перестановок не нужно, потому что, как легко понять, когда от каждой из позиций, которые описываются перестановками ~р и ф, можно перейти к стандартной, то это удается осуществить и от позиции «р*ф. Поэтому достаточно убедиться в этом лишь для таких перестановок, в произведения которых раскладывается каждая четная перестановка. Возьмем, например, перестановки (1, 2, 3), (1, 2, 4), (1, 2, 5), (1, 2, 15). (1) «л ««г Все фишки в коробке, кроме тех, которые стоят на первом и втором 7~ Гэ «««г местах, можно «связать» в одну цепь, которая может двигаться так, чтобы взаимное размещение звеньев цепи Рис.
36 не изменялось (если не учитывать свободного места, которое может двигаться вдоль цепи). Для этого достаточно представить себе, что в коробке поставлены внутренние стенки, например, так, как это сделано на рис. 36. Фишки могут. двигаться вдоль «стенок» почасовой стрелке или против нее. Каждая фишка, которая входит в цепь, после определенного числа шагов может стать на место с номером 3. Пусть размещение характеризуется циклом (1, 2, й), т. е. в коробке фишка с номером 2 стоит на первом месте, фишка с номером Й вЂ” на втором месте, фишка с номером 1 — на й-м месте (3 =й(15), а все остальные — на своих местах.
Делая определенное, число перемещений звеньев цепи, мы можем фишку с номером 1 поставить на 3-е место. После этого, перемещая фиктивную фишку вдоль цепи в противоположном направлении, освободим место с номером 7. Теперь можно, переставляя лишь фишки, что стоят на местах с номерами 1, 2, 3, 5, б, 7, достичь того, чтобы фишки с номером 1 и 2 стали на свои места, с номером й — на третье место, а остальные нв изменили позиций. Зто видно из схемы последовательного . ыв перемещения фишек, приведенной на рис. 37. На этой схеме ° и х обозначают фишки, номера которых для нас несущественны. В результате таких перемещений изменился порядок размещения лишь трех 'фишек.
Фишку с номером й можно теперь включить в цепь. Перемещая по цепи, поставим ее на место с номером й. При этом все остальные фишки из цепи займут начальное положение. Осталось лишь поставить фиктивную фишку на последнее место, и мы получим стандартное размещение. г Л хг~ ху7. Ггя х о Ряс. 37 Докажем теперь, что каждая четная перестановка расклидываппся в произведение циклов из ряда (1). Действительно, каждая четная перестановка а раскладывается в произведение четного числа транспозиций: с»=6» 6» ...'6»»-»'6»» (2) Если а=(1, 2), то в силу равенства а'=е можно написать а = 6» а а б, 6» а а 6, ...
б », а а б » = = (6» а) ° (а ° 6») (6» ° а) ° (о- 6») " ° " (6»»-» а) ° (а ° 6»») Для завершения доказательства достаточно показать, что для любой транспозиции (1, 1) оба произведения (1, 1) (1, 2) и (1, 2) ° (1, 1) можно разложить в произведение циклов из ряда (1).
А этот факт действительно имеет место, как показывают следующие легко проверяемые равенства: (1, 2) ° (1, у) =(1,!) ° (1, 2) = = (1, 2, )) ° (1, 2, 1) ° (1, 2, 1) ° (1, 2, 1), если 1, /) 2, (1, 2) (1 1) = (2 !) (1 2) = (1 2. 1) если /)2, (1, 2) ° (2, 1) =(1, 1) ° (1„2) =(1, 2, 1) ° (1, 2, )), если !') 2. Если одно из 6» в разложении (2) равно (1, 2), то соответствующее произведение на а будет тождественной перестановкой и его можно не учитывать, 1!9 Упражнении 1. Как практически осуществлять переход к стандартной позиции от размещений, которые характеризуются четной перестановкой) 2. Доказать, что каждая четная перестановка на множестве л4=(1, 2, ..., и) раскладывается в произведение таких циклов длины 3: (1, 2, 3), (2, 3, 4), ..., (и — 2, и — 1, и).
3. Разложить в произведение циклов вида (1, 2, А) перестановки ф=(1, 2, 3) ° (7, 5) ° (4, 6, 9, 8), ф=(1, 2, 3, 4) (8, 7, 5, 6). 4. Можно лн перейти к стандартному размещению от начальных позиций, заданных перестановками 1 2 3 4 5 6 7 8 9 1О 1! 12 13 14 15) ( 8 7 6 5 1 2 4 3 13 15 11 10 14 12 9/' 1 2 3 4 5 6 7 8 9 10 11 12 13 !4 151 6 3 4 5 2 1 15 10 13 !2 11 14 9 8 7) 5. Если позиция характеризуется нечетной перестановкой, то от н можно перейти к размещению, которое. отличается от стандартного порядком двух последних фишек. Доказать зто. 6.
На фишках длв игры эв пятнадцатьэ вместо чисел написаны буквы и. г, р, а, в, п, я, т, н, а, д, ц, а, т, ь. Перемещая фишки, как в игре в чпятиадцатьэ, от каждого 'размещения можно перейти к такому, когда буквы на фишках образуют фразу энгра в пятнадцатьм Доказать зто. 7. Игра чхамелеонэ проводится на едоскеэ с девятью клетками, като. г я з рые соединены прямолинейными отрезками (рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
