Matroids Matheplanet Forum Index
Moderiert von Buri Gockel
Strukturen und Algebra » Gruppen » Gruppentheorie beim 2x2x2-Rubik's Cube
Autor
Kein bestimmter Bereich Gruppentheorie beim 2x2x2-Rubik's Cube
ograsse
Neu Letzter Besuch: im letzten Monat
Dabei seit: 31.07.2022
Mitteilungen: 3
  Themenstart: 2022-07-31 14:08

Hallo Forum, ich möchte gern gruppentheoretische Überlegungen zum Lösen des 2x2x2 Rubiks Cube verwenden. Dazu würde ich zunächst einmal auch diesen Würfel noch weiter vereinfachen, nämlich so, dass alle Ecken sozusagen unabhängig von ihrer konkreten Farbbelegung betrachtet werden sollen, sprich die Ecken können einfach mit den Zahlen 1 - 8 wie in der folgenden Anordnung gezeigt, notiert werden: 8 -- 7 /| /| 4 -- 3 | | 5 -| 6 |/ |/ 1 -- 2 OBdA. kann man nun immer davon ausgehen, dass eine Ecke richtig positioniert ist, sagen wir die 8, d.h. alle anderen sieben Ecken sind im Allgemeinen eine Permutation von (1,2,3,4,5,6,7). Es gibt also 7! Möglichkeiten diese anzuordnen. Man kann sich nun weiter klar machen, dass sich alle Bewegungen aus den Drehungen am Würfel zusammen setzen, die üblicherweise mit F,B,U,D,R,L gekennzeichnet werden (von Front, Back, Up, Down, Right, Left). Ein Strich am Buchstaben kennzeichnet das Inverse und wegen der Fixierung der 8 reicht es aus, lediglich 3 der 6 Drehungen zu betrachten, also F, R, D und deren Inverse F', R', D': F=B'=(2,3,4,1, 5,6,7)=(1,2,3,4) F'=F3=B=(4,1,2,3,5,6,7)=(4,3,2,1) R=L'=(1,6,2,4,5,7,3)=(2,6,7,3) R'=R3=L=(1,3,7,4,5,2,6)=(3,7,6,2) D=U'=(5,1,3,4,6,2,7)=(1,5,6,2) D'=D3=U=(2,6,3,4,1,5,7)=(2,6,5,1) Das letzte Gleichheitszeichen nutzt die Zyklenschreibweise. Die Verknüpfung von Drehungen soll in Leserichtung, also von links nach rechts erfolgen, bspw. wäre F ○ R = (6,2,4,1,5,7,3)=(1,6,7,3,4) Das dient erst einmal nur der Vorbereitung, ich hoffe, es gibt bis hierher keine Fehler. Nun möchte ich gern mit diesen 6 Bewegungen Züge erstellen, die den Würfel lösen aber eben per Rechnung. D.h. wenn eine beliebige Permutation $\pi$ gegeben ist, möchte ich $\pi$', das selbst ja einfach anzugeben ist, nun als Folge von Verknüpfungen zwischen F, R, D, F', R', D' darstellen. Und das ist nun nicht so einfach und dafür bräuchte ich bitte eine Idee :) Ich habe im übrigen auch den Artikel "Ein Spiel mit Gruppenstruktur" hier auf der Seite gelesen, das hat mir leider nicht geholfen. viele Grüße Olli


   Profil
Triceratops
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 28.04.2016
Mitteilungen: 6372
Wohnort: Nordamerika
  Beitrag No.1, eingetragen 2022-07-31 23:13

Ich denke, es ist keine gute Idee, die 8 als gelöst zu betrachten und auch noch während der gesamten Drehnungen zu fixieren. Dadurch schränkst du die möglichen Züge stark ein, was unpraktisch ist aber teilweise auch zu Permutationen führt, die eben deshalb nicht lösbar sind. Außerdem verlierst du dadurch natürlich die gesamte Symmetrie des Würfels. Ein weiterer Fehler besteht darin, dass du davon auszugehen scheinst, dass jede Permutation auftreten kann. Das ist aber nicht der Fall. Der 2er Cube (ohne die von dir gemachte Vereinfachung) hat 3.674.160 mögliche Kombinationen, das heißt solche, die vom Ursprungszustand aus durch Rotationen erreichbar sind. Du kannst das ja einmal mit der Liste aller theoretisch möglichen Kombinationen vergleichen (die ist viel größer). Ich würde an deiner Stelle erst einmal zu Materialien im Internet hiernach suchen. Das ist schließlich ein sehr bekanntes Problem. Das heißt, ich würde hier nicht bei 0 anfangen.


   Profil
