Anzahl Möglichkeiten -Rotation < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 02:14 Mo 15.02.2016 | | Autor: | mmfbn |
Hi,
man hat ein Quadrat mit je einer bestimmten Anzahl von Feldern auf jeder Seite. Zum Beispiel mit drei:
[mm] \vmat{\bigcirc & \bigcirc & \bigcirc \\\bigcirc & & \bigcirc \\\bigcirc & \bigcirc & \bigcirc}
[/mm]
Nun will man eine bestimmte Anzahl dieser Felder ankreuzen. Zum Beispiel zwei:
[mm] \vmat{\bigcirc & \otimes& \otimes \\\bigcirc & & \bigcirc \\\bigcirc & \bigcirc & \bigcirc}
[/mm]
Gesucht ist nun die Anzahl der möglichen "Ankreuzmuster", die sich gegenseitig nicht durch Rotationen (90°,180°,270°(, 360°)) und/oder Spiegelungen (Horizontal, Vertikal, Diagonal) aufeinander abbilden lassen.
zum Beispiel geht nun nicht mehr:
[mm] \vmat{\bigcirc & \bigcirc & \otimes \\\bigcirc & & \otimes \\\bigcirc & \bigcirc & \bigcirc}
[/mm]
Da man dieses erhält wenn man das obere an der Diagonale spiegelt.
Mit 2 Kreuzen gibt es bei einem Quadrat mit 3 Feldern an jeder Seite insgesammt 6 "Ankreuzmuster":
[mm] \vmat{\otimes & \otimes & \bigcirc \\\bigcirc & & \bigcirc \\\bigcirc & \bigcirc & \bigcirc}\vmat{\otimes & \bigcirc & \otimes \\\bigcirc & & \bigcirc \\\bigcirc & \bigcirc & \bigcirc}\vmat{\otimes & \bigcirc & \bigcirc \\\bigcirc & & \otimes \\\bigcirc & \bigcirc & \bigcirc}\vmat{\otimes & \bigcirc & \bigcirc \\\bigcirc & & \bigcirc \\\bigcirc & \bigcirc & \otimes }\vmat{\bigcirc & \otimes & \bigcirc \\\bigcirc & & \otimes \\\bigcirc & \bigcirc & \bigcirc }\vmat{\bigcirc & \otimes & \bigcirc \\\bigcirc & & \bigcirc \\\bigcirc & \otimes & \bigcirc }
[/mm]
Bei einem Kreuz sind es 2 und bei 3 Kreuzen glaube ich 10. Bei 0 und 8 gibts nur eine Möglichkeit und bei 7,6,5 ist es wie bei 1,2,3.
Speziell gesucht ist nun die Anzahl bei 4 Kreuzen. Schön zu wissen wäre auch noch wieviel es sind, wenn das Quadrat mehr als 3 Felder pro Seite hat. Die Ergebnisse oben waren mehr oder weniger ausgezählt. Das kann man bei mehr Feldern nur noch schlecht machen.
Gesucht ist eine möglichst allgemeine Lösung.
Bin nicht sicher, in welches Fachgebiet der Mathematik es genau fällt. Hoffe es passt in etwa hier rein.
-----------
Unter anderem bisher dazu überlegt:
Man kann es immer so rotieren/spieglen, dass ein Kreuz auf dem ersten Feld und/oder dem zweite liegt (außer bei 0 Kreuzen). Dann muss man nur noch die Kombinationen von einem Kreuz weniger durchprobieren.
Man könnte jedem "Ankreuzmuster" eine Zahl zuordnen (binär zu decimal), die kleinst mögliche, die durch rotation/spiegeln möglich ist. Dann zählt man die unterschiedlichen Zahlen.
Beides ist aber eher fürs auszählen gedacht, rechnen wäre gut.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 11:16 Mo 15.02.2016 | | Autor: | Teufel |
Hi!
Das Thema passt hier gut hin. :)
Kennst du das ![[]](/images/popup.gif) Lemma von Burnside (bzw Cauchy)? Damit kann man Sachen zählen, die invariant unter Gruppenoperationen bleiben (z.B. Rotationen und Spiegelungen in deine Fall).
Für $n=3$ und 2 Kreuze in deinem Fall:
$G$ = Gruppe der Drehungen und Spiegelungen (Anmerkung: du brauchst nur eine Spiegelung, z.B. horizontal, weil man die vertikale auch durch die horizontale + Rotation simulieren kann)
$X$ = Menge der verschiedenen Ankreuzmuster ohne die Drehungen/Spiegelungen zu beachten [mm] ($\left|X\right|=\vektor{8 \\ 2}$)
[/mm]
$|X/G|$ = Anzahl der verschiedenen Orbits von $X$ unter $G$ = Zahl, die du suchst
[mm] $X^g$ [/mm] = Anzahl der verschiedenen Ankreuzmuster, die unter der Gruppenoperation $g$ gleich bleiben, z.B. alle Ankreuzmuster, die unter einer 90°-Rotation in sich selbst übergehen.
Eingesetzt:
$|G|=8$ (4 Rotationen + 4 Rotationen mit Spiegelung)
Jetzt muss man noch [mm] $|X^g|$ [/mm] für alle [mm] $g\in [/mm] G$ bestimmen. Nehmen wir mal $g=0°=360°$, also wenn man nichts dreht oder spiegelt. Da bleibt natürlich jedes Ankreuzmuster so, wie es ist, jedes der $|X|$ geht in sich selbst über.
90°: Nichts bleibt, wie es ist.
180°: 4 Muster bleiben gleich (welche?)
270°: Nichts.
Spiegelung + 0°: 4
Spiegelung + 90°: 4
Spiegelung + 180°: 4
Spiegelung + 270°: 4
Nach Formel gilt [mm] $|X/G|=\frac{1}{|G|}\sum\limits_{g\in G}|X^g|=\frac{1}{8}(\vektor{8 \\ 2}+0+4+0+4+4+4+4)=\frac{48}{8}=6.
[/mm]
Das kannst du auch verallgemeinern, aber du kannst es ja erstmal für n=2 und 1 oder 2 Kreuze üben. Dann kannst du dich mal an 4 wagen. Es ist natürlich trotzdem anstrengend zu schauen, dass man wirklich alle Muster findet, die unter irgendwelchen Operationen gleich bleiben, aber besser als alles durchzuprobieren ist es allemal, besonders wenn $n$ wächst.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:08 Mo 15.02.2016 | | Autor: | mmfbn |
Hallo Teufel,
danke für die Antwort. Von dem Lemma habe ich noch nichts gehört (leider viel zu wenig Mathe gehabt) aber das passt ja perfekt. Hätte nicht gedacht, dass es für genau dieses Problem einen Lösungweg gibt.
Ich habe mal mit 4 Kreuzen durchprobiert. (mit horizontaler Spiegelung)
bei 0° bilden [mm] \vektor{8 \\ 4} [/mm] Möglichkeiten auf sich ab
bei 90°: 2
bei 180°: 6
bei 270°: 2
Spiegelung + 0°: 6
Spiegelung + 90°: 6
Spiegelung + 180°: 6
Spiegelung + 270°: 6
[mm] $|X/G|=\frac{1}{|G|}\sum\limits_{g\in G}|X^g|=\frac{70+34}{8}=13
[/mm]
Ich habe auch mal ein Programm geschrieben, welches jeder Konfiguration die kleinst mögliche Zahl zuordnet, die es durch Drehungen und/oder Spiegelungen erreichen kann. Da kommt auch 13 raus.
Der Lösungsweg mit dem Lemma ist aber mathematisch schöner :), jedoch kommt man bei beiden Lösungswegen nicht so einfach um auszählen drum rum.
|
|
|
|
