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

Розгортка кубика Рубіка. Кожному з поворотів граней відповідає елемент групи 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=\langle L,F,R,B,U,D\rangle$

Властивості

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

$|G|={\dfrac {8!\cdot 12!\cdot 3^{8-1}\cdot 2^{12-1}}{2}}=43\ 252\ 003\ 274\ 489\ 856\ 000=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\neq RF$. Іншими словами, не всі пари поворотів комутують.

Підгрупи

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

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

$G_{sq}=\langle L^{2},F^{2},R^{2},B^{2},U^{2},D^{2}\rangle$

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

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

Центр групи

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

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

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

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

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

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

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

Див. також

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

Джерела

• Joyner, David (2002). Adventures in group theory: Rubik's Cube, Merlin's machine, and Other Mathematical Toys. Baltimore: Johns Hopkins University Press. ISBN 0-8018-6947-1.

Посилання

• W. D. Joyner. Lecture notes on the mathematics of the Rubik's cube (англ.). Архів оригіналу за 5 вересня 2013. Процитовано 22 липня 2013.