Група кубика Рубіка

Розгортка кубика Рубіка. Кожному з поворотів граней відповідає елемент групи S₄₈.

Група кубика Рубіка — підгрупа симетричної групи S₄₈, елементи якої відповідають рухам кубика Рубіка. Під рухом йдеться про поворот однієї з граней або послідовність таких поворотів.

Визначення

У 3×3×3 кубика 6 граней по 9 етикеток, але центральні етикетки граней при будь-яких рухах залишаються на своїх місцях.

Позначимо центри граней літерами $\{L,F,R,B,U,D\}$ (див. малюнок), а інші етикетки — числами від 1 до 48.

Тепер поворотам відповідних граней на 90° за годинниковою стрілкою ми можемо зіставити елементи симетричної групи $S_{48}$ етикеток кубика Рубіка, які не є центрами граней:

$L=(1,3,8,6)(2,5,7,4)(33,9,41,32)(36,12,44,29)(38,14,46,27)$

$F=(9,11,16,14)(10,13,15,12)(38,17,43,8)(39,20,42,5)(40,22,41,3)$

$R=(17,19,24,22)(18,21,23,20)(48,16,40,25)(45,13,37,28)(43,11,35,30)$

$B=(25,27,32,30)(26,29,31,28)(19,33,6,48)(21,34,4,47)(24,35,1,46)$

$U=(33,35,40,38)(34,37,39,36)(25,17,9,1)(26,18,10,2)(27,19,11,3)$

$D=(41,43,48,46)(42,45,47,44)(6,14,22,30)(7,15,23,31)(8,16,24,32)$

Тоді група кубика Рубіка $G$ визначається як підгрупа $S_{48}$, породжена поворотами шести граней на 90°:

$G=⟨L,F,R,B,U,D⟩$

Властивості

Порядок групи $G$ дорівнює

$|G|=\frac{8!\cdot 12!\cdot 3^{8-1}\cdot 2^{12-1}}{2}=43252003274489856000=2^{27}\cdot 3^{14}\cdot 5^3\cdot 7^2\cdot 11$

Нехай $K_f$ — граф Келі групи $G$ з 18 утворюючими, які відповідають 18 ходам метрики FTM.

Кожна з $4,32\cdot 10^{19}$ конфігурацій може бути вирішена не більше ніж за 20 ходів FTM. Іншими словами, ексцентриситет вершини графу $K_f$, яка відповідає «зібраному» стану головоломки, дорівнює 20.

Діаметр графу $K_f$ також дорівнює 20.

Найбільший порядок елемента в $G$ дорівнює 1260. Наприклад, послідовність ходів $(R{U}^2{D}^{\prime }B{D}^{\prime })$ необхідно повторити 1260 разів, перш ніж кубик Рубіка повернеться до початкового стану.

$G$ не є абелевою групою, оскільки, наприклад, $FR\ne RF$. Іншими словами, не всі пари поворотів комутують.

Підгрупи

Група квадратів

Група квадратів (square group) — підгрупа групи $G$, породжувана поворотами граней на 180°:

$G_{sq}=⟨L^2,F^2,R^2,B^2,U^2,D^2⟩$

Порядок групи квадратів дорівнює 663 552.

Група квадратів використовується в алгоритмі Тістлетуейта, за допомогою якого вдалося довести достатність 45 ходів для складання кубика Рубика.

Центр групи

Центр групи складається з елементів, що комутують з кожним елементом групи. Центр групи кубика Рубіка складається з двох елементів: тотожна перестановка та Шаблон:Нп.

Супергрупа кубика Рубіка

Етикетки, що знаходяться в центрах граней кубика Рубіка, не переміщаються, але повертаються. На звичайному кубику Рубіка орієнтація центрів граней невидима.

Група всіх рухів кубика Рубіка з видимими орієнтаціями центрів граней називається супергрупою кубика Рубика. Вона в $\frac{4^6}{2}=2048$ разів більше групи $G$.

Гамільтонів цикл на графі Келі

На графі Келі $K_q$ групи $G$ з 12 утворюючими, які відповідають ходам метрики QTM, існує гамільтонів цикл. Знайдений цикл використовує повороти лише 5 з 6 граней.

Існує відповідна гіпотеза Ласло Ловаса для довільного графа Келі.

Див. також

• Гамільтонів граф
• Граф Келі
• Математика кубика Рубіка
• Нормальна підгрупа
• Перестановка
• Теорія груп

Джерела

• Шаблон:Cite book

Посилання

• Шаблон:Cite web