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

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

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

Определение[править | править вики-текст]

Каждый из поворотов граней кубика Рубика может рассматриваться как элемент симметрической группы множества 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°[2]:

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

Свойства[править | править вики-текст]

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

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

Каждая из \approx 4{,}32\cdot 10^{19} конфигураций может быть решена не более чем за 20 ходов FTM. Другими словами, эксцентриситет вершины графа K_f, соответствующей «собранному» состоянию головоломки, равен 20[7].

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

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

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

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

Каждая группа, порядок которой не превышает 12, изоморфна некоторой подгруппе группы кубика Рубика. Каждая неабелева группа, порядок которой не превышает 24, также изоморфна некоторой подгруппе группы кубика Рубика. Группы C_{13} (циклическая группа порядка 13) и D_{26} (диэдральная группа порядка 26) не изоморфны никаким подгруппам группы кубика Рубика[13].

Центр группы[править | править вики-текст]

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

Циклические подгруппы[править | править вики-текст]

В июле 1981 года Jesper C. Gerved и Torben Maack Bisgaard доказали, что группа кубика Рубика содержит элементы 73 различных порядков от 1 до 1260, и нашли число элементов каждого возможного порядка[14][15][16].

Группа кубика Рубика содержит циклические подгруппы порядков

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 18, 20, 21, 22, 24, 28, 30, 33, 35, 36, 40, 42, 44, 45, 48, 55, 56, 60, 63, 66, 70, 72, 77, 80, 84, 90, 99, 105, 110, 112, 120, 126, 132, 140, 144, 154, 165, 168, 180, 198, 210, 231, 240, 252, 280, 315, 330, 336, 360, 420, 462, 495, 504, 630, 720, 840, 990, 1260.

Лишь один элемент (единичный элемент группы) имеет порядок 1; второй наиболее редкий порядок — 11 (44 590 694 400 элементов); около 10,6 % всех элементов (4 601 524 692 892 925 952) имеют порядок 60[14][16].

В таблице приведены примеры последовательностей поворотов граней, соответствующих элементам некоторых порядков[11][17][18].

Порядок элемента Последовательность поворотов граней
4 F
6 R^2 U^2
63 R U^{-1}
105 R U
1260 R U^2 D^{-1} B D^{-1}

Группа квадратов[править | править вики-текст]

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

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

Порядок группы квадратов равен 663 552[20].

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

Супергруппа кубика Рубика[править | править вики-текст]

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

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

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

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

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

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

  1. Часто в литературе не разделяются три, строго говоря, различных понятия — состояние (конфигурация) кубика Рубика, преобразование и последовательность поворотов граней («ходов»). См., например, Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Anna Lubiw, Andrew Winslow. Algorithms for Solving Rubik's Cubes. — «The configurations of the Rubik's Cube, or equivalently the transformations from one configuration to another, form a subgroup of a permutation group, generated by the basic twist moves». Обычно из контекста ясно, идёт ли речь о состояниях или о преобразованиях, переводящих одно состояние в другое.
  2. 1 2 Schönert, Martin Analyzing Rubik's Cube with GAP (англ.). Проверено 19 июля 2013. Архивировано из первоисточника 5 сентября 2013.
  3. В. Дубровский Математика волшебного кубика (рус.) // Квант. — 1982. — № 8. — С. 22 — 27, 48.
  4. Jaap Scherphuis. Rubik's Cube 3x3x3 The number of positions (англ.). Проверено 19 июля 2013. Архивировано из первоисточника 5 сентября 2013.
  5. 1 2 3 4 Jaap Scherphuis. Useful Mathematics (англ.). Проверено 22 июля 2013. Архивировано из первоисточника 5 сентября 2013.
  6. Ryan Heise. Rubik's Cube theory: Laws of the cube (англ.). Проверено 21 июля 2013. Архивировано из первоисточника 5 сентября 2013.
  7. Rokicki, T.; Kociemba, H.; Davidson, M.; and Dethridge, J. God's Number is 20 (англ.). Проверено 19 июля 2013. Архивировано из первоисточника 27 июля 2013.
  8. Weisstein, Eric W. Rubik's Cube (англ.). Проверено 22 июля 2013.
  9. Lucas Garron. (R U2 D' B D')1260 (англ.). Проверено 22 июля 2013. Архивировано из первоисточника 5 сентября 2013.
  10. 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.
  11. 1 2 Jamie Mulholland. Lecture 21: Rubik's Cube: Subgroups of the Cube Group (2011).
  12. Davis, Tom. Group Theory via Rubik’s Cube (2006). Проверено 22 июля 2013. Архивировано из первоисточника 5 сентября 2013.
  13. 1 2 Mathematics of the Rubik's Cube, 1996, p. 209
  14. 1 2 David Singmaster. Cubic Circular, Issue 3 & 4 Orders of Elements (pp. 34-35) (англ.). Проверено 24 ноября 2015. Архивировано из первоисточника 14 сентября 2015.
  15. Walter Randelshofer. Possible orders.
  16. 1 2 Jesper C. Gerved, Torben Maack Bisgaard. (Letter to David B. Singmaster) (27 июля 1981). Архивировано из первоисточника 1 августа 2015. (письмо Д. Сингмастеру с таблицами, содержащими число элементов каждого возможного порядка группы кубика Рубика)
  17. Математические миниатюры, 1991
  18. Michael Z. R. Gottlieb. Order Calculator.
  19. Mathematics of the Rubik's Cube, 1996, p. 234
  20. Jaap Scherphuis. Cube subgroups (англ.). Проверено 22 июля 2013. Архивировано из первоисточника 5 сентября 2013.
  21. Bruce Norskog. A Hamiltonian circuit for Rubik's Cube!. Domain of the Cube Forum. Проверено 21 июля 2013. Архивировано из первоисточника 5 сентября 2013.
  22. Bruce Norskog. A Hamiltonian circuit for Rubik's Cube!. Speedsolving.com. Проверено 21 июля 2013. Архивировано из первоисточника 5 сентября 2013.
  23. Mathematics of the Rubik's Cube, 1996, p. 129

Литература[править | править вики-текст]

Ссылки[править | править вики-текст]