г.Ставрополь Теория графов и групп на основе математики кубика Рубика. Работа №3162

ТЕОРИЯ ГРАФОВ И ГРУПП НА ОСНОВЕ МАТЕМАТИКИ КУБИКА РУБИКА И ПОИСК АЛГОРИТМА БОГА
Кривчикова Анастасия Витальевна
Свистунова Наталья Владимировна
ГБОУ ВО Ставропольский государственный педагогический
институт, г. Ставрополь.
Кубик Рубика был создан в середине 1970-х венгерским архитектором Эрне Рубиком. В то время он работал в отделе Дизайна интерьера в академии Прикладного искусства в Будапеште. Студентам было сложно понять математическую теорию групп. Работая с группами, Рубик однажды сделал 27 деревянных кубиков, каждый был окрашен в шесть разных цветов. Однакосложить из них один куб, чтобы каждая грань была разного цвета, оказалось довольно трудно. Сам Рубик бился с задачей целый месяц. Первый кубик Рубик был использован как обучающий инструмент, чтобы помочь понять структурное перемещение независимых частей. Но самой большой проблемой оказалось придумать механизм.
С абстрактно-математической точки зрения, Математика кубика Рубика - ряд математических методов для изучения свойств кубика Рубика, алгоритмов сборки и оценки алгоритмов сборки. Разработана на основе теории групп, теории графов, комбинаторики, теории вычислимости [3].
Известно множество алгоритмов, построенных для перевода кубика Рубика из произвольной конфигурации в собранную – в которой все грани одного цвета. В 2010 году доказано, что для решения кубика Рубика из произвольной конфигурации в конечную конфигурацию достаточно не более 20 ходов – поворотов осей граней на 90 и 180. Это число является диаметром графа Кэли группы кубика Рубика. В 2014 году доказано, что для решения куба только движениями с поворотом граней 90 достаточно не более 26 ходов [4].
В математике кубика Рубика существует такое понятие как алгоритм Бога, который решает головоломку в минимально возможное количество ходов.
Существует два широко используемых метода для измерения длины решения (метрики). Первый способ — в котором одним ходомсчитается поворот грани на 90 (четверть оборота, quarterturnmetric, QTM). Во втором способе одним ходом считается не только поворот грани на 90но и оборот в 180 (faceturnmetric, FTM или HTM — half-turnmetric). Таким образом вращение грани на 180 в метрикеQTM считается за два хода, а в метрике FTM – за один [1].
Для указания в тексте длины последовательности для используемой метрики используется нотация, состоящая из цифр числа ходов и строчной первой буквы обозначения метрики. Так, 14q расшифровывается как - 14 ходов в метрике QTM, а 12f – 12 ходов в метрике FTM. Чтобы указать, что число ходов в метрике является минимальным, после обозначения длины последовательности ставится звездочка: 16q* что является оптимальным решением в 16 ходов QТМ [1].
Кубик Рубик может быть использован как пример математической группы.
Каждый из шести поворотов граней кубика Рубика может рассматриваться как элементсимметрической группымножества 48 этикеток кубика Рубика, не являющихся центрами граней. Более конкретно, можно пометить все 48 этикеток числами от 1 до 48 и сопоставить каждому из ходов элемент симметрической группы S48 [2].
Тогда группа кубика Рубика G определяется как подгруппа S48, порождаемая шестью поворотами граней:
G = {F, B, U,D, L, R}
Порядок группы равен:
│G│=
8! ▪ 12! ▪ 38 ▪212
= 43252003274489856000 = 227▪ 314▪ 53▪ 72▪ 11
3 ▪ 2 ▪ 2
Каждая из 4,32 ▪ 1019 конфигураций может быть решена не более чем за 20 ходов, где за один ход считается любой поворот грани [4].
История поиска алгоритма Бога кубика Рубика началась еще с 1980 года, когда открылся список рассылки для любителей кубика Рубика. С тех пор, математики, компьютерщики и любители стремились найти алгоритм Бога — алгоритм, который позволит на практике решать кубик Рубика за минимальное Число ходов. С этой проблемой была связана проблема определения числа Бога — числа ходов, всегда достаточного для сборки головоломки [5].
В июле 2010 года, учитель математики из Дармштадта, Герберт Коцемба, математик из Кентского университета Морли Дэвидсон, программист из пало-Альто, Томас Рокики, и инженер компании GoogleInc. Джон Детридж доказали, что любая конфигурация кубика Рубика может быть решена не более чем за 20 поворотов граней в метрике FTM. Таким образом, Любой поворот грани является ходом. Время расчета составило около 35 лет процессорного времени.
В августе 2014 года, Томасом Рокики и Морли Дэвидсоном доказано, что любая конфигурация кубика Рубика может быть решена не более чем за 26 ходов в метрике QТМ. Время расчета было около 29 лет процессорного времени в суперкомпьютерном центре Огайо [4].
Таким образом,число Бога в метрике FTMоказалось равно 20 ходам, а в метрике QТМ – 26.
Список литературы
1. Дубровский В. Алгоритм волшебного кубика // Квант – 2005. – №7. С – 17.
2. Дубровский В. Алгоритм волшебного кубика // Квант – 2005. – №8. С – 19.
3. Залгаллер В. Венгерский шарнирный кубик//Квант.— 2005.—№12.—С. 17 — 21.
4. Константинов И.Векторное сложение кубика //Наука и жизнь.— 2014.—№ 5.
5. Мыльников М.Всем кубикам кубик//Юный техник.— 2007.—№7.