Суперфлип

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
«Суперфлип»

«Суперфлип» (англ. superflip[1]) или 12-флип (англ. 12-flip[2])[К 1] — конфигурация кубика Рубика, отличающаяся от собранного состояния тем, что каждый из 12 рёберных кубиков перевёрнут на своём месте[1]. «Суперфлип» является примером «антипода» — конфигурации, требующей для решения максимально возможного числа поворотов граней➤.

«Суперфлипом» также называют преобразование (эффект от выполнения последовательности поворотов граней), которое изменяет ориентацию каждого из 12 рёберных кубиков на противоположную, сохраняя при этом ориентации угловых кубиков и перестановку элементов[3].

В 1992 году «суперфлип» был упомянут в журнале «Квант» под названием «пасьянс „реверс“»[4].

Свойства

[править | править код]

«Суперфлип» — одна из четырёх конфигураций, имеющих все возможные симметрии (другие три конфигурации — Pons Asinorum, композиция «суперфлипа» с Pons Asinorum и начальная (собранная) конфигурация)[5][6][7].

Вместе с тождественным преобразованием, преобразование «суперфлип» входит в центр группы кубика Рубика[8][3][9]:

Некоторые свойства «суперфлипа» зависят от того, считается ли поворот грани на 180° за 1 «ход» (метрика FTM, англ. face turn metric) или за 2 «хода» (метрика QTM, англ. quarter turn metric)[К 2].

Локальный максимум в метрике QTM

[править | править код]

Если построить граф Кэли по группе кубика Рубика c 12 образующими, соответствующими поворотам граней головоломки на 90°, то соответствующая «суперфлипу» вершина графа окажется локальным максимумом: она дальше от вершины, соответствующей тождественному преобразованию чем любая из 12 смежных вершин[10][2]. Этот факт был одной из причин рассматривать «суперфлип» как кандидат в конфигурации, наиболее удалённые от начальной[10].

Пусть — любая последовательность поворотов граней на 90°, эффект которой — преобразование «суперфлип». Пусть — последний поворот грани в . Благодаря симметричности «суперфлипа» можно преобразовать с помощью вращений и отражений в последовательность поворотов граней той же длины, заканчивающуюся любым из 12 допустимых поворотов. Таким образом, любой из 12 «соседей» «суперфлипа» может быть получен применением последовательности без последнего поворота, то есть расположен на 1 поворот ближе к начальной конфигурации[2].

Оптимальное решение

[править | править код]

В метрике FTM

[править | править код]

В 1992 году Дик Т. Винтер[10][7][11] нашёл решение «суперфлипа» в 20 поворотов граней, которое в нотации Сингмастера можно записать как[К 3]:

В 1995 году Майкл Рид доказал оптимальность этого решения в метрике FTM[10][7][12]. Иными словами, если за один ход считать поворот любой из граней на 90° или 180°, то кратчайшее решение «суперфлипа» состоит из 20 ходов[13]. «Суперфлип» стал первой конфигурацией с известным расстоянием от собранного состояния, равным 20 «ходам» в метрике FTM[14][5].

В 2010 году было показано, что любая разрешимая конфигурация головоломки может быть решена не более чем в 20 поворотов граней[14]. Предположение, что «суперфлип» может быть «антиподом», т.е. находиться на максимально возможном расстоянии от начальной конфигурации, было высказано задолго до установления «числа Бога» кубика Рубика[15][16].

В метрике QTM

[править | править код]

В 1995 году Майкл Рид[17][7] нашёл решение «суперфлипа» в 24 поворота на 90°, которое можно записать как[К 4]

Как в 1995 году показал Джерри Брайан, более короткого решения в метрике QTM не существует[17][7]. Иными словами, если за один ход считать поворот любой из граней на 90°, то кратчайшее решение «суперфлипа» состоит из 24 ходов.

«Суперфлип» не является «антиподом» в метрике QTM: существуют конфигурации, для решения которых требуется более 24 поворотов на 90°[18]. Тем не менее, «антиподом» в метрике QTM является другая связанная конфигурация — так называемый «суперфлип с четырьмя точками»➤.

«Суперфлип с четырьмя точками»

[править | править код]

Преобразование «четыре точки» (англ. four-spot) затрагивает центры четырёх из шести граней головоломки, меняя каждый из них местами с центром противоположной грани. «Четыре точки» можно определить как эффект последовательности поворотов[19][К 5]

Тогда «суперфлип с четырьмя точками» (англ. superflip [composed] with four-spot[17]) получается последовательным применением преобразований «суперфлип» и «четыре точки»[19].

В 1998 году Майкл Рид показал, что расстояние между конфигурацией «суперфлип с четырьмя точками» и начальной конфигурацией в метрике QTM в точности равно 26[20][21][19]. «Суперфлип с четырьмя точками» стал первой конфигурацией с доказанной необходимостью для решения 26 ходов в метрике QTM[21].

В 2014 году было показано, что любая разрешимая конфигурация кубика Рубика может быть решена не более чем в 26 поворотов граней на 90°[21].

См. также

[править | править код]

Примечания

