Открыть главное меню

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

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

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

ОпределениеПравить

Каждый из поворотов граней кубика Рубика может рассматриваться как элемент симметрической группы множества 48 этикеток кубика Рубика, не являющихся центрами граней. Пометим центры граней буквами   (см. рисунок), а остальные этикетки — числами от 1 до 48. Теперь поворотам соответствующих граней на 90° по часовой стрелке можно сопоставить элементы симметрической группы  :

 
 
 
 
 
 

Тогда группа кубика Рубика   определяется как подгруппа  , порождаемая поворотами шести граней на 90°[2]:

 

СвойстваПравить

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

 

Пусть   — граф Кэли группы   с 18 образующими, которые соответствуют 18 ходам метрики FTM.

Каждая из   конфигураций может быть решена не более чем за 20 ходов FTM. Другими словами, эксцентриситет вершины графа  , соответствующей «собранному» состоянию головоломки, равен 20[7].

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

Наибольший порядок элемента в   равен 1260. Например, последовательность ходов   необходимо повторить 1260 раз[9], прежде чем кубик Рубика вернётся в исходное состояние[10][11].

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

ПодгруппыПравить

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

Центр группыПравить

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

Циклические подгруппыПравить

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

Порядок элемента Последовательность поворотов граней
4  
6  
63  
105  
1260  

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

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

Группа квадратовПравить

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

 

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

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

Супергруппа кубика РубикаПравить

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

Группа всех преобразований кубика Рубика с видимыми ориентациями центров граней называется супергруппой кубика Рубика. Она в   раз больше группы  [5].

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

На графе Кэли   группы   с 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. Архивировано 26 июля 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). Архивировано 24 ноября 2015 года.
  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.

ЛитератураПравить

СсылкиПравить