Системный анализ групп преобразований состояний кубика Рубика
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ
Национальный аэрокосмический университет им. Н.Е. Жуковского
«Харьковский авиационный институт»
КУРСОВАЯ РАБОТА
по дисциплине: «Основы системного анализа»
на тему: СИСТЕМНЫЙ АНАЛИЗ ГРУПП ПРЕОБРАЗОВАНИЙ СОСТОЯНИЙ КУБИКА РУБИКА
г. Харьков - 2014 год
Оглавление
Введение
. Системный анализ групп преобразования состояний кубика Рубика
.1 Актуальность работы
.2 Дерево проблем
.3 Дерево целей
. Описание системы трехмерного визуализатора процесса дефрагментации (кубика рубика) с точки зрения системного анализа
.1 Структурное описание системы
.2 Функциональное описание системы
.3 Информационное описание системы
.4 Классификационное описание системы
. Модельное представление объекта исследования
.1 Основные уравнения, описывающие объект исследования
.2 Входные и выходные величины
.3 Исследование преобразований состояний кубика Рубика с помощью математической теории групп
.4 Анализ некоторых алгоритмов решения головоломки
.4.1 Алгоритм Тистлетуэйта
.4.2 Алгоритм Коцембы
.4.3 Метод CFOP (метод Джессики Фридрих)
.4.4 Основные факторы, влияющие на оптимизацию групп преобразований состояний кубика Рубика
Заключение
Список литературы
Приложение
Введение
Кубик Рубика - одна из популярнейших в мире головоломок. Её создал в 1975 году Эрнё Рубик (Erne Rubik, Rubik Ernő) - венгерский изобретатель, скульптор и профессор архитектуры.
В 1971 году Эрнё был назначен преподавателем Академии прикладных искусств. Среди прочих дисциплин он преподавал трехмерное моделирование. По одной из версий, при помощи данного учебного пособия Рубик пытался объяснить студентам основы математической теории групп. Задача изобретателя была такова: заставить отдельные разноцветные кубики свободно вращаться на своих местах, не нарушая конструктивного единства всего приспособления.
Самому изобретателю потребовался месяц, чтобы собрать кубик, после создания первой модели.
января 1975 г. Эрнё Рубик подал заявку на патент.
В течение последующих 40 лет ведущие математики и программисты пытались найти кратчайший алгоритм сборка кубика Рубика. На данный момент кратчайший алгоритм не найден.
В первой главе данной работы приведен обзор литературы, сделаны выводы по результатам обзора информационных источников. Также представлены дерево проблем и дерево целей, определена цель исследования. Определен объект исследования, приведено доказательство того, что объект исследования является объектом с точки зрения системного анализа. Определен предмет исследования.
Во второй главе содержится анализ предмета исследования. Приведены структурный, функциональный, информационный и классификационный виды анализа исследуемого объекта.
В третьей главе обоснован выбор модельного представления объекта исследования. Приведены входные и выходные величины, а также основные уравнения, описывающие объект исследования.
В заключении представлены выводы, предложения и рекомендации, показана практическая значимость работы.
дефрагментация кубик рубик математический
1. Системный анализ групп преобразования состояний кубика Рубика
.1 Актуальность работы
Кубик Рубика - это пластмассовый куб, разбитый на 27 конгруэнтных кубиков. Внутренний кубик удален, а 26 наружных кубиков соединены так, что любая грань из 9 кубиков, прилегающих к одной грани куба, может быть повернута в любом направлении на 900. После поворота на 900 вся система сохраняет прежнюю свободу вращений: снова любую грань в любом направлении можно повернуть в ее плоскости на 900.
Первоначально каждая из граней большого куба окрашена в свой цвет (красный, оранжевый, желтый, зеленый, синий, белый). После ряда случайно выбранных вращений окраска граней куба становится пестрой: на грани присутствуют клетки разных цветов. Решение головоломки состоит в том, чтобы с помощью вращений добиться изначальной расстановки кубиков, т.е. такой расстановки, при которой каждая грань куба снова будет одного цвета.
«Джон Конвей, один из крупнейших специалистов по теории групп в мире, либо один из его коллег в Кембридже определил кратчайший путь из любого данного состояния назад к начальному состоянию как «Алгоритм Бога» [1].
Число комбинаций кубиков, которые можно получить вращением граней (подсчитано, что их N = 43 252 003 274 489 856 000, т.е. более 43 квинтиллионов) делает ее недоступной для перебора даже на ЭВМ. Можно заметить, что не любая комбинация может быть получена вращением граней куба: если разрешить разборку куба на составляющие его 26 кубиков, то можно составить 12N = 529024039393878272000 различных комбинаций.
1.2 Дерево проблем
Основную проблему данной работы, можно разбить на подпроблемы и представить в виде дерева проблем (см. рис. 1.1)
.Сложность последовательной обработки всех возможных различных состояний кубика Рубика
.1.Сложность построения графа состояний кубика Рубика
.1.1.Ограниченные возможности графических редакторов и средств для визуализации графа состояний кубика Рубика
.2.Ограниченность ресурсов вычислительной техники
.2.1.Ограниченностьвместимости цифровых носителей
Рисунок 1.1 - Дерево проблем
.3 Дерево целей
Основную цель данной работы, можно разбить на подцели и представить в виде дерева целей (см. рис. 1.2).
.Исследовать возможность создания алгоритмов и сформулировать рекомендации, позволяющие оптимизировать количество преобразований между начальным и целевым состояниями кубика Рубика
.1.Оптимизация на группе преобразований состояний кубика Рубика
.1.1.Применение методов теории групп
.2.Поиск алгоритма для нахождения оптимального решения
.2.1.Изучение и анализ алгоритмов преобразования состояний кубика Рубика
Рисунок 1.2 - Дерево целей
Цель работы - исследовать возможность создания алгоритмов и сформулировать рекомендации, позволяющие оптимизировать количество преобразований между начальным и целевым состояниями кубика Рубика.
Объект исследования - Состояния кубика Рубика.
Предмет исследования - Группы преобразований состояний кубика Рубика
Методы исследования:
·Обработка существующей информации;
·Анализ существующих алгоритмов.
Основные задачи исследования:
·Изучение алгоритмов преобразования состояний кубика Рубика;
·Определение основных факторов, влияющих на оптимизацию групп преобразований кубика Рубика.
2. Описание системы трехмерного визуализатора процесса дефрагментации (кубика рубика) с точки зрения системного анализа
.1 Структурное описание системы
Рассмотрим структуру системы кубика Рубика (Рисунок 2.1) и её свойства с позиций системного анализа.
Рисунок 2.1 - Структура кубика Рубика
Свойства системы:
)Эмерджентность
Центральный механизм - предназначен для соединения 26 конгруэнтных кубиков управления вращениями граней
Кубики - определяют положение цветовых индикаторов на каждой грани
Каждая из систем выполняет свою функцию, но их объединение способствует визуализации пошагового процесса дефрагментации без нарушения целостности всего устройства.
)Целостность
При удалении из системы всех центральных кубиков реберные и угловые кубики перестают управляться центральным механизмом, и система перестает существовать
)Аддитивность
Переход системы в нулевое состояние осуществляется последовательными поворотами граней куба.
)Синергизм
Вращение одной грани вызывает одновременное изменение положения и ориентации в пространстве девяти кубиков, принадлежащих вращающейся грани.
)Прогрессирующая систематизация
Процесс сборки кубика Рубика - это стремление к целостному цветовому покрытию каждой грани
)Изоморфизм
Все центральные, реберные и угловые кубики сходны между собой по строению (внутри группы).
Тип элементного состава - смешанный тип. Однотипными элементами являются кубики и в то же время они отличаются от центрального механизма.
Тип элементов - вещественный.
Тип связей между элементами - информационный.
Тип структуры - иерархическая.
Условно кубик Рубика можно представить кибернетической моделью, где {x1, …, xn} - вектор входов объекта, а {y} - выход.
.2 Функциональное описание системы
Функциональное описание системы - это описание как основной функции, выполняемой системой, так и функций подсистем и элементов данной системы с указанием параметров системы, подсистем и элементов. Функциональное описание также содержит структурноеописание системы, описание системоразрушающих и системообразующих факторов.
Структурное описание системы:
.Кубик Рубика
.1.Центральный механизм
.1.1.Толстое плечо креста
.1.2.Тонкая ось креста
.1.2.1.Шайба
.1.2.2.Пружина
.1.2.3.Гайка
.2.Кубики
.2.1.Центральные
.2.1.1.Цветные накладки
.2.2.Реберные
.2.2.1.Цветные накладки
.2.3.Угловые
.2.3.1.Цветные накладки
Функции системы и ее подсистем представлены в таблице 2.1
Таблица 2.1 - Функциональное описание системы
КодЭлементФункцияФункции системы первого уровня1Кубик РубикаПреобразование групп состояний цветовой схемы кубика РубикаФункции подсистем второго уровня1.1Центральный механизмКрепление центральных кубиков Вращение граней кубика Рубика1.2КубикиВизуализация вращений гранейФункции подсистем третьего уровня1.1.1Толстое плечо крестаОбеспечение фиксации центральных кубиков1.1.2Тонкая ось крестаОбеспечение подвижного крепления центральных кубиков при помощи пружины, шайбы и гайки1.2.1Центральные кубикиОпределение цвета соответствующей грани Фиксация угловых и реберных кубиков1.2.2Реберные кубикиОпределение состояния кубика Рубика Ориентация цветовых накладок относительно «собранного» состояния1.2.3Угловые кубикиОпределение состояния кубика Рубика Ориентация цветовых накладок относительно «собранного» состоянияФункции подсистем четвертого уровняКодЭлементФункция1.1.3ШайбаОбеспечение защиты пластмассовой части центрального кубика от продавливания металлической пружиной1.1.4ПружинаОбеспечение упругого соединения вращаемой грани1.1.5ГайкаОбеспечение фиксации пружины1.2.1.1 1.2.2.1 1.2.3.1Цветные накладкиВизуализация состояний кубика Рубика
Параметры системы и ее подсистем представлены в таблице 2.2
Таблица 2.2 - Параметры подсистем и элементов
КодЭлементПараметрыПараметры системы первого уровня1Кубик РубикаКачество Количество слоевПараметры подсистем второго уровня1.1Центральный механизм1.2КубикиКачество материала Безопасность материала Пластичность материала Длина стороныПараметры подсистем третьего уровня1.1.1Толстое плечо крестаДлина Диаметр Симметричность относительно центра1.1.2Тонкая ось крестаДиаметр Длина1.2.1Центральные кубикиТолщина внешней части Внешний диаметр выступа Внутренний диаметр выступа1.2.2Реберные кубикиДлина до внутреннего выступа Длина внутреннего выступа Ширина внутреннего выступа Радиус скругления1.2.3Угловые кубикиДлина до внутреннего выступа Длина внутреннего выступа1.2.3Угловые кубикиШирина внутреннего выступа Радиус скругленияПараметры подсистем четвертого уровня1.1.3ШайбаВнутренний диаметр Внешний диаметр Толщина шайбы1.1.4ПружинаДиаметр проволоки Стержень Внутренний диаметр Внешний диаметр Расточка Шаг Длина в сжатом состоянии Допустимая длина Свободная длина Количество витков Коэффициент упругости Длина под нагрузкой1.1.5ГайкаМарка стали Класс точности Класс прочности Поле допуска резьбы1.2.1.1 1.2.2.1 1.2.3.1Цветные накладкиБезопасность материала Толщина основы Толщина клеевого слоя Ширина основы
Итоговое и суммарное количество функций
·Функции первого уровня - 1
·Функции второго уровня - 2
·Функции третьего уровня - 5
·Функции четвертого уровня - 4
Общие характеристики системы представлены в таблице 2.3
Таблица 2.3 - Общие характеристики системы
ФункциональностьРангФакторыСистеморазрушающиеСистемообразующиеМногофункциональнаяПассивное существованиеНарушение правил эксплуатацииСоблюдение правил эксплуатации
.3 Информационное описание системы
Информационное описание должно давать представление об организации и управлении системой. Это наиболее полное описание, так как описывает систему уже в процессе ее функционирования. Информационное описание определяет зависимость морфологических и функциональных свойств системы от качества и количества внутренней (о самом себе и о среде) и внешней (поступающей из внешней среды) информации.
Принцип работы объекта исследования
На рисунках 2.2, 2.4 и 2.5 изображены внутренний крест, реберный кубик и угловой кубик соответственно. На рисунке 2.3 изображено крепление центрального кубика на внутреннем кресте
Рисунок 2.6 изображает внутреннюю сторону грани, снятой с креста.
Рисунок 2.7 изображает кубик Рубика, с которого снята одна грань и один реберный кубик.
Для большей наглядности на рисунках 2.6 и 2.7 центральные кубики, реберные кубики, угловые кубики и внутренний крест окрашены в разные цвета. Эта окраска не имеет отношения к цветным накладкам на внешних гранях кубиков.
На рисунках 2.6 и 2.7 видно как выступы на реберных и угловых кубиках складываются в почти цилиндрический выступ с внутренней стороны грани большого куба, а на среднем слое образуется цилиндрическое кольцеобразное углубление. Поворот грани отвечает повороту цилиндрического выступа в цилиндрическом углублении.
Роль пружины 4 (Рисунок 2.2) - в том, чтобы иметь возможность слегка оттягивать при поворотах вращающуюся грань.[2]
Рисунок 2.2
Перечень элементов системы:
)толстое плечо креста - 1;
)тонкая ось креста - 6;
)пружина - 6;
)гайка - 6;
)центральные кубики - 6;
)реберные кубики - 12;
)угловые кубики - 8;
)цветные накладки -54 (9шт х 6цветов).
Свойства деталей элементов представлены в таблице 2.4
Таблица 2.4 - Свойства деталей элементов системы
№Наименование элементаОбозначениеКоличество свойствПримечание1Толстое плечо крестаа111(1) - является несущим элементом системы2Тонкая ось крестаа221(2) - связывает механизм крепления центральных кубиков с толстым плечом креста 2(2) - является осью вращения граней3Шайба а311(3) - обеспечивает защиту пластмассовой части центрального кубика от продавливания металлической пружиной4Пружинаа421(4) - развивает усилие в растянутом состоянии 2(4) - развивает усилие в сжатом состоянии 3(4) - обеспечивает подвижность грани5Гайкаа511(5) - фиксирует положение пружины6Центральные кубикиа611(6) - обеспечивают крепление реберных и угловых кубиковПродолжение таблицы 2.4№ п/пНаименование элементаОбозначениеКоличество свойствПримечание7Реберные кубикиа711(7) - вращаются вокруг центральных кубиков8Угловые кубикиа811(8) - вращаются вокруг центрального кубика9Цветные накладкиа911(9) - обеспечивают цветовую идентификацию всех видов кубиков
Среднегеометрическое число свойств на один элемент:
а = = = 1,167
Структура объекта представлена на рисунке 2.3
Рисунок 2.3 - Граф системы
Связи системы между элементами системы:
1)Соединительные
. Угловые кубики - центральный кубик
. Реберные кубики - центральный кубик
. Центральный кубик - шайба
. Угловой кубик - цветные накладки
. Реберный кубик - цветные накладки
. Центральный кубик - цветная накладка
. Пружина - гайка
. Гайка - тонкая ось креста
. Тонкая ось креста - толстое плечо креста
)Преобразующие
. Внешняя среда (пользователь) - угловые кубики
. Внешняя среда (пользователь) - реберные кубики
. Шайба - пружина
Количество связей на один элемент системы представлено в таблице 2.5
Таблица 2.5 - Количество связей на один элемент
№Наименование элементаКоличество связей1Толстое плечо креста12Тонкая ось креста23Шайба24Пружина25Гайка26Центральные кубики37Реберные кубики38Угловые кубики39Цветные накладки1
Среднегеометрическое число связей на один элемент:
а = = = 1,963
Определяем число квантов пространства, занимаемых элементами (Таблица 2.6).
Квант пространства элемента vi- объем прямоугольного параллелепипеда, ограничивающего заданный элемент.
Объем пространства существования элементов V - это объем куба с ребром, равным сумме максимальных габаритов размеров элементов.
Число квантов: =
Таблица 2.6 - Число квантов пространства, занимаемых элементами
№Наименование элементаГабаритные размерыКвант пространства элементаМаксимальный размерЧисло квантов1Толстое плечо креста19х19х196859190,004 х1052Тонкая ось креста15х3х3135150,19 х1053Шайба 6х6х0,51861,429х1054Пружина10х5х5250100,103х1055Гайка3х5х57550,343 х1056Центральные кубики19х19х196859190,004 х1057Реберные кубики24х24х2011520240,002 х105 8Угловые кубики24х24х2413824240,002 х1059Цветные накладки15х15х1225150,114 х105
V = =
Среднегеометрическое число квантов пространства:
а==
=
=3,426*
2.4 Классификационное описание системы
Классификация - это разделение совокупности объектов на
классы по наиболее существенным признакам.
Результаты классификации системы представлены в таблице 2.7.
Таблица 2.7 - классификация системы по классификационным признакам
№Признак классификацииТип системы по признакуОпределение1По связи системы с окружающей средойОткрытаяВзаимодействует с окружающей средой2По происхождениюИскусственнаяСистема создана человеком3По объективности существованияРеальнаяСистема состоит из искусственных объектов4По типу описания законов функционированияСистема типа «белый ящик»Для данной системы законы функционирования известны полностью5По способу управления системойСистема с комбинированным управлениемБлок управления в системе - это центральный механизм, но вращает грани человек6По действиюТехническаяДанная система - совокупность взаимосвязанных физических элементов7По централизацииЦентрализованнаяВ данной системе есть центральный механизм управления8По однородности структурыРазнороднаяВ данной системе элементы не взаимозаменяемы9По типу сложностиИнформационно-логическаяДанная система является головоломкой10По мерностиМногомернаяВ данной системе много входов и один выход11По организованностиХорошо организованнаяДля данной системы определены все ее элементы, связи и цели12По линейностиНелинейнаяНе описывается линейным уравнением13По непрерывностиДискретнаяВсе элементы данной системы дискретны14По обусловленности действияДетерминированнаяВходы однозначно определяют выход
3. Модельное представление объекта исследования
.1 Основные уравнения, описывающие объект исследования
Для обозначения последовательности поворотов граней кубика Рубика 3×3×3 используется «нотация Сингмастера» [3], разработанная Дэвидом Сингмастером и опубликованная им в 1981 г.
Буквы L, R, F, B, U, D обозначают поворот на 90° по часовой стрелке левой (left), правой (right), передней (front), задней (back), верхней (up) и нижней (down) граней соответственно. Повороты на 180° обозначаются добавлением справа к букве цифры 2 или добавлением в верхнем индексе цифры 2 справа от буквы. Поворот на 90° против часовой стрелки обозначается добавлением штриха ( ′ ) или добавлением в верхнем индексе -1 справа от буквы. Так, например, записи L2 и L2; L′ и L-1 эквивалентны.
Существует два наиболее распространённых способа измерения длины решения (метрики). Первый способ - одним шагом (ходом) решения считается поворот грани на 90° (quarterturnmetric, QTM). По второму способу - за 1 ход также считается и полуоборот грани (faceturnmetric, FTM, иногда это обозначают HTM - half-turnmetric). Так, F2 (поворот передней грани на 180°) должен считаться за два хода в метрике QTM или за 1 ход в метрике FTM.
Для указания в тексте длины последовательности для используемой метрики используется нотация, состоящая из цифр числа ходов и строчной первой буквы обозначения метрики. Так, 14f обозначает «14 ходов в метрике FTM», а 10q - «10 ходов в метрике QTM». Чтобы указать, что количество ходов является минимальным в данной метрике, используется звёздочка: 10f* обозначает оптимальность решения в 10 ходов FTM.
3.2 Входные и выходные величины
Входными величинами являются всевозможные состояния кубика Рубика. Единственной выходной величиной является нулевое (собранное) состояние.
.3 Исследование преобразований состояний кубика Рубика с помощью математической теории групп
Состояния - различные варианты сборки кубика Рубика, возникающие при произвольной расстановке 8 угловых кубиков по вершинам куба и 12 реберных - по ребрам. Центральные кубики во всех состояниях расположены одинаково - так же, как в нулевом состоянии, когда каждая грань куба окрашена в один цвет. Если состояние S2 можно получить из состояния S1 с помощью некоторой операции, то и от S2 можно перейти к S1, изменив направление каждого из поворотов на противоположное и выполняя их в обратном порядке. В этом случае состояния S1 и S2 являются связанными.
Чтобы полностью описать состояние кубика Рубика, нужно для каждого маленького кубика указать место, которое он занимает, и его ориентацию на этом месте. Каждый угловой кубик можно поместить в одно и то же место тремя, а реберный - двумя способами.
Пусть кубик Рубика находится в нулевом состоянии. Перенумеруем его вершины и находящиеся в них угловые кубики числами от 1 до 8, а ребра и соответствующие реберные кубики - числами от 1 до 12. Кроме того на каждом ребре большого куба выберем определенное направление (вектор).
Теперь местонахождение i-го углового (j-го среднего) кубика в состоянии S можно задать номером σS(i) (τS(j)) той вершины (ребра), где он находится (i = 1..8, j = 1..12).
Чтобы задать ориентацию угловых кубиков, выделим пару противоположных граней большого куба, например его горизонтальные грани. Для определенности предположим, что верхний кубик - синий, а нижний - зеленый. Каждый угловой кубик имеет либо одну грань синего цвета, либо одну грань зеленого цвета. Угол α (α = 00, 1200 или 2400), на который следовало бы повернуть этот кубик в его положении вокруг диагонали большого куба против часовой стрелки, чтобы эта грань (синяя или зеленая) стала горизонтальной, будем называть углом поворота данного углового кубика в состоянии S и об означать αS(i), где i - номер кубика.
Ориентацию j-го реберного кубика в состоянии S зададим углом βS(i) между вектором ребра, на котором кубик должен находиться, и вектором ребра, на котором он находится (τS(j)-го ребра). Угол βS(i) может равняться 00 или 1800; будем называть его углом поворота j-го реберного кубика в состоянии S.
Проследим, как изменяются характеристики состояний αS, βS, τS и σS при поворотах граней. Легко проверить что:
)Углы поворотов угловых кубиков не изменяются при поворотах четырех вертикальных граней на 1800 и при произвольных поворотах горизонтальных граней.
)Углы поворотов реберных кубиков не изменяются при поворотах двух противоположных граней на 1800 и при произвольных поворотах остальных граней.
)При повороте любой вертикальной грани на ±900 к углам поворотов αs двух кубиков, стоящих в ее противоположных вершинах, добавляется по 1200, а к углам поворотов двух ее других угловых кубиков добавляется по 2400.
)При повороте правой или левой грани на ±900 меняются углы поворотов всех четырех реберных кубиков этой грани.
A(S) = αS(1) + αS(2) + … + αS(S) = βS(1) + βS(2) + … + βS
остаются постоянными при всех поворотах граней. Такие характеристики состояний называются инвариантами. Значения любого инварианта для двух связанных состояний S1 и S2 совпадают. Поэтому равенства A(S1) = A(S2) и B(S1) = B(S2) являются необходимыми условиями связанности состояний. Присоединив к ним аналогичное равенство для еще одного инварианта, получаются достаточные условия.
Перестановкой конечного множества называется любое отображение этого множества на себя. Таким образом, функция σs заданная на множестве {1, …, 8}, является перестановкой этого множества, а τS - перестановка множества {1, … , 12}. С любой операцией F также связаны две перестановки τF и σFэтих же множеств: если нулевое состояние S0 переводится операцией F в состояние S, то, по определению, σS(i) = σF(i), τF(j) = τS(j). Другими словами, σF(i) и τF(j) - это номера тех мест, которые занимают в результате операции F угловой кубик, стоявший на i-м месте, и реберный кубик, стоявший на j-м месте.
Выполнив одну за другой перестановки σ1 и σ2 одного и того же множества, мы снова получим его отображение на себя - перестановку σ. Она называется композицией перестановок σ1 и σ2: σ = σ1 ○ σ2.
Пусть σ - произвольная перестановка множества {1, 2, … , n}. Нарисуем одну под другой две строчки по n точек. Если при перестановке σ число i переходит в j, соединим i-ю точку верхней строки отрезком с j-й точкой нижней строки - мы получим граф перестановки σ. Обозначим через N(σ) число точек пересечения отрезков графа (точку, в которой пересекается больше двух отрезков, сосчитаем столько раз, сколько пар отрезков ее содержит). Перестановка σ называется четной (нечетной), если число N(σ) четно (нечетно). Знак перестановки σ определим равенством ε(σ) = (-1) N(σ). ε(σ) равно 1 или -1 в зависимости от того, четна или нечетна перестановка. Выясним, как зависит четность композиции σ1 ○ σ2 от четностей σ1 и σ2. Граф композиции строится очень просто: совмещаем нижнюю строку графа перестановки σ1 с верхней строкой графа σ2 - получается промежуточный граф, а затем заменяем каждую ломаную в промежуточном графе на отрезок, соединяющий ее концы. Число точек пересечения ломаных в промежуточном графе равно N(σ1) + N(σ2). При распрямлении число точек пересечения ломаных может уменьшиться, но его четность сохранится.
Таким образом, N(σ1 ○ σ2) и N(σ1) + N(σ2) - числа одной четности; следовательно, ε(σ1 ○ σ2) = (-1) N(σ1 ○ σ2) = (-1) N(σ1) + N(σ2)= (-1) N(σ1) × 1N(σ2) = ε(σ1) ○ ε(σ2). Другими словами, композиция двух перестановок четна, если их четности совпадают, и нечетна в противном случае.
Допустим, что перестановка σ множества из n элементов оставляет неподвижными n - mэлементов, а остальные m элементов можно упорядочить так, что первый из них переходит во второй, второй - в третий, i-й - в (i+1)-й, а m-й элемент - опять в первый. Тогда перестановка называется циклом длины m или m-циклом.
Назовем знаком состояния S число ε(S) = ε(σS) ○ ε(τS). Оно равно 1 или -1 в зависимости от того, совпадают или нет четности перестановок σSи τS.
Рассмотрим поворот F любой грани на 900. Пусть в результате этого поворота кубик Рубика перешел из состояния S в состояние S. Тогда σS = σS ○ σF, τS = τS ○ τF. Перестановки σFи τF - это 4-циклы, поэтому они нечетны и ε(σF) = ε(τF) = -1.