Математика кубика рубика и перестановочных головоломок
Где здесь группа
Возможно, заглянув в педивикию, многие видели, что к статьям типа [[теория групп]] в качестве картинки довольно часто приведена картинка кубика рубика. Для начала я попытаюсь объяснить, где у кубика рубика та самая группа, о которой идет речь в тех статьях
Для начала, попробую ввести термин преобразование кубика рубика
Точное определение преобразования, наверное было бы слишком сложным и абстрактным и начинающимся со слов "Класс эквивалентности формул..." потому попробую объяснить описательно. Преобразование это что-то среднее между формулой и позицией. Но не формула и не позиция.
От формулы преобразование отличается тем, что если разные формулы делают одно и то же, то это одно и то же преобразование. Ну, например, поворот одной грани и 3 поворота той же грани в другую сторону в принципе могут записываться разными формулами, но делают одно и то же, так что это то же самое преобразование. То есть в термине преобразование нас не интересует, как именно, какими поворотами это было сделано.
В общем, каждой позиции кубика можно поставить в соответсвие единственное преобразование, которое делает эту позицию из собранного состояния. Потому в этом понятии есть сходство с понятием позиция, но есть и отличия. Например, ниже будем рассматривать композицию преобразований то есть то, что будет, если два преобразования сделать последовательно. С позициями неясно, как вводить такое понятие.
В общем, в понятиях позиция и преобразование есть немало общего с понятиями точка и вектор в геометрии. В геометрии к точке можно приложить вектор и получим новую точку, а тут к позиции можно применить преобразование и получим новую позицию. В геометрии две точки задают вектор, здесь две позиции задают преобразование, которое переводит одну позицию во вторую.
Да, пустое преобразование, которое ничего не делает -- такое же полноценное преобразование, как и другие.
Если у нас есть два преобразования a и b, то мы можем выполнить их последовательно. То что получится, тоже, разумеется, будет будет преобразованием. Запишем его как a*b. Символ "*", впрочем не нужен, не принято его писать у неабелевых групп, так что запишем даже просто ab, типа произведение преобразований.
Понятно, что у кубика рубика в общем случае ab≠ba. То есть обычно (хотя и не всегда) важно, в каком порядке применять преобразования (да хотя бы даже просто обычные повороты), хотя перестановочные элементы (такие преобразования a и b, для которых ab=ba) тоже есть.
Зато у этой операции есть другое простое свойство: для любых трех элементов a b c справедливо (ab)c=a(bc) То есть если мы выберем для произведения три преобразования, то неважно как мы будем их перемножать, или сначала первое на второе, а потом произведение на третье, или первое умножим на зарнее выполненное произведение второго и третьего.
Выше я упомянул пустое преобразование. Обозначим его e или 1. У него есть очевидное свойство: для любого преобразования a справедливо, что ae=ea=a
Пусть у нас есть преобразование a. Если мы возьмем какую-нибудь формулу, которой оно получилось, и выполним ее действия в обратном порядке, получим преобразование b. Для этих двух преобразований выполняется ab=e И, кроме того, эти два преобразования, очевидно коммутируют, то есть выполняется еще и ba=e. Будем называть такое b обратным элементом к a или a-1 То есть для любого элемента a существует элемент a-1 такой, что aa-1=a-1a=e
Вот, в общем-то мы и описали то, что является группой. Ибо группа это
множество элементов с определенной на них бинарной операцией, для которой выполняются
следующие условия:
1 Для любых двух элементов a и b существует элемент a*b (или ab) в той же группе
2 У операции есть вышеупомянутое свойство ассоциативности, то есть (ab)c=a(bc)
3 В ней существует элемент e такой что для любого элемента a из группы ae=ea=a
4 Для каждого элемента a существует элемент a-1 такой, что
aa-1=a-1a=e
Бывают такое группы, что в них для любых двух элементов a и b справедливо ab=ba Такие группы называют абелевыми или коммутативными. Операцию у них уже принято обозначать знаком +, а нейтральный элемент (тот, что в неабелевых обозначают 1 или e) у абелевых обычно обозначают 0. Но группа преобразований кубика рубика не из таких, и абелевых групп я касаться не буду.
Так вот: группа преобразований кубика рубика является типичным примером конечной неабелевой группы. Количество элементов в этой группе хоть и очень велико, но все-таки конечно. Можно сказать, что это подгруппа более сложной группы S48, но, хоть от нее отрезано и немало, эта группа осталась довольно запутанной, и вообще, абсолютно любая конечная группа является подгруппой группы Sсколько-нибудь, а у нашей хотя бы неабелевость не пропала.
То, что буден ниже, частично описано в педивикии в статьях [[симметрическая группа]] и [[перестановка]], но в других терминах. Доводилось слышать, что там термины более корректные, но у нас на лекциях говорилось так, поэтому и тут буду писать давно знакомыми терминами. Кроме того, кажется в Куроше используются именно эти термины.
Почему в игре 15 нельзя переставить 14 и 15?
Следующая, наверное самая важная тема боюсь будет слишком абстрактной. Чтобы она легче воспринималась, перед ней попробую привести доказательство того, что в игре 15 невозможно переставить элементы 14 и 15. Для этого потребуется теорема, которую тут же и докажу, и на игре 15 она должна восприниматься проще, чем если бы я ее попробовал доказать без такого вступления. В педивикии приведено какое-то доказательство этого факта, но мне, для дальнейшей теории, надо показать именно это, мое доказательство, кторое я сам нашел на 1м курсе, когда прошли соотсвтесвующую теорию...
Для начала, заткнем пустое, вакантное поле фишкой 16. Будем считать, что у нас нет пустого поля, а просто фишку 16 мы можем поменять местами с одним из соседних с ней. Вот пример позиции:
3 2 1 4 5 16 8 9 7 11 6 10 13 14 15 12
Кстати, позиция как раз невозможная... Попытаемся выделить в ней циклы, а именно будем делать следующее: Возьмем какое-нибудь место, где стоит не свой элемент. Пусть будет место элемента 6, где стоит фишка 16. Смотрим, что там стоит - 16. Перейдем к месту 16 и посмотрим, что стоит там - 12, дальше прееходим к месту 12 итд. Так, как число мест конечно, то рано или поздно мы начнем повторяться. Причем первое повторенное место будет то, с кторого начали - 6. Выпишем в скобках последовательно все, что мы таким образом прошли. Получится (6,16,12,10,11) Назовем это циклом. Потом выделим все остальные циклы. Получим, что наша позиция состоит из циклов (3,1)(6,16,12,10,11)(7,8,9). В принципе, к этим циклам можно добавить еще циклы длины 1, состоящие из стоящих на своих местах элементов типа (3,1)(6,16,12,10,11)(7,8,9)(2)(4)(5)(13)(14)(15), но это ничего не меняет.
Очевидно, что каждой позиции соответсвует единственное разложение на такие циклы, разве что сами циклы можно записать иначе, типа вместо (7,8,9) можно написать (8,9,7), ну или можно местами поменять циклы в записи, неважно.
Длиной цикла назовем число элементов, кторые к нему относятся, так наша позиция состоит из одного цикла длины 2, одного длины 5, одного длины 3 (и шести длины 1).
Декрементом позиции назовем следующую фигню: суммарную длину всех циклов минус их количество. То есть у нашей позиции декремент равен 2+5+3-3=7. Ну, или, если учитывать циклы длины 1, то он равен 2+5+3+1+1+1+1+1+1-9=7 Поэтому я и писал, что учет циклов длины 1 ничего не меняет.
Так вот: оказывается, что декремент (а также его четность) - весьма важная характеристика позиции. Декремент это что-то вроде числа бога позиции: Если разрешим менять местами любые 2 элемента, то минимально возможное число ходов, за которые позиция решается будет равно декременту. Про его четность есть вообще замечательная теорема:
Перестановка местами любых двух элементов в позиции меняет четность декремента
Заметим, что наш ход - это перстановка местами элемента 16 с одним из его соседних. Теорема же говорит о том, что нсли мы вообще выберем любые 2 и поменяем их местами, то четность декремента изменится: если раньше он был четным, то станет нечетным и наоборот
Ну, для доказательства теоремы надо рассмотреть 4 случая (или 3 случая, из которых один распадется на два):
1. Когда преставляются два элемента, не входящие ни в один из циклов
2. Когда один из элементов не входит ни в один из циклов, а другой входит
3. Когда оба элемента входят в циклы
3.1. При том оба входят в один цикл
3.2. При том они входят в разные циклы
1. Самый простой случай. Если мы переставляем два элемента, не входящие ни в какие циклы, то представление позициив виде циклов изменится очевидным образом: в ней добавится цикл длины 2. Суммарное число всех двигаемых элементов увеличится на 2, а число циклов увеличится на 1. Декремент увеличится на 1, его четншость сменится.
Пример: Исходная позиция. Выделены элементы, которые будем переставлять:
3 2 1 4 5 16 8 9 7 11 6 10 13 14 15 12
Как уже писалось выше, ее разложение на циклы такое: (3,1)(6,16,12,10,11)(7,8,9) и декремент=7. Теперь все-таки переставим выделенное:
3 14 1 4 5 16 8 9 7 11 6 10 13 2 15 12
Новое разложение на циклы: (3,1)(14,2)(6,16,12,10,11)(7,8,9) И лекремент теперь =2+2+5+3-4=8 четный, сменился
2 Один из элементов не входил ни в один цикл, другой входил
Ну, в этом случае все циклы, кроме одного не меняются. Путь тот цикл, в который входил один из переставляемых элментов будет (a1,a2,a3....an) Пусть те элементы, который мы переставляем - это a2 и b (не входящий в циклы). Если элемент aне 2, то просто перезапишем этот цикл так, чтобы он был впереди вторым и стал a2.
Ну, просто смотрим, что стало с циклом после перестановки a2 и b : a1 - на его месты был a2, но мы его переставили с b поэтому следующим в записи будет b. На месте b раньше стоял сам b, но после перестановки встал a2, так что следующим элементом цикла станет a2 Все же дельнейшие элементы цикла, можно заметить, так и остались на своих местах.
Вывод - в этом случае просто один цикл увеличивается на 1, суммарная длина циклов увеличивается на 1, количество циклов не меняется, следовательно декемент увеличивается на 1, а следовательно и в этом случае четность декремента меняется.
Пример: Опять исходная позиция c декрементом 7. Опять выделены элементы, которые будем переставлять:
3 2 1 4 5 16 8 9 7 11 6 10 13 14 15 12
переставляем...
3 1 2 4 5 16 8 9 7 11 6 10 13 14 15 12
Раскладываем на циклы: Получается (1,3,2)(6,16,12,10,11)(7,8,9) Декремент=3+5+3-3=8 четность сменилась.
3.1. Оба переставляемых элемента входят в один цикл.
Пусть этот цикл (a1,a2,a3,...ak....an) Выделил переставляемые элементы этого цикла с теми же соображениями, что если первый имеет номер в цикле не 2, то всегда можно просто переписать этот цикл так, чтоыб номер у него был 2
Смотрим, что делается с этим циклом после перестановки a2 и ak: На месте a1 стоял a2, а после преестановки стоит теперь ak. На месте ak стоял ak+1, и сейчас там же стоит... Смотрим что получилось и получилось этот цикл сократился до (a1,ak,ak+1,...an). Но это еще не все... На месте ak-1 стоял ak, а теперь стоит a2. На месте a2 стоял a3, и по прежнему так и стоит. Получаем, что появился еще один цикл: (ak-1,a2,a3,...ak-2)
Итого в результате 3.1 просто один цикл разбился на 2. Число двигаемых элементов не изменилось, число циклов увеличилось на 1, а следовательно декремент уменьшился на 1, а следовательно его четность сменилась и в этом случае
Пример: Опять исходная позиция c декрементом 7. Опять выделены элементы, которые будем переставлять:
3 2 1 4 5 16 8 9 7 11 6 10 13 14 15 12
переставляем...
3 2 1 4 5 16 8 9 7 11 12 10 13 14 15 6
Новое разложение на циклы: (3,1)(6,16)(7,8,9)(10,11,12) декремент=2+2+3+3-4=6
3.2. Оба переставляемых элемента входят в разные циклы.
Пусть эти циклы (a1,a2,a3....an) и (b1,b2,b3....bk) Переставляемые элементы a2 и b2 выделил. Смотрим, что с ними проиходит. На месте a1 стояло a2, а после перестановки стоит b2. На месте b2 стоило b3 и до сих пор стоит... Доходим до bk, за которым по прежнему стоит b1. А вот на месте b1 раньше стояло b2, а пеосле их перестановки стоит уже a2. На месте a2 стояло a3 и это не изменилось. В итоге получатеся, что вместо этих двух циклов после перестановки получается один цикл (a1,b2,b3,b4,...bk,b1,a2,a3,...an)
Получается, что в этом случае число элементов не изменилось, а число циклов уменьшилось на 1. Следовательно, декремент увеличился на 1.
Пример: Опять исходная позиция c декрементом 7. Опять выделены элементы, которые будем переставлять:
3 2 1 4 5 16 8 9 7 11 6 10 13 14 15 12
переставляем...
3 2 1 4 5 8 16 9 7 11 6 10 13 14 15 12
Новое разложение на циклы: (3,1)(6,8,9,7,16,12,10,11) Декремент=2+8-2=8
В приведенном выше упрощенном доказательстве есть ряд несущественных помарок, касающихся случаев, когда в процессе возникают циклы длины 1, но они малосущественны и общем-то самая важная теорема всей этой статьи доказана.
Ну вот, важную теорему доказали, а теперь посмотрим наначальную и на конечную позиции. Ну, на начальную смотреть особо не на что. Циклов нет, декремент равен 0, то есть он четный. А вот та позиция, невозможность которой хотим доказать:
1 2 3 4 5 6 7 8 9 10 11 12 13 15 14 16
Ее разложения на циклы самое простое: (14,15). Декремент равен 1, то есть он нечетный.
Каждый ход у нас - это перестановка элемента 16 и одного из соседних с ним. А следовательно с каждым ходом обязательно меняется четность декремента. Через нечетное число ходов декремент будет нечетный, а через четное - четный. Наша конечная позиция с нечетным декрементом, а следовательно к ней можно прийти только за нечетное число ходов...
Но можно ли прийти за нечетное? Раскрасим дно головоломки в белый и черный цвет в шахматном порядке:
Б Ч Б Ч Ч Б Ч Б Б Ч Б Ч Ч Б Ч Б
С каждым ходом будет меняться цвет дна у пустой клетки. А следовательно за четное число ходов цвет дна не может измениться, а за нечетное изменится обязательно.
И в начальной и в конечной позиции пустая фишка стоит на том же месте, а значит цвет дна не изменился, а значит за нечетное число ходов ее достичь невозможно.
Злые языки говорят, что описанное выше условие не только необходимо, но и достаточно, чтобы головоломка собиралась, но я это не проверял:-)
Группа подстановок
Понятно, что преобразования, образующие группу есть и у упомянутой в прошлой главе
игры 15. Если задуматься, что это за преобразования, то один из возможных ответов будет такой:
Это функция, которая по номеру места указывает номер фишки, которая на этом месте стоит.
При этом все такие функции удовлеторя.т следующим свойствам:
Они определены для любого числа от 1 до 16
Для разных, неравных чисел i и j каждая из таких функций будет принимать разные, неравные
значения.
Для каждой функции и для любого значения есть аргумент такой что значение функции от этого
аргумента равно заданному значению.
Итак: пусть у нас теперь есть некоторое конечное множество, то есть множество
из n элементов {1,2,3,...n} Что из себя представляют эти элементы - нам неинтересно
от слова совсем, поэтому для удобства будем считать, что это просто числа от 1 до n.
Рассмотрим теперь функции f, определенные на этом множестве
с вышеупомянутыми свойствами:
Для любого a от 1 до n определено значение функции f(a) и оно тоже от 1 до n
Для любых a и b если a≠b то обязательно f(a)≠f(b)
Для любого b существует a такое что f(a)=b
На самом деле, одно из вышеприведенных условий избыточно для конечных множеств, то есть прямо следует из других, но пусть будет так.
Если мы возьмем множество всех таких функций, то на нем мы можем определить операцию композиции функций (f*g)(x)=g(f(x))
Можно заметить, что такое множество с такой операцией таки образует группу, которую называют группой подстановок и записывают Sn, где n - число элементов исходного множества. (само же число элементов группы=n!=2*3*4*...*n) Элементы же этого множества, то есть эти функции, называются подстановками.
Так вот: практически все, что я описывал выше про позиции игры 15 справедливо про подстановки. А именно:
Любая подстановка естественным образом разбивается на произведение независимых циклов.
Декремент подстановки - это количество всех двигаемых ею элементов минус количество тех самых независимых циклов
Подстановка с четным декрементом называется четной, а с нечетным декрементом -- нечетной.
Подстановка, которая не двигает никакие элементы кроме двух, которые меняет местами (цикл длины 2) назвается транспозицией.
Умножение на транспозицию меняет четность подстановки.
На самом деле вышеприведеное утверждение, доказанное в предыдущей главе, -- всего лишь частный случай более общего.
Существует довольно простая теорема о том, что любая подстановка может быть представлена в виде произведения транспозиций. Доказывается тем, что любой цикл (a1,a2,a3,...an) есть по сути следующее произведение транспозиций: (a1,a2)*(a1,a3)*...*(a1,an)
Вспомнив теорему, получим, что четная подстановка может быть представлена только как произведение четного числа транспозиций, а нечетная - только как произведение нечетного их числа.
Вот и стала понятна формулировка более общей теоремы: Умножение на четную подстановку никогда не меняет четность подстановки. Умножение на нечетную подстановку обязательно меняет четность подстановки
Доказательство, опираясь на вышеизложенное, элементарно. Умножение на четную подстановку это четное число раз умножение на транспозицию, то есть четное число раз изменение четности. Умножение же на нечетную подстановку это умножение нечетнео число раз на транспозицию, то есть нечетное число раз изменение четности.
Дочитавшим досюда бонус в виде той же самой темы, но в другом месте. И вот еще
Применение этого всего
Ну, в общем-то очевидно, что вот эта вся теория очень хорошо применятеся к головоломкам типа кубика рубика. А именно: занумеруем все стикеры кубика номерами от 1 до 48. Теперь преобразования, которых я писал выше - это как раз одстановки из S48. Как я писал выше, позиции можно сопоставить преобразование, которое переводит собранный кубик в эту позицию. Осталось только понять, что есть повороты, которыми мы собираем.
Собственно довольно очевидно и то, что из себя представляют эти повороты. Видно, что при повороте боковой грани (а поворот центральной тут рассматривать неинтересно, можно просто сказать, что это два поворота боковых) перемещаются 20 стикеров. Причем перемещаются они пятью циклами длины 4. В педивикии в статье [[группа кубика рубика]] эти циклы даже расписаны в уже объясненных выше обозначениях.
Кроме такого лобового подхода, описывающего сразу все, возможны и другие подходы:
Возможно рассматривать его как подстановку не на стикерах, а на кубиках (реберных и угловых). Это будет подгруппа, очевидно, группы S20 Тогда поворот грани - это два цикла длины 4, что является четной подстановкой, а следовательно вот доказательство, что в нем невозможно просто поменять местами два угловых - от этого обязательно поменяются и, например, два реберных.
Возможно забыть об угловых и рассматривать его как подстановку на только реберных кубиках или толко реберных стикерах. В первом случае будет подстановки из S12 и порождаться они будут циклами длины 4 - нечетными подстановками и с каждым ходом будет меняться четность. Во втором случае это будут подстановки из S24 и порождаться они будут парой циклов длины 4 - только четными подстановками, а следовательно на реберных стикерах нечетная подстановка невозможна (например, невозможно перевернуть только 1 реберный элемент)
В общем, изо всех невозможных позиций, из этой теории вроде не следует только невозможность повернуть один угловой кубик. Я позже придумал несложное доказательсто этого, но никак не затрагивающее этой теории.
Мегаминкс везде порождается циклами длины 5. Как его не крути, нечетные подстановки на нем в принципе невозможны, ни при какой интерпертации.
Коммутатор это такая псевдооперация в группе. (Сам термин, думаю, возник веке в 19м, а не через 20 лет после того как некторые придумали их применение к кубику рубика) Для двух элементов a и b их коммутатор (записывается как [a,b]) это [a,b]=aba-1b-1 Важно, что если a - некоторое преобразование, делающее на некотором слое аккуратное нужное действие, а b - поворот этого слоя, то их коммутатор [a,b] - как правило нужная формула. Подробнее об этом. Многие формулы представляют собой коммутаторы некоторых двух преобразований. Заметим, что раз aa-1=e , а e - четная подстановка, то четности a и a-1 всегда одинаковы (на самом деле у них и декремент будет одинаков), а следовательно aba-1b-1 для любых a и b - подстановка всегда четная. А следовательно коммутаторы в принципе неспособны сделать никакое нечетное преобразование.
Переставить два угловых элемента коммутаторы, как я выше сказал, не в силах, но если сделать поворот боковой грани, то угловые элементы умножатся на цикл длины 4, то есть на нечетную подстановку, и подстановка на угловых станет четной. А тут уже коммутаторы попробовать можно.
Аналогичная проблема у меня возникает на кубике рубика размера 4. В моем алгоритме сборки там вскоре после сборки первого слоя нет ничего, кроме коммутаторов. Но иногда, на реберных нецентральных элементах возникает нечетная подстановка. Смотрим и выясняем, что поворот боковой грани там на этих элементах - два цикла длины 4 - подстановка четная, а вот поворот небоковой грани внезапно просто цикл длины 4 - подстановка нечетная. Делаем поворот предпоследнего слоя, сдвигаем обратно его элементы коммутаторами (заранее специально не собираем на предпоследнем слое ничего, кроме реберных, его центральные оставляем напоследок) и четность подстановки действительно меняется.