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

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

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

Визначення

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

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

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

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

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

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

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

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

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

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

${\displaystyle G=\langle L,F,R,B,U,D\rangle }$

Властивості

Порядок групи ${\displaystyle G}$ дорівнює^{[1][2][3][4][5]}

${\displaystyle |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}$

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

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

Діаметр графу ${\displaystyle K_{f}}$ також дорівнює 20^[7].

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

${\displaystyle G}$ не є абелевою групою, оскільки, наприклад, ${\displaystyle FR\neq RF}$. Іншими словами, не всі пари поворотів комутують^[10].

Підгрупи

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

Група квадратів (square group) — підгрупа групи ${\displaystyle G}$, породжувана поворотами граней на 180°^[4]:

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

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

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

Центр групи

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

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

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

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

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

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

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

Див. також

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

Примітки

1. Schönert, Martin. Analyzing Rubik's Cube with GAP (англ.). Архів оригіналу за 20 січня 2013. Процитовано 19 липня 2013.
2. В. Дубровский. . — № 8.
3. Jaap Scherphuis. Rubik's Cube 3x3x3 (англ.). Архів оригіналу за 28 липня 2013. Процитовано 19 липня 2013. {{cite web}}: Проігноровано невідомий параметр |subtitle= (довідка)
4. Jaap Scherphuis. Useful Mathematics (англ.). Архів оригіналу за 24 листопада 2012. Процитовано 22 липня 2013.
5. Ryan Heise. Rubik's Cube theory: Laws of the cube (англ.). Архів оригіналу за 2 серпня 2013. Процитовано 21 липня 2013.
6. Rokicki, T.; Kociemba, H.; Davidson, M.; and Dethridge, J. God's Number is 20 (англ.). Архів оригіналу за 21 липня 2013. Процитовано 19 липня 2013.
7. Weisstein, Eric W. Rubik's Cube (англ.). Архів оригіналу за 2 червня 2013. Процитовано 22 липня 2013.
8. Lucas Garron. (R U2 D' B D')1260 (англ.). Архів оригіналу за 5 вересня 2013. Процитовано 22 липня 2013.
9. Joyner, David (2002). Adventures in group theory: Rubik's Cube, Merlin's machine, and Other Mathematical Toys. Baltimore: Johns Hopkins University Press. с. 7. ISBN 0-8018-6947-1.
10. Davis, Tom (2006). Group Theory via Rubik’s Cube (PDF). Архів оригіналу (PDF) за 2 жовтня 2013. Процитовано 22 липня 2013.
11. Jaap Scherphuis. Cube subgroups (англ.). Архів оригіналу за 20 січня 2013. Процитовано 22 липня 2013.
12. Bruce Norskog. A Hamiltonian circuit for Rubik's Cube!. Domain of the Cube Forum. Архів оригіналу за 18 серпня 2013. Процитовано 21 липня 2013.
13. Bruce Norskog. A Hamiltonian circuit for Rubik's Cube!. Speedsolving.com. Архів оригіналу за 30 травня 2014. Процитовано 21 липня 2013.

Джерела

• 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.