ograsse
Neu Letzter Besuch: im letzten Monat
Dabei seit: 31.07.2022
Mitteilungen: 3
  Beitrag No.2, vom Themenstarter, eingetragen 2022-08-01 08:40

Hallo Triceratops, danke für deine Antwort. Ich verstehe in gewisser Weise, worauf du hinaus möchtest, daher muss ich wohl kurz etwas zur Motivation sagen. Den kleinen, sowie den großen Würfel kann ich bereits lösen, auch ohne Mathematik. Ein bisschen Gruppentheorie kann ich auch und möchte das nun zusammen bringen. Du hast recht, es gibt da bereits viel Literatur dazu. Aber zugleich sprichst du auch die Probleme an, die ich selbst damit habe. Zum einen ist die kleine und erst recht die große Würfelgruppe sehr groß, ich möchte sagen zu groß, um wirklich überblickt zu werden (jedenfalls noch für mich), meine Vereinfachung auf besagte 7!=5040 Permutationen dagegen ist überschaubar. Weiter sprichst du an, dass durch die Vereinfachung die gesamte Symmetrie des Würfels verloren geht. Das habe ich mich auch gefragt bzw. mehr mathematisch, bildet die Reduktion strukturerhaltend auf eine Untergruppe der kleinen Würfelgruppe ab? Du verneinst das strikt, ich bin mir da nicht so sicher und prüfe das noch. Damit hängt natürlich zusammen, ob alle Permutationen erreicht werden können. Was ich gerade mache ist daher folgendes (mit Computerunterstützung), ich versuche alle Züge, die man aus F, R und D zusammen setzen kann unter Berücksichtigung sowohl ihrer Zyklizität (schließlich ist $F^4=1$ usw.), also auch der Zyklizität der zusammengesetzten Züge zu erfassen und dann zu schauen, ob alle Permutationen erreicht werden konnten. Also kurz, ich prüfe, ob F, R, D ein Erzeugendensystem ist. Das ist jetzt sicher brute force, aber hier geht das wie gesagt noch und eine andere Idee habe ich nicht.


   Profil
Slash
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.03.2005
Mitteilungen: 8950
Wohnort: Sahlenburg (Cuxhaven)
  Beitrag No.3, eingetragen 2022-08-01 10:01

Moin Olli, hast du mal mit den Worten "2x2x2 Rubik's Cube group theory" gegoogelt? Da finden sich gleich auf Seite 1 eine Menge PDFs. Gruß, Slash


   Profil
ograsse
Neu Letzter Besuch: im letzten Monat
Dabei seit: 31.07.2022
Mitteilungen: 3
  Beitrag No.4, vom Themenstarter, eingetragen 2022-08-02 09:33

Hallo Slash, natürlich hatte ich zunächst gegoogelt und dadurch auch auf diese Seite gefunden, allerdings auf deutsch. Insofern war dein Hinweis auf englisch zu suchen goldrichtig, danke dafür. Und tatsächlich lieferte bereits das erste Resultat genau das richtige Ergebnis (siehe hier). Dort wird sogar noch weiter reduziert, nicht eine Ecke, sondern eine Kante (also zwei benachbarte Ecken) wird fixiert. Das reduziert auch die verbleibenden Bewegungsmöglichkeiten auf zwei Drehungen, nämlich R und U; der Autor betrachtet dann im folgenden nur die 2-Erzeuger-Gruppe aus diesen beiden Bewegungen, also G=. Das ist noch einmal deutlich übersichtlicher als meine 3-Erzeuger-Gruppe . Wie ich betrachtet er im Folgenden die Untergruppe K von G, die nur die Orientierungen der Ecken wechselt, um letztlich den Quotienten G/K zu bilden, von dem er zeigt, dass er isomorph zu $S_5$ ist. Letzteres habe ich leider nicht verstanden, weil er Notationen benutzt, die ich nicht kenne. Vielleicht weiss hier ja jemand mehr. So schreibt er bspw. auf S.5 von der "projective line $\mathbb{P}^1(\mathbb{F}_5)$", wo ich nicht weiss, was $\mathbb{P}^1(\mathbb{F}_5)$ bedeutet. Er leitet daraus aber dann weiter $PGL(2,\mathbb{F}_5)$ ab usw. Im Wesentlichen ist mir der ganze Anpunkt 2) auf S.5 unverständlich geblieben. Es wäre toll, wenn da jemand mal raufschauen und es mir kurz erklären könnte. einen schönen Tag euch allen Olli


   Profil
