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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Развёртка кубика Рубика. Каждому из поворотов граней соответствует элемент группы S48.

Гру́ппа ку́бика Ру́бика — подгруппа симметрической группы S48, элементы которой соответствуют движениям кубика Рубика. Под движением подразумевается эффект хода (поворота одной из граней) или последовательности ходов.

Определение[править | править исходный текст]

Каждый из поворотов граней кубика Рубика может рассматриваться как элемент симметрической группы множества 48 этикеток кубика Рубика, не являющихся центрами граней. Пометим центры граней буквами \{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°[1]:

G=\langle L,F,R,B,U,D\rangle

Свойства[править | править исходный текст]

Порядок группы G равен[1][2][3][4][5]

|G| = \dfrac{8!\cdot 12!\cdot 3^8\cdot 2^{12}}{3\cdot 2\cdot 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[6].

Диаметр графа K_f также равен 20[7].

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

G не является абелевой группой, так как, например, F R\ne R F. Другими словами, не все пары ходов коммутируют[10].

Подгруппы[править | править исходный текст]

Группа квадратов[править | править исходный текст]

Группа квадратов (square group) — подгруппа группы G, порождаемая поворотами граней на 180°[4]:

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

Порядок группы квадратов равен 663552[11].

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

Центр группы[править | править исходный текст]

Центр группы состоит из элементов, коммутирующих с каждым элементом группы. Центр группы кубика Рубика состоит из двух элементов: тождественная перестановка и суперфлип (англ.)[4].

Супергруппа кубика Рубика[править | править исходный текст]

Этикетки, находящиеся в центрах граней кубика Рубика, не перемещаются, но поворачиваются. На обычном кубике Рубика ориентация центров граней невидима.

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

Гамильтонов цикл на графе Кэли[править | править исходный текст]

На графе Кэли K_q группы G с 12 образующими, которые соответствуют ходам метрики QTM, существует гамильтонов цикл. Найденный цикл использует повороты только 5 из 6 граней[12][13].

Существует соответствующая гипотеза (англ.) Ловаса для произвольного графа Кэли.

См. также[править | править исходный текст]

Примечания[править | править исходный текст]

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

Литература[править | править исходный текст]

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

Ссылки[править | править исходный текст]