Mathematisches Problem

[Magic-spielbox]

Hallo zusammen!

Folgendes Problem: Von einem 3x3 Felder-Quadrat sollen immer genau 3 Felder gefüllt sein.
Frage: Wie viele verschiedene Möglichkeiten gibt es dafür (Symmetrien bzw. Drehen des Quadrates soll dabei berücksichtigt sein)?

Gut, ich habe das nun für das 3x3 Quadrat für mich schematisch gelöst, aber gibt es dafür eine mathematische Formel?
Und wie sieht es bei einem 4x4 Quadrat aus, wo immer genau 4 Felder gefüllt sind?

Wer kann helfen?

Michael

[Magic-spielbox]

Nur noch mal zur Klarstellung: Es sollen eindeutig verschiedene Möglichkeiten sein. Also wenn man durch Drehen des Quadrats eine bereits vorhandene Konstellation erzielt, darf diese nicht mitgezählt werden.

[Volker L.]

Ich glaube nicht, dass es dafür eine mathematische Formel gibt.

Ohne die Bedingung, dass durch Drehen ineinander überführbare
Kombinationen (also rotationssymmetrische) nur einmal
gezählt werden sollen, wäre der Binomialkoeffizient das,
was Du suchst (3 aus 9 bzw. 4 aus 16, ausgeschrieben
9! /(3!*6!) ), aber ich kann mir nicht vorstellen, dass
es eine Formel gibt, um zu berechnen, wieviele davon
einzigartig sind.

Gruß, Volker

[hgzwopjp]

Volker L. schrieb:
> aber ich kann mir nicht vorstellen, dass
> es eine Formel gibt, um zu berechnen, wieviele davon
> einzigartig sind.

... daß es eine gibt, halte ich für offensichtlich. Wie einfach die dann ist, sei mal dahingestellt...

[MatthiasC]

Mal in die Tonne gedacht:

Ohne Drehen ist die Anzahl 9*8*7 Möglichkeiten.

Beträgt die tatsächliche Anzahl nicht einfach nur 1/4 davon?

[Thygra]

MatthiasC schrieb:
> Beträgt die tatsächliche Anzahl nicht einfach nur 1/4 davon?

Das kann ich mir nicht vorstellen, weil es die symmetrischen Anordnungen gar nicht 4 Mal gibt, sondern sowieso nur 1 Mal. Nur die unsymmetrischen Anordnungen gibt es 4 Mal.

[hgzwopjp]

Erstens, weil manche Möglichkeiten eben schon symmetrisch sind und dann nicht gezählt würden, und dann gibt es noch Spiegelsymmetrie.
Abgesehen davon sind es ohne Drehen nicht 9*8*7, sondern 9 über 3, also ein Sechstel davon.

[Volker L.]

MatthiasC schrieb:
>
> Mal in die Tonne gedacht:
>
> Ohne Drehen ist die Anzahl 9*8*7 Möglichkeiten.
>
> Beträgt die tatsächliche Anzahl nicht einfach nur 1/4 davon?

Nein, weil einige Kombinationen im Fall der Rotation 4mal
vorkommen, andere aber nur 2mal (die, die in sich schon
punktsymmetrisch sind).

Beispiel:
Nummerieren wir die Felder durch wie auf dem Zahlenblock
der Tastatur. 3 in gerader Reihe am Rand gibt es 4mal:
7-8-9, 9-6-3, 3-2-1, 1-4-7, die alle rotationssymmetrisch
sind, nach Magics Forderung also nur als 1 Kombination
zählen.
3 in gerader Reihe in der Mitte kommt aber nur 2mal vor:
4-5-6 und 8-5-2.

[Magic-spielbox]

Vielen Dank an alle, die sich hier beteiligt haben. Ich denke, ich kenne nun die Lösung. Einen mathematischen Beweis kann ich allerdings nicht liefern.
Matthias Ansatz ist eigentlich der richtige, es fehlte nur die korrekte Berechnung der Möglichkeiten, nämlich 3aus9 sind: (9x8x7)/(3x2x1) = 84
Davon ein Viertel sind 21, was in der Tat die Lösung ist.

Letztlich erscheint es logisch, denn aufgrund der Symmetrien gibt es jede Situation viermal, dies trifft auch auf die Mittelreihen zu.
Wenn man sich Himmelsrichtungen an dem Quadrat vorstellt (N, O, S, W), so kann man das Quadrat in vier Positionen auf Nord drehen und in jeder Ausrichtung einmal die gesamten Möglichkeiten eintragen. Letztlich ist ein 3x3 Quadrat nichts anderes als eine 9er-Reihe in 3 Zeilen untereinander geschrieben. Also muss man in der Tat die Möglichkeiten einer 9er-Reihe durch 4 teilen.