[править | править код]
  1. ↑ Слово «flip» используется для обозначения операции переворачивания рёберного кубика на месте. См., например, Singmaster, 1981, p. 35, 72: «Thistlethwaite has shown that the 12-flip (i.e. the flip of all 12 edges) is not in the subgroup generated by slice and antislice moves.»
  2. ↑ О метриках см. также Математика кубика Рубика#Метрики графа конфигураций.
  3. ↑ Lucas Garron. F B U2 R F2 R2 B2 U' D F U2 R' L' U B2 D R2 U B2 U. alg.cubing.net.
  4. ↑ Lucas Garron. R' U U B L' F U' B D F U D' L D D F' R B' D F' U' B' U D'. alg.cubing.net. Дата обращения: 13 апреля 2016. Архивировано 28 апреля 2016 года.
  5. ↑ Lucas Garron. F F B B U D' R R L L U D'. alg.cubing.net. Дата обращения: 28 февраля 2016. Архивировано 5 марта 2016 года.

Источники

[править | править код]
  1. ↑ 1 2 Joyner, 2008, p. 75.
  2. ↑ 1 2 3 David Singmaster. Cubic Circular, Issue 5 & 6, p. 24. Cubic Circular. Jaap Scherphuis. Jaap's Puzzle Page (1982). Дата обращения: 28 февраля 2016. Архивировано 3 апреля 2013 года.
  3. ↑ 1 2 Joyner, 2008, p. 99.
  4. ↑ В. Дубровский, А. Калинин. Новости кубологии // Квант. — 1992. — № 11. Архивировано 9 ноября 2014 года.
  5. ↑ 1 2 Herbert Kociemba. Symmetric Patterns: The Group Oh. — «There are four cubes, which exactly have all possible symmetries of the cube, one of them - the Superflip - needs 20 moves to be generated. Historically this was the first cube which was proven to need 20 moves, and this is still the best lower bound for the diameter of the cube group.» Архивировано 9 марта 2016 года.
  6. ↑ Jerry Bryan. Symm(x)=M (Completely Symmetric Patterns). Архивировано 13 апреля 2016 года.
  7. ↑ 1 2 3 4 5 Michael Reid. M-symmetric positions. Rubik's cube page (24 мая 2005). Архивировано 6 июля 2015 года.
  8. ↑ Jaap Scherphuis. Useful Mathematics. Jaap's Puzzle Page. Дата обращения: 28 февраля 2016. Архивировано из оригинала 24 ноября 2012 года.
  9. ↑ Singmaster, 1981, p. 31.
  10. ↑ 1 2 3 4 Pochmann, 2008, p. 16.
  11. ↑ Dik T. Winter. Kociemba's algorithm. Cube Lovers (Mon, 18 May 92 00:49:48 +0200). Дата обращения: 28 февраля 2016. Архивировано 15 июля 2013 года.
  12. ↑ Michael Reid. superflip requires 20 face turns. Cube Lovers (Wed, 18 Jan 95 10:13:45 -0500). Дата обращения: 28 февраля 2016. Архивировано 8 июля 2013 года.
  13. ↑ Joyner, 2008, p. 149.
  14. ↑ 1 2 Tomas Rokicki, Herbert Kociemba, Morley Davidson, John Dethridge. God's Number is 20. Дата обращения: 28 февраля 2016. Архивировано 21 июля 2013 года.
  15. ↑ Joyner, 2008, p. 149: «For a while it was guessed that the superflip position is the position which is as far from 'start' (the solved position) as possible.».
  16. ↑ Singmaster, 1981, p. 52-53: «In the Figure we see there is a unique antipode to I, i.e. a point at maximal distance 3 from I. <…> Holroyd wonders if the whole group of the cube has a unique antipode. Resolving this may require the complete description of God's algorithm (p 34). He suggests that either the 12-flip (pp 28,31,35,48) or the 12-flip combined with the ordinary 5-X pattern of the slice-squared group (pp 11,20,48) might be an antipode.».
  17. ↑ 1 2 3 Joyner, 2008, p. 100.
  18. ↑ Joyner, 2008, p. 100, 149.
  19. ↑ 1 2 3 Michael Reid. superflip composed with four spot. Cube Lovers (август 1998). Архивировано 4 октября 2015 года.
  20. ↑ Joyner, 2008, pp. 100-101.
  21. ↑ 1 2 3 Tomas Rokicki, Morley Davidson. God's Number is 26 in the Quarter-Turn Metric. Дата обращения: 28 февраля 2016. Архивировано 7 июля 2015 года.

Литература

[править | править код]
  • David Joyner. Adventures in Group Theory: Rubik's Cube, Merlin's Machine, and Other Mathematical Toys. — JHU Press, 2008. — ISBN 0801897262. — ISBN 9780801897269.
  • David Singmaster. Notes on Rubik's Magic Cube. — Enslow Publishers, 1981.
  • Stefan Pochmann. Analyzing Human Solving Methods for Rubik's Cube and similar Puzzles (29 марта 2008). Архивировано 9 ноября 2014 года.
Источник — https://ru.wikipedia.org/w/index.php?title=Суперфлип&oldid=137480803