Bahnformel Kombinatorik < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Gegeben sei ein 3x3 Quadrat. Jede der 9 Flächen wird entweder schwarz oder weiß gefärbt. Wie viele verschiedene Färbungen gibt es bis auf Drehung des Quadrates? |
Hallo,
ich brauche glaube ich Hilfe bei dieser Aufgabe.
Es geht wie gesagt um die Anzahl Färbungen, die am besten über die 2.Bahnformel bestimmt werden sollen. Vom Vorgehen mal unabhängig tue ich mich mit der Bestimmung der Fixpunkte für jede Drehung etwas schwer.
Für eine Drehung um 360° sind alle 512 Quadrate Fixpunkte, die Drehung um 180° sollte eigentlich auch nicht so schwer sein.
Ich bin bisher an solche Aufgaben immer so drangegangen, dass ich mir überlegt habe, welche Flächen, Ecken, Punkte welche Anforderungen erfüllen müssen, damit es einen Fixpunkt produziert.
Wenn ihr mir bei der Drehung um 90° (und die um 270°, die damit ja irgendwie einhergeht meine ich) helfen könnt wäre ich euch sehr dankbar.
Liebe Grüße
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:00 So 16.11.2014 | | Autor: | tobit09 |
Hallo Killercat,
was besagt die 2. Bahnformel?
Viele Grüße
Tobias
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:10 So 16.11.2014 | | Autor: | Killercat |
Die 2.Bahnformel - so wie ich sie kennengelernt habe - besagt, dass die Anzahl der Bahnen gerade gleich ist der durchschnittlichen Anzahl an Fixpunkten pro Bahn.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:08 So 16.11.2014 | | Autor: | tobit09 |
> Die 2.Bahnformel - so wie ich sie kennengelernt habe -
> besagt, dass die Anzahl der Bahnen gerade gleich ist der
> durchschnittlichen Anzahl an Fixpunkten pro Bahn.
Leider ist mir diese Formulierung nicht wirklich klar.
Könntest du die zweite Bahnformel inklusiv aller Voraussetzungen mal wörtlich abtippen?
Wahrscheinlich kann ich dir dann helfen.
|
|
|
| |
|
Kein Problem:
Def: [mm] GxM \rightarrow M [/mm] sei eine Gruppenwirkung, und g ein Element aus G.
[mm] F_g = {x \in M | gx=x} [/mm] die Menge aller Fixpunkte von g.
Weiterhin sei [mm] X(g) = |F_g|[/mm]
sowie M,G endlich, M/G = [mm] {B_1,...,B_t} [/mm] die Menge der Bahnen. Dann gilt folgender Satz:
2.Bahnformel: [mm] |M/G| = \frac {1}{|G|} \sum {X(g)} [/mm]
So stehts in meinem Skript.
Um vielleicht mein Problem nochmal zu erklären. Die operierende Gruppe müsste ja die C4 sein; es gibt 4 Drehungen. Als Hinweis steht bei der Aufgabe jetzt folgendes, was mich etwas stutzig macht (zwecks mangelnder Zeichenfunktion versuch ich es mal aufzuschreiben):
121
212 sei eine mögliche Färbung des Würfels
212
Diese wird als äquivalent betrachtet zu:
122
211
122 (was einer Drehung um 270° im Uhrzeigersinn/90° gegen entsprechen soll)
Mein Gedankenansatz war jetzt nach Bedingungen an die Färbung zu suchen, um damit die Fixpunkte zu bestimmen. Nur leider klappt das irgendwie nicht so wirklich.
Liebe Grüße
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 14:48 So 16.11.2014 | | Autor: | tobit09 |
> Def: [mm]GxM \rightarrow M[/mm] sei eine Gruppenwirkung, und g ein
> Element aus G.
> [mm]F_g = {x \in M | gx=x}[/mm] die Menge aller Fixpunkte von g.
> Weiterhin sei [mm]X(g) = |F_g|[/mm]
> sowie M,G endlich, M/G =
> [mm]{B_1,...,B_t}[/mm] die Menge der Bahnen. Dann gilt folgender
> Satz:
> 2.Bahnformel: [mm]|M/G| = \frac {1}{|G|} \sum {X(g)}[/mm]
Danke! Diese Formel kannte ich tatsächlich noch nicht.
> Um vielleicht mein Problem nochmal zu erklären. Die
> operierende Gruppe müsste ja die C4 sein; es gibt 4
> Drehungen.
Ja. Und die Drehung um 90 Grad erzeugt die Gruppe. Also ist die Gruppe tatsächlich zyklisch.
> Als Hinweis steht bei der Aufgabe jetzt
> folgendes, was mich etwas stutzig macht (zwecks mangelnder
> Zeichenfunktion versuch ich es mal aufzuschreiben):
> 121
> 212 sei eine mögliche Färbung des Würfels
> 212
>
> Diese wird als äquivalent betrachtet zu:
> 122
> 211
> 122 (was einer Drehung um 270° im Uhrzeigersinn/90°
> gegen entsprechen soll)
Warum macht dich das stutzig?
> Mein Gedankenansatz war jetzt nach Bedingungen an die
> Färbung zu suchen, um damit die Fixpunkte zu bestimmen.
> Nur leider klappt das irgendwie nicht so wirklich.
Du hast offenbar (ohne sie explizit hingeschrieben zu haben), die zielführende Idee gehabt, die Gruppe $G$ der vier Drehungen um 0 Grad, 90 Grad, 180 Grad und 270 Grad (mit Komposition als Gruppenverknüpfung) auf der Menge $M$ aller Färbungen eines 3x3-Quadrate mit den Farben schwarz und weiß operieren zu lassen.
Die Elemente der Menge $M/G$ entsprechen dann eins zu eins den Färbungen bis auf Drehung.
Gesucht ist also $|M/G|$.
Gemäß zweiter Bahnformel gilt
$|M/G| = [mm] \frac [/mm] {1}{|G|} [mm] \sum_{g\in G} [/mm] {X(g)}$.
Es gilt $|G|=4$.
Bleibt "nur noch" $X(g)$, also die Anzahl der Fixpunkte von g, für jede der vier Drehungen zu bestimmen.
Dazu hat dir Teufel ja schon einen Ansatz genannt.
Wahrscheinlich habe ich dir jetzt nicht viel Neues verraten, aber vielleicht interessiert es ja den ein oder anderen "Mitleser".
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:14 So 16.11.2014 | | Autor: | Teufel |
Hi!
Diese Formel ist auch als Lemma von Burnside bzw. Das Lemma,das nicht von Burnside ist, bekannt. ;)
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 14:31 So 16.11.2014 | | Autor: | Teufel |
Hi!
Ja, also die Fixpunkt für 0° stimmen. Ansonsten kannst du es recht systematisch, z.B. für 180°, so machen:
Du hast hier dein Quadrat wobei die Felder die Farben [mm] $f_1,\ldots, f_9\in\{\text{Schwarz},\text{Weiß}\}$ [/mm] haben, meinetwegen so angeordnet
[mm] f_1\qquad f_2\qquad f_3
[/mm]
[mm] f_4\qquad f_5\qquad f_6
[/mm]
[mm] f_7\qquad f_8\qquad f_9
[/mm]
Drehst du jetzt um 180°, dann erhältst du
[mm] f_9\qquad f_8\qquad f_7
[/mm]
[mm] f_6\qquad f_5\qquad f_4
[/mm]
[mm] f_3\qquad f_2\qquad f_1
[/mm]
Das ist genau dann ein Fixpunkt, also sieht aus wie davor, falls [mm] f_9=f_1,\; f_8=f_2,\; f_7=f_3,\; f_6=f_4,\; f_5=f_5 [/mm] ist. Wie viele Färbungen bleiben also mit diesen Beschränkungen übrig?
Genau so kannst du es auch mit 90° machen.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:55 So 16.11.2014 | | Autor: | Killercat |
Erstmal vielen lieben Dank euch beiden, ich setz mich jetzt mal hin, versuche das zu verstehen und die Aufgabe zu machen.
Liebe Grüße
|
|
|
| |
|
So, ich habe hier mal einen ersten Lösungsvorschlag. Mal schauen ob ich die Idee von Teufel verstanden habe...
Dann wollen wir mal:
Für die Drehung um 0/360° gibt es 512 Fixpunkte.
90°:
1 2 3
4 5 6
7 8 9
wird unter Anwendung der Drehung zu
7 4 1
8 5 2
9 6 3
Das bedeutet: 7=1,4=2,1=3,8=4,5=5,2=6,9=7,6=8,3=9
was sich zusammenfasst zu:
1=3=7=9
2=4=6=8
5=5
Das bedeutet, ich habe für jeden dieser 3 'Komplexe' 2 Möglichkeiten ihn einzufärben, entweder blau oder gelb, damit ich einen Fixpunkt kriege. Das wären dann 2x2x2 = 8 Möglichkeiten.
Für die Drehung um 180°:
9=1
8=2
7=3
4=6
5=5
Analog zu oben wären das [mm]2^5[/mm] Möglichkeiten, also 32
Die Drehung um 270° geht analog zur Drehung um 90° und gibt ebenfalls 8 Fixpunkte.
Das würde dann, auf Basis dieser Rechnungen, zu folgendem Ergebnis führen:
512+16+32 = 560
560/4 = 140
ich bitte um Kontrolle/ Korrektur, falls ich etwas falsch verstanden habe.
Liebe Grüße
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 15:30 So 16.11.2014 | | Autor: | Teufel |
Jop, genau, so würde ich es auch machen! Sieht gut aus.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:33 So 16.11.2014 | | Autor: | Killercat |
Okay, vielen dank :)
|
|
|
|