Michael

[yzemaze]

Volker L. schrieb:
> 3 in gerader Reihe in der Mitte kommt aber nur 2mal vor:
> 4-5-6 und 8-5-2.
Bei der Berechnung des Binominalkoeffizienten bleiben Symmetrien aber außen vor. Daher solltest du auch 6-5-4 und 2-5-8 nicht vergessen.
=> 9!/(3!*6!)/4

Ob für Kantenlänge n > 2 allgemein n²!/(n!*(n²-n)!)/4 gilt, wäre dann halt noch zu beweisen ;)

[Thygra]

Magic schrieb:
> Letztlich erscheint es logisch, denn aufgrund der Symmetrien
> gibt es jede Situation viermal, dies trifft auch auf die
> Mittelreihen zu.

Das kann ich noch nicht so ganz glauben. Denn zum Beispiel die Situation, in der alles außer den 4 Ecken besetzt ist, gibt es nur einmal. Und die Situation, in der alles bis auf 2 gegenüberliegende Ecken besetzt ist, gibt es zweimal.

Deshalb kann "durch 4 teilen" einfach nicht stimmen.

[peer]

Hi,
Thygra schrieb:
>
> Magic schrieb:
> > Letztlich erscheint es logisch, denn aufgrund der Symmetrien
> > gibt es jede Situation viermal, dies trifft auch auf die
> > Mittelreihen zu.
>
> Das kann ich noch nicht so ganz glauben. Denn zum Beispiel
> die Situation, in der alles außer den 4 Ecken besetzt ist,
> gibt es nur einmal. Und die Situation, in der alles bis auf 2
> gegenüberliegende Ecken besetzt ist, gibt es zweimal.
>
> Deshalb kann "durch 4 teilen" einfach nicht stimmen.

Aber in deinem Beispiel sind mehr als 3 Felder besetzt. Magic hat gefordert, dass immer genau drei Felder besetzt sein müssen.

ciao
peer

[Thygra]

peer schrieb:
> Aber in deinem Beispiel sind mehr als 3 Felder besetzt. Magic
> hat gefordert, dass immer genau drei Felder besetzt sein
> müssen.

Okay, das hatte ich verdrängt. Aber es ändert nichts. Dann nimm halt eine Diagonale von 3 Feldern. Die gibt es nur zweimal, nicht viermal. Oder nimm bei 4 x 4 Feldern nur die 4 Eckfelder, die gibt es nur einmal.

Das Problem bleibt also, die Rechnung kann so nicht stimmen (bis mich jemand vom Gegenteil überzeugt).

[Peter Nos]

Hallo zusammen,

ich glaube nicht, dass es einen einfachen geschlossenen Ausdruck gibt. Die einzelnen Konfigurationen haben halt unterschiedliche Symmetrieeigenschaften: 2,4 oder 8.

Das Schöne an der Frage ist aber ihre Beschränktheit auf 3x3 Matrizen. Alle Lösungen lassen sich einfach abzählen. Jeder Ansatz ist damit einfach überprüfbar.

Ohne Berücksichtigung der Symmetrie sind es wie schon angemerkt 9 über 3 = 9!/(3!*6!) = 9*8*7/6 = 84 Lösungen. Leicht lässt sich eine Reihe Matrizen zusammen mit ihren symmetrischen Vielfachen (bzgl Spiegelung & Rotation) hinschreiben.

Ich kam auf 16 elementar unterschiedlichen Lösungen:
2 mit 2er Symmetrie -> 4 Möglichkeiten
8 mit 4er Symmetrie -> 32 Möglichkeiten
6 mit 8er Symmetrie -> 48 Möglichkeiten
Das wären dann 84 ohne Berücksichtigung der Symmetrie, qed.

Da 84/16=5,25 ergibt, vermute ich, dass es keine wirklich elegante wie einfache Lösung gibt.

viele Grüße,
p.

p.s:
Hier kommen sie noch, die Möglichkeiten:

111 110 110 110 110 110 110
000 100 010 001 000 000 000
000 000 000 000 100 010 001
(4) (4) (8) (8) (8) (8) (8)

101 101 101
010 000 000
000 100 010
(4) (4) (4)

100 100
011 010
000 001
(8) (2)

100
001
010
(4)

010 010
110 101
000 000
(4) (4)

010
010
010
(2)

[peer]

Hi,
hgzwopjp schrieb:
>
> Volker L. schrieb:
> > aber ich kann mir nicht vorstellen, dass
> > es eine Formel gibt, um zu berechnen, wieviele davon
> > einzigartig sind.
>
> ... daß es eine gibt, halte ich für offensichtlich. Wie
> einfach die dann ist, sei mal dahingestellt...