Folgende Antworten hat der Fragesteller vermutlich noch nicht gesehen.
Er/sie war noch nicht wieder auf dem Matheplaneten
StefanVogel
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 26.11.2005
Mitteilungen: 4100
Wohnort: Raun
  Beitrag No.5, eingetragen 2022-08-06 07:15

Hallo ograsse, zur Frage aus dem Themenstart, das schafft das GAP-Programm. \quoteon(2022-07-31 14:08 - ograsse im Themenstart) F=B'=(2,3,4,1, 5,6,7)=(1,2,3,4) R=L'=(1,6,2,4,5,7,3)=(2,6,7,3) D=U'=(5,1,3,4,6,2,7)=(1,5,6,2) Das letzte Gleichheitszeichen nutzt die Zyklenschreibweise. \quoteoff \sourceon GAP gap> F:=(1,2,3,4); (1,2,3,4) gap> R:=(2,6,7,3); (2,6,7,3) gap> D:=(1,5,6,2); (1,5,6,2) \sourceoff \quoteon ... F'=F3=B=(4,1,2,3,5,6,7)=(4,3,2,1) ... R'=R3=L=(1,3,7,4,5,2,6)=(3,7,6,2) ... D'=D3=U=(2,6,3,4,1,5,7)=(2,6,5,1) \quoteoff \sourceon gap> B:=F^-1; (1,4,3,2) gap> L:=R^-1; (2,3,7,6) gap> U:=D^-1; (1,2,6,5) gap> B=F^3; true gap> L=R^3; true gap> U=D^3; true \sourceoff \quoteon Die Verknüpfung von Drehungen soll in Leserichtung, also von links nach rechts erfolgen, bspw. wäre F ○ R = (6,2,4,1,5,7,3)=(1,6,7,3,4) Das dient erst einmal nur der Vorbereitung, ich hoffe, es gibt bis hierher keine Fehler. \quoteoff \sourceon gap> F*R; (1,6,7,3,4) \sourceoff stimmt überein bis jetzt. \quoteon Nun möchte ich gern mit diesen 6 Bewegungen Züge erstellen, die den Würfel lösen aber eben per Rechnung. D.h. wenn eine beliebige Permutation $\pi$ gegeben ist, möchte ich $\pi$', das selbst ja einfach anzugeben ist, nun als Folge von Verknüpfungen zwischen F, R, D, F', R', D' darstellen. Und das ist nun nicht so einfach und dafür bräuchte ich bitte eine Idee :) \quoteoff Das geht dann mit Expressing Group Elements as Words in Generators. Als Beispiel verwende ich die Permutation \(\pi\)=(1,2). \sourceon gap> GruppeFRD:=Group(F,R,D); Group([ (1,2,3,4), (2,6,7,3), (1,5,6,2) ]) gap> Size(GruppeFRD); 5040 gap> Epi:=EpimorphismFromFreeGroup(GruppeFRD:names:=["F","R","D"]); [ F, R, D ] -> [ (1,2,3,4), (2,6,7,3), (1,5,6,2) ] gap> pi:=(1,2); (1,2) gap> PreImagesRepresentative(Epi,pi); R*D^-1*R^-1*(D*F^-2)^2*D^-1*F gap> #Probe: gap> R*D^-1*R^-1*(D*F^-2)^2*D^-1*F; (1,2) \sourceoff Das Ergebnis lautet \(\pi=\pi'\)=R*D^-1*R^-1*(D*F^-2)^2*D^-1*F. Mit den Gruppenbezeichnungen aus dem pdf kenne ich mich nicht so sehr aus, speziell ob die in dem Zusammenhang mehr bedeuten als nur eine Bezeichnung der auftretenden Gruppen. Die Berechnungen damit sollten aber auch mit dem GAP-Programm machbar sein. Da sind Gruppen wie PGL enthalten. Viele Grüße, Stefan


   Profil
