Superflip

"Superflip" ( ang.  superflip [1] ) nebo 12-flip ( ang.  12-flip [2] ) [K 1] -  Konfigurace Rubikovy kostky , která se od složeného stavu liší tím, že každá z 12 hraných kostek je otočena na jeho místě [1] . "Superflip" je příklad "antipodu" - konfigurace, která vyžaduje maximální možný počet otočení tváře k vyřešení .

"Superflip" se také nazývá transformace (efekt provedení sekvence rotací ploch), která změní orientaci každé z 12 okrajových kostek na opačnou, přičemž zachová orientaci rohových kostek a permutaci prvků [3 ] .

V roce 1992 byl „superflip“ zmíněn v časopise „ Quantum “ pod názvem „reverse solitaire“ [4] .

Vlastnosti

"Superflip" je jednou ze čtyř konfigurací, které mají všechny možné symetrie (další tři konfigurace jsou Pons Asinorum , kompozice "superflip" s Pons Asinorum a počáteční (smontovaná) konfigurace) [5] [6] [7] .

Spolu s transformací identity vstupuje transformace "superflip" do středu grupy Rubikovy kostky [8] [3] [9] :

Některé vlastnosti „superflipu“ závisí na tom, zda je otočení obličeje o 180° považováno za 1 „pohyb“ ( metrika FTM , anglicky  face turn metric ) nebo 2 „pohyby“ (metrika QTM, anglická čtvrtotáčková  metrika ) [K 2 ] .

Lokální maximum v metrice QTM

Pokud sestrojíme Cayleyho graf ze skupiny Rubikovy kostky s 12 generátory odpovídajícími rotacím ploch skládačky o 90°, pak se vrchol grafu odpovídající „superflipu“ ukáže jako lokální maximum . : je dále od vrcholu odpovídajícího identické transformaci než kterýkoli z 12 sousedních vrcholů [10] [2 ] . Tato skutečnost byla jedním z důvodů, proč uvažovat o „superflipu“ jako o kandidátovi na konfiguraci, která je nejdále od výchozí [10] .

Nechť je libovolná sekvence otočení plochy o 90°, jejímž efektem je transformace „superflip“. Dovolit být poslední otočení obličeje v . Díky své symetrii lze „superflip“ přeměnit pomocí rotací a odrazů na sekvenci rotací tváří stejné délky, končící některou z 12 povolených rotací. Tedy kteréhokoli z 12 „sousedů“ „superflipu“ lze získat aplikací sekvence bez poslední rotace, to znamená, že se nachází o 1 rotaci blíže k výchozí konfiguraci [2] .

Optimální řešení

V metrice FTM

V roce 1992 našel Dick T. Winter [10] [7] [11] řešení „superflipu“ ve 20 otočeních obličeje, které lze v Singmasterově notaci zapsat jako [K 3] :

V roce 1995 Michael Reed prokázal optimalitu tohoto řešení v metrice FTM [10] [7] [12] . Jinými slovy, pokud jeden tah počítá otočení kterékoli z ploch o 90° nebo 180°, pak nejkratší řešení „superflipu“ sestává z 20 tahů [13] . "Superflip" byla první konfigurace se známou vzdáleností od shromážděného stavu, která se rovnala 20 "tahům" v metrice FTM [14] [5] .

V roce 2010 se ukázalo, že jakoukoli řešitelnou konfiguraci hlavolamu lze vyřešit ne více než 20 otočeními obličeje [14] . Návrh, že „superflip“ může být „antipod“, tzn. být v maximální možné vzdálenosti od výchozí konfigurace, bylo uvedeno dlouho před stanovením " Božího čísla " Rubikovy kostky [15] [16] .

V metrikách QTM

V roce 1995 našel Michael Reid [17] [7] řešení „superflipu“ ve 24 otáčkách o 90°, což lze zapsat jako [K 4]

Jak ukázal Jerry Bryan v roce 1995, v metrice QTM neexistuje kratší řešení [17] [7] . Jinými slovy, pokud počítáme otočení kterékoli z ploch o 90° v jednom tahu, pak nejkratší řešení „superflipu“ se skládá z 24 tahů.

"Superflip" není "antipod" v metrice QTM: existují konfigurace, které vyžadují více než 24 90° otočení k vyřešení [18] . „Protipod“ v metrice QTM je však další související konfigurace – tzv. „čtyřbodový superflip“ .

"Super Flip se čtyřmi body"

Čtyřbodová transformace ovlivní středy čtyř ze  šesti ploch skládačky a každou z nich vymění za střed protilehlé plochy. "Čtyři body" lze definovat jako účinek sledu zatáček [19] [K 5]

Poté se postupným aplikováním transformací „superflip“ a „čtyřbodový“ [19] získá  „ superflip [složený] se čtyřmi body [17]] .

V roce 1998 Michael Reid ukázal, že vzdálenost mezi čtyřbodovou konfigurací superflipu a počáteční konfigurací v metrice QTM je přesně 26 [20] [21] [19] . „čtyřbodový superflip“ byl první konfigurací s prokázanou potřebou vyřešit 26 pohybů v metrice QTM [21] .

V roce 2014 se ukázalo, že jakoukoli řešitelnou konfiguraci Rubikovy kostky lze vyřešit maximálně 26 rotacemi ploch o 90° [21] .

Viz také

Poznámky

  1. ↑ Slovo „převrácení“ se používá k označení operace převrácení hranové krychle na místě. Viz například Singmaster, 1981 , str. 35, 72: "Thistlethwaite ukázal, že 12-flip (tj. flip všech 12 hran) není v podskupině generované slice a antislice pohyby."
  2. ↑ Metriky viz také Matematika Rubikovy kostky#Metrics of a Configuration Graph .
  3. ↑ Lucas Garron. FB U2 R F2 R2 B2 U' DF U2 R' L' U B2 D R2 U B2 U . alg.cubing.net .
  4. ↑ Lucas Garron. R' UUB L' F U' BDFU D' LDD F' R B' D F' U' B' U D' . alg.cubing.net .
  5. ↑ Lucas Garron. FFBBU D' RRLLU D' . alg.cubing.net .

Zdroje

  1. ↑ 12 Joyner , 2008 , str. 75.
  2. ↑ 1 2 3 David Singmaster. Krychlový kruh, číslo 5 a 6, s. 24 . Kubický kruhový . Jaap Scherphuis. Jaap's Puzzle Page (1982).
  3. ↑ 12 Joyner , 2008 , str. 99.
  4. ↑ V. Dubrovský, A. Kalinin. Novinky z kubologie  // Kvant . - 1992. - č. 11 . Archivováno z originálu 9. listopadu 2014.
  5. ↑ 1 2 Herbert Kociemba. Symetrické vzory: Skupina O h . „Jsou to čtyři kostky, které mají přesně všechny možné symetrie kostky, jedna z nich – Superflip – potřebuje ke generování 20 tahů. Historicky to byla první kostka, u které bylo prokázáno, že potřebuje 20 tahů, a to je stále nejlepší spodní mez pro průměr skupiny kostek.". Archivováno z originálu 9. března 2016.
  6. ↑ Jerry Bryan. Symm(x)=M (zcela symetrické vzory) . Archivováno z originálu 13. dubna 2016.
  7. ↑ 1 2 3 4 5 Michael Reid. M-symetrické polohy . Stránka Rubikova kostka (24. května 2005). Archivováno z originálu 6. července 2015.
  8. ↑ Jaap Scherphuis. Užitečná matematika (odkaz není k dispozici) . Jaapova puzzle stránka . Datum přístupu: 28. února 2016. Archivováno z originálu 24. listopadu 2012. 
  9. ↑ Singmaster, 1981 , s. 31.
  10. ↑ 1 2 3 4 Pochmann, 2008 , s. 16.
  11. ↑ Dik T. Zima. Kociembův algoritmus . Cube Lovers (Po, 18. květen 92 00:49:48 +0200).
  12. ↑ Michael Reid. superflip vyžaduje 20 otočení obličeje . Milovníci kostek (st, 18. ledna 95 10:13:45 -0500).
  13. ↑ Joyner, 2008 , str. 149.
  14. ↑ 1 2 Tomáš Rokicki, Herbert Kociemba, Morley Davidson, John Dethridge. Boží číslo je 20 .
  15. ↑ Joyner, 2008 , str. 149: "Chvíli se hádalo, že pozice superflipu je pozice, která je co nejdále od 'startu' (vyřešené pozice)."
  16. ↑ Singmaster, 1981 , s. 52-53: „Na obrázku je unikátní antipod k I, tj. bod v maximální vzdálenosti 3 od I. <…> Holroyd přemýšlí, zda má celá skupina krychle jedinečný antipod. Vyřešení tohoto může vyžadovat úplný popis Božího algoritmu (str. 34). Navrhuje, že buď 12-flip (str. 28, 31, 35, 48) nebo 12-flip kombinovaný s běžným vzorem 5-X ze skupiny se čtvercovými plátky (str. 11, 20, 48) by mohl být antipod. ".
  17. ↑ 1 2 3 Joyner, 2008 , str. 100.
  18. ↑ Joyner, 2008 , str. 100, 149.
  19. ↑ 1 2 3 Michael Reid. superflip složený ze čtyř bodů . Milovníci kostek (Ne, 2. srpna 1998 08:47:44 -0400). Archivováno z originálu 4. října 2015.
  20. ↑ Joyner, 2008 , str. 100-101.
  21. ↑ 1 2 3 Tomáš Rokicki, Morley Davidson. Boží číslo je 26 ve čtvrtotáčkové metrice .

Literatura