Nicht unbedingt. Es gibt z.B. keine (bekannte) Formel wie viele nichtsymmetrische magische nxn Quadrate es für beliebige n gibt. Diese Fragestellung ist zumindest verwandt.

ciao
peer

[raccoon]

Hallo Michael,

um dich wenigstens auf die richtige Spur zu bringen, liefere ich dir ein paar Stichworte - inhaltlich ist das Thema etwas zu lange her, sodass ich es mangels Zeit gerade nicht ausarbeiten könnte.

Dein Thema gehört zur Kombinatorik und nennt sich Permutation ( http://de.wikipedia.org/wiki/Permutation#Weitere_Darstellungen ). In deinem konkreten Fall ist es eine Permutationsmatrix.
Wirf mal einen Blick hierauf und schau, ob du damit klarkommst. Ansonsten liest bestimmt Heinrich mit und reibt sich gerade die Finger ;) :

http://de.wikipedia.org/wiki/Permutationsmatrix#Eigenschaften


Beispiel fuer eine 2x2-Matrix ergibt zunächst 6 Permutationen, von denen aber nur 2 nicht-identisch sind (Thygras Vermutung, dass man nicht einfach durchzählen und etwa durch 3 oder 4 teilen kann, ist also korrekt):

11 A
00

10 A
10

10 B
01

01 B
10

01 A
01

00 A
11

Wenn du deine Lösung verifizieren konntest, schreib doch nochmal, würde mich auch interessieren.

Gruß

raccoon

[Axel H.]

Hallo,

wenn der Ansatz der 9-Felder-Reihe gewählt wird und es "9 über 3" Möglichkeiten gibt, drei Felder davon zu besetzen, gibt das die bekannten 84 Möglichkeiten. Das Teilen durch 4 aufgrund der 4 Betrachtungsmöglichkeiten eines 3x3-Feldes schließt m.E. genau wie gewünscht die Punktsymmetrie aus. Allerdings gibt es vier Möglichkeiten, die davon ausgeschlossen werden müssten, nämlich die Besetzungen der beiden Mittelreihen sowie die Diagonalen. Diese sind neben ihrer Punktsymmetrie auch noch an einer Achse spiegelsymmetrisch. Für die restlichen sollte die normale Punktsymmetrie gelten, so dass man die vier Sonderfälle vorher abzieht und hinterher wieder draufaddiert, es also

(84-4)/4 + 4 = 24 Möglichkeiten gibt.

Auch das aber ohne Gewähr!

Für das 4x4-Quadrat mit immer vier Steinen könnte es damit einfacher sein. Denn da gibt es aufgrund des fehlenden Mittelpunktfeldes keine Spielgelsymmetrie, die ausgeschlossen werden müsste. Demnach käme man da auf 16!/(4!*12!) / 4 = 455 Möglichkeiten.

viele Grüße
Axel

[Axel H.]

Und dann doch falsch zuende gedacht...
Hinterher dürfen natürlich nur 2 statt vier draufgezählt werden, weil je zwei ja wieder punktsymmetrische sind, also:

(84-4)/4 + 2 = 22 unterschiedliche Lösungen.

Für das von raccoon aufgeführte 2x2-Problem ergibt sich analog:

(6-2) / 4 + 1 = 2 Lösungen

Das wiederum bedeutet, dass bei dem 4x4-Quadrat auch noch einige Kombinationen vorher rausgerechnet werden müssen. Und zwar alle, deren eine "Hälfte" nach 180°-Drehung um den Mittelpunkt identisch mit der zweiten "Hälfte" ist (u.a. die Diagonalen). Da ich kein Mathematiker bin, weiß ich nicht, wie man das fachgerecht bezeichnet.

viele Grüße
Axel

[Thygra]

Axel H. schrieb:
> Das wiederum bedeutet, dass bei dem 4x4-Quadrat auch noch
> einige Kombinationen vorher rausgerechnet werden müssen. Und
> zwar alle, deren eine "Hälfte" nach 180°-Drehung um den
> Mittelpunkt identisch mit der zweiten "Hälfte" ist (u.a. die
> Diagonalen).

So einfach ist es nicht. Es gibt auch welche, die nach 90° Drehung identisch sind. (Die 4 Ecken bzw. die 4 Mittelfelder.)

[Axel H.]

Beide genannten gehören zu den von mir beschriebenen dazu (Wenn man das 4-Ecken-Bild um 180° dreht, kommen die gefüllten Felder genau übereinander. Mit den Mittelfeldern genauso). Man muss beim Draufaddieren dieser ausgenommenen Lösungen nur schauen, wieviele unterschiedliche Bilder man unter Berücksichtigeung der Drehungen erhält, damit man nicht (wie ich im ersten Versuch) zu viele drauf addiert.

viele Grüße
Axel