Rubiks terninggruppe

Rubiks terninggruppe

Opkaldt efter	Rubiks terning
Studerede i	gruppeteori
Gruppebestilling	4.325200327449E+19
Mediefiler på Wikimedia Commons

Rubiks terninggruppen er en undergruppe af den symmetriske gruppe S 48 , hvis elementer svarer til transformationer af Rubiks terning . Transformation betyder effekten af at dreje en hvilken som helst af ansigterne eller en sekvens af drejninger af ansigter [1] .

Definition

Hver af rotationerne af Rubiks terningflader kan betragtes som et element i den symmetriske gruppe af sættet med 48 Rubiks terningetiketter, der ikke er midten af fladerne. Vi markerer centrene af ansigterne med bogstaver (se figuren), og de resterende etiketter med tal fra 1 til 48. Nu, ved at dreje de tilsvarende flader med 90 ° med uret, kan vi forbinde elementerne i den symmetriske gruppe : $\{L,F,R,B,U,D\}$ $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)

Derefter defineres Rubiks terninggruppe som en undergruppe genereret af rotationer af seks flader med 90° [2] : $G$ $S_{{48}}$

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

Egenskaber

Grupperækkefølgen er [2] [3] [4] [5] [6] $G$

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

Lad være Cayley-grafen for en gruppe med 18 generatorer svarende til 18 træk af FTM-metrikken . $K_f$ $G$

Hver af konfigurationerne kan løses i højst 20 FTM-træk. Med andre ord er excentriciteten af grafens toppunkt svarende til puslespillets "samlede" tilstand 20 [7] . $\approx 4{,}32\cdot 10^{19}$ $K_f$

Diameteren på grafen er også 20 [8] . $K_f$

Den højeste rækkefølge af element i er 1260. For eksempel skal rækkefølgen af træk gentages 1260 gange [9], før Rubiks terning vender tilbage til sin oprindelige tilstand [10] [11] . $G$ $(R\ U^{2}\ D^{{\prime }}\ B\ D^{{\prime }})$

$G$ er ikke en abelsk gruppe , da f.eks . Med andre ord, ikke alle par af elementer pendler [12] . $FR\ne RF$

Undergrupper

Hver gruppe, hvis rækkefølge ikke overstiger 12 , er isomorf for en eller anden undergruppe af Rubiks terninggruppen. Enhver ikke-abelsk gruppe, hvis rækkefølge ikke overstiger 24, er også isomorf for en eller anden undergruppe af Rubiks terninggruppen. Grupperne ( cyklisk gruppe af orden 13) og ( dihedral gruppe af orden 26) er ikke isomorfe til nogen undergrupper af Rubiks terninggruppen [13] . $C_{13}$ $D_{26}$

Gruppecenter

Gruppens centrum består af elementer, der pendler med hvert element i gruppen. Centrum af Rubiks terninggruppen består af to elementer: identitetstransformationen og superflip [5] [13] .

Cykliske undergrupper

I juli 1981 beviste Jesper C. Gerved og Torben Maack Bisgaard, at Rubiks terninggruppe indeholder elementer af 73 forskellige ordener fra 1 til 1260, og fandt antallet af elementer af hver mulig orden [14] [15] [16] .

Elementrækkefølge	Ansigtsrotationssekvens
fire	$F$
6	$R^{2}U^{2}$
63	$EN^{-1}$
105	$DA$
1260	${\displaystyle RU^{2}D^{-1}BD^{-1))$

Rubiks terninggruppe indeholder undergrupper af cyklisk orden

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, 402, 4,13 154, 165, 168, 180, 198, 210, 231, 240, 252, 280, 315, 330, 336, 360, 420, 462, 495.

Kun ét element (gruppens identitetselement) har rækkefølge 1; den næst sjældneste orden er 11 ( 44.590.694.400 elementer ); omkring 10,6 % af alle elementer ( 4601524692892926000 ) har orden 60 [14] [16] .

Tabellen viser eksempler på ansigtsrotationssekvenser, der svarer til elementer af visse rækkefølger [11] [17] [18] .

Gruppe af firkanter

Den firkantede gruppe (kvadratisk gruppe) er en undergruppe af gruppen genereret af 180° rotationer af flader [5] [19] : $G$

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

Rækkefølgen af gruppen af kvadrater er 663 552 [20] .

Gruppen af firkanter bruges i Thistlethwaite-algoritmen , ved hjælp af hvilken det var muligt at bevise, at 45 træk er tilstrækkeligt til at løse Rubiks terning.

Rubiks terning supergruppe

Etiketterne placeret i midten af ansigterne på Rubik's Cube bevæger sig ikke, men roteres. På en almindelig Rubiks terning er orienteringen af centrene af ansigterne usynlig.

Gruppen af alle Rubiks terningtransformationer med synlige ansigtscenterorienteringer kaldes Rubiks terning-supergruppen. Den er gange større end gruppen [5] . $\dfrac{4^6}{2}=2048$ $G$

Hamiltonsk cyklus på Cayley-grafen

Der er en Hamilton-cyklus på Cayley-grafen for en gruppe med 12 generatorer svarende til bevægelser af QTM-metrikken . Den fundne cyklus bruger kun rotationer af 5 ud af 6 flader [21] [22] [23] . $K_q$ $G$

