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

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

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

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

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

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

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

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

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

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

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

Наибольший порядок элемента в равен 1260, а наименьший - 4. Например, последовательность ходов необходимо повторить 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. Архивировано из первоисточника 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.

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

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