StefanVogel
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 26.11.2005
Mitteilungen: 4100
Wohnort: Raun
  Beitrag No.6, eingetragen 2022-08-07 07:50

Anstelle der Flächenbezeichnungen A1, A2, A3 im pdf verwende ich 11, 12, 13. Für B1, B2, B3 dann 21, 22, 23 und so weiter bis 61, 62, 63 für F1, F2, F3. Dann erzeuge ich aus den Drehungen R und U die Gruppe G. \sourceon GAP gap> R:=(31,62,52,43)(32,63,53,41)(33,61,51,42); (31,62,52,43)(32,63,53,41)(33,61,51,42) gap> U:=(11,21,31,41)(12,22,32,42)(13,23,33,43); (11,21,31,41)(12,22,32,42)(13,23,33,43) gap> G:=Group(R,U); gap> Size(G); 29160 \sourceoff Die Untergruppe K besteht aus allen Permutationen in G, die die Position der Ecken unverändert lassen und nur die Ausrichtung der Ecken ändern, also die 11 nur auf 11, 12 oder 13 abbilden, 21 nur auf 21, 22 oder 23 und so weiter bis 61 nur auf 61, 62 oder 63. Eine Permutation g auf Element 11 anwenden wird in GAP als 11^g geschrieben. \sourceon gap> L:=Filtered(G,g->((11^g in [11,12,13])and(21^g in [21,22,23])and(31^g in [31,32,33])and(41^g in [41,42,43])and(51^g in [51,52,53])and(61^g in [61,62,63]))); [ (), (51,53,52)(61,62,63), (51,52,53)(61,63,62), ... ] gap> K:=Subgroup(G,L); gap> Size(K); 243 gap> Size(K)=3^5; true \sourceoff K ist ein Normalteiler von G, deshalb kann die Faktorgruppe F=G/K gebildet werden. \sourceon gap> IsNormal(G,K); true gap> F:=FactorGroup(G,K); Group([ (3,6,5,4), (1,2,3,4) ]) gap> Size(F); 120 \sourceoff und diese Faktorgruppe F=G/K ist isomorph zu S5, PGL(2,5) und einer aus h1 und h2 erzeugten Untergruppe H. \sourceon gap> S:=SymmetricGroup(5); Sym( [ 1 .. 5 ] ) gap> IsomorphismGroups(F,S); [ (1,2)(3,4)(5,6), (1,2,3,5,4,6) ] -> [ (3,4), (1,2,3)(4,5) ] gap> gap> gap> P:=PGL(2,5); Group([ (3,6,5,4), (1,2,5)(3,4,6) ]) gap> IsomorphismGroups(F,P); [ (1,2)(3,4)(5,6), (1,2,3,5,4,6) ] -> [ (1,2)(3,4)(5,6), (1,2,3,5,4,6) ] gap> gap> gap> h1:=R*U*R^-1*U*R*U^-1*R^-1*U*R*U^2*R^-1*U; (11,22,31,42)(12,23,32,43)(13,21,33,41) gap> h2:=U*R*U^-1*R*U*R^-1*U^-1*R*U*R^2*U^-1*R; (31,61,52,42)(32,62,53,43)(33,63,51,41) gap> H:=Group(h1,h2); gap> IsomorphismGroups(F,H); [ (1,2)(3,4)(5,6), (1,2,3,5,4,6) ] -> [ (11,22)(12,23)(13,21)(31,42)(32,43)(33,41)(51,63)(52,61)(53,62), (11,22,31,52,42,61)(12,23,32,53,43,62)(13,21,33,51,41,63) ] \sourceoff Warum es gut ist zu wissen, dass F=G/K nicht nur zu S5 sondern auch zu PGL(2,5) und H isomorph ist, das habe ich noch nicht verstanden.


   Profil

Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2022 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]