Der er en tilsvarende Lovas-formodning for en vilkårlig Cayley-graf.

Se også

Noter

↑ Ofte i litteraturen er tre, strengt taget, forskellige begreber ikke adskilt - tilstanden (konfigurationen) af Rubiks terning, transformationen og rækkefølgen af vendinger af ansigterne ("bevægelser"). Se for eksempel Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Anna Lubiw, Andrew Winslow. Algoritmer til løsning af Rubiks terninger . - "Konfigurationerne af Rubik's Cube, eller tilsvarende transformationerne fra en konfiguration til en anden, danner en undergruppe af en permutationsgruppe, genereret af de grundlæggende twist-bevægelser." Hentet 14. november 2015. Arkiveret fra originalen 3. april 2017. (ubestemt) . Det fremgår normalt af sammenhængen, om vi taler om stater eller om transformationer, der overfører en tilstand til en anden.
↑ 1 2 Schönert, Martin analyserer Rubiks terning med GAP . Hentet 19. juli 2013. Arkiveret fra originalen 5. september 2013.
↑ V. Dubrovsky. Mathematics of the Magic Cube // Kvant. - 1982. - Nr. 8 . - S. 22 - 27, 48 . (Russisk)
↑ Jaap Scherphuis. Rubiks terning 3x3x3 . Antallet af stillinger (engelsk) . Hentet 19. juli 2013. Arkiveret fra originalen 5. september 2013.
↑ 1 2 3 4 Jaap Scherphuis. Nyttig matematik . Hentet 22. juli 2013. Arkiveret fra originalen 5. september 2013.
↑ Ryan Heise. Rubiks terningteori: terningens love (engelsk) . Hentet 21. juli 2013. Arkiveret fra originalen 5. september 2013.
↑ Rokicki, T.; Kociemba, H.; Davidson, M.; og Dethridge, J. Guds tal er 20 . Dato for adgang: 19. juli 2013. Arkiveret fra originalen 26. juli 2013.
↑ Weisstein, Eric W. Rubiks terning . Hentet 22. juli 2013. Arkiveret fra originalen 2. juni 2013.
↑ Lucas Garron. (R U2 D' B D')1260 (engelsk) . Hentet 22. juli 2013. Arkiveret fra originalen 5. september 2013.
↑ Joyner, David. Eventyr i gruppeteori: Rubiks terning , Merlins maskine og andet matematisk legetøj . — Baltimore: Johns Hopkins University Press, 2002. - S. 7 . - ISBN 0-8018-6947-1 .
↑ 1 2 Jamie Mulholland. Foredrag 21: Rubik's Cube: Subgroups of the Cube Group (link unavailable) (2011). Arkiveret fra originalen den 24. november 2015. (ubestemt)
↑ Davis, Tom. Gruppeteori via Rubik's Cube (2006). Hentet 22. juli 2013. Arkiveret fra originalen 5. september 2013. (ubestemt)
↑ 1 2 Mathematics of the Rubik's Cube, 1996 , s. 209.
↑ 1 2 David Singmaster. Cubic Circular, Nummer 3 & 4 . Ordener af elementer (s. 34-35 ) . Hentet 24. november 2015. Arkiveret fra originalen 14. september 2015.
↑ Walter Randelshofer. Mulige ordrer . Hentet 24. november 2015. Arkiveret fra originalen 24. november 2015. (ubestemt)
↑ 1 2 Jesper C. Gerved, Torben Maack Bisgaard. (Brev til David B. Singmaster) (27. juli 1981). Arkiveret fra originalen den 1. august 2015. (ubestemt)(brev til D. Singmaster med tabeller, der indeholder antallet af elementer i hver mulig rækkefølge af Rubiks terninggruppen)
↑ Matematiske miniaturer, 1991 .
↑ Michael ZR Gottlieb. Ordreberegner . Dato for adgang: 24. november 2015. Arkiveret fra originalen 3. februar 2016. (ubestemt)
↑ Mathematics of the Rubik's Cube, 1996 , s. 234.
↑ Jaap Scherphuis. Kube undergrupper . Hentet 22. juli 2013. Arkiveret fra originalen 5. september 2013.
↑ Bruce Norskog. Et Hamilton-kredsløb for Rubik's Cube! . Domæne for Cube Forum. Hentet 21. juli 2013. Arkiveret fra originalen 5. september 2013. (ubestemt)
↑ Bruce Norskog. Et Hamilton-kredsløb for Rubik's Cube! . speedsolving.com. Hentet 21. juli 2013. Arkiveret fra originalen 5. september 2013. (ubestemt)
↑ Mathematics of the Rubik's Cube, 1996 , s. 129.

Litteratur

Joyner, David. Eventyr i gruppeteori: Rubiks terning , Merlins maskine og andet matematisk legetøj . — Baltimore: Johns Hopkins University Press, 2002. - ISBN 0-8018-6947-1 .
Savin A.P. Matematiske miniaturer / Kunstner E. Shabelnik. - M . : Børnelitteratur , 1991. - S. 79-81. — 127 s. - (Kend og kunne). - ISBN 5-08-000596-3 .
WD Joyner. Mathematics of the Rubik's Cube (1996). Dato for adgang: 5. december 2015. Arkiveret fra originalen 20. februar 2016. (ubestemt)