Mathematische Lösung gesucht

Zvoni

Erfahrenes Mitglied
hmm, das Problem müsste aber auflösbar sein.
Wenn ich mich an meinen Mathe-Unterricht noch richtig erinner, ist alleine die Zuteilung der Menschen eine "Kombination ohne Wiederholung" analog dem Lotto-Problem.

In der Urne sind Bälle von 1 bis 8, und ich ziehe immer nur 2 Bälle ohne Zurücklegen und ohne beachten der Reihenfolge (Beispiel [1,6] = [6,1])

Daraus ergibt sich für n=8 und k=2 nach der Formel:
n! / ((n-k)!*k!)
8! / ((8-2)!*2!) = 28 verschiedene Kombinationen unsere 8 Personen miteinander zu kombinieren.

Aber wie ich jetzt die 4 Termine und 4 Orte da reinbekomme bin ich mir auch nicht sicher.
Irgendwie denke ich dauernd es gibt 16 Kombinationen hierfür, was impliziert, dass ich 28 Paarungen da eigentlich unterbringen können müsste.
 

HonniCilest

Erfahrenes Mitglied
*eek* Das Problem ist lösbar wo auch immer bei den Erklärungsversuchen oben das Problem liegt ^^

Ich bin nun so vorgegangen:
- Ich habe mir ein Satz Zahlenpaare zusammengesucht, wo jede Zahl 4x vorkommt. Mein ergebnis waren die Zahlenpaare mit einer geraden und einer ungeraden Zahl.
- Die Paare mit der 1 habe ich einfach diagonal in das Gitter geschrieben.
- Für die Paare mit der 2 habe ich dann auch einfach eine Position angenommen unter den genannten Bedingungen.
- Für die übrigen Paare mit der 3 verblieb dannn nur noch eine Variante. Analog sah es dann auch mit den restlichen Paaren aus.

Wie dem auch sei ist meine 1 mögliche Lösung nun folgende:
12 56 78 34
58 14 23 67
47 38 16 25
36 27 45 18
 
Zuletzt bearbeitet:

lunivo

Grünschnabel
Sehr beeindruckend! Damit ist meine Frage beantwortet, vielen Dank!

Jetzt habe ich mich jedoch so lange schon damit beschäftigt, dass ich nicht drum herum komme noch einmal nachzuhaken, wie du auf diese Lösung gekommen bist. Bei deiner Erklärung bin ich schon beim zweiten Punkt ausgestiegen. Hast du herumprobiert oder konntest du das wissenschaftlich angehen? Wenn ja - lässt sich das in einem Algorithmus abbilden?

Vielen Dank nochmal für deine Denkarbeit!
 

HonniCilest

Erfahrenes Mitglied
Für Punkt 1 hatte ich eine kleine Pyramide in Excel mit möglichen Kombinationen. Jede Spalte hatte einen Eintrag weniger. Ich hatte dann festgestellt, dass jede Zahl 4x vorkommt, wenn ich von dieser Pyramide jede 2. Zeile rausschmeiße. Die verbliebenen Zahlen waren dann diese gerade-ungerade Kombinationen. Dass eine Zahl dann schräg muss wahr mir ziemlich klar. Darum waren die 4 Kombinationen mit der 1 gleich eingetragen. Dann habe ich auch erstmal dagesessen und überlegt wie gehe ich mit den übrigen Zahlen vor, die Kombinationen mit der 2 waren daher eher "mutig". Da die 2 aber schon in Spalte/Zeile 1 war, blieb nur noch ein 3x3 Quadrat. Dann habe ich mir die 3 restlichen 3er-Kombinationen gemeinsam angeschaut. Insgesamt konnten diese an 5 Positionen, aber nur eine Variante konnte man so einbauen, dass sich diese nicht gegenseitig behindern. Drum ist die andere Diagonale entstanden. In Zeile 4 war danach noch eins leer, ich war damit klar welche Kombination hinmuss - die 45 - und welch Zufall die hatte ich auch noch übrig. Das restliche Quadrat hat sich dann genauso gefüllt. Mathematisch belegen kann ich meine Vorgehensweise nicht! Aber für weitere Überlegungen: Die 1er und 3er Reihen sind bei mir antidiagonal, ich weiß nicht ob das Zufall ist oder einen höheren Sinn hat ;-)
 
Zuletzt bearbeitet:

lunivo

Grünschnabel
Unglaublich! Vielen Dank! Ich werde schauen, ob ich dieses Problem mit einem Algorithmus lösen kann. Mich würde brennend interessieren, ob es andere Kombinationen geben kann.

Wenn ich mehr weiß, poste ich das hier.

Falls einer vor mir drauf kommen sollte, würde ich mich natürlich freuen, das hier zu lesen.

Danke für eure Mühen!
 

HonniCilest

Erfahrenes Mitglied
Unglaublich! Vielen Dank! Ich werde schauen, ob ich dieses Problem mit einem Algorithmus lösen kann. Mich würde brennend interessieren, ob es andere Kombinationen geben kann.

Natürlich du kannst die Zahlen als Zeichen beliebig tauschen immerhin könnte da genauso abcdefgh stehen, genauso kannst du Spalten und Zeilen beliebig mixen. Die Frage ist nur ob man eine "Standardlösung" mit einer (mathematischen) Methode zusammenbasteln kann, die vielleicht auch für größere Quadrate gültig ist.
 
Zuletzt bearbeitet:

Zvoni

Erfahrenes Mitglied
Die Frage ist nur ob man eine "Standardlösung" mit einer (mathematischen) Methode zusammenbasteln kann, die vielleicht auch für größere Quadrate gültig ist.

Yepp, und da seh ich eher das Problem: Was sind die Rahmenbedingungen, die überhaupt erfüllt sein müssen, damit es eine Lösung gibt? Gibt es einen math. Beweis dafür, woraus sich ein Algorhytmus ableiten lassen kann?
Mit Rahmenbedingungen meine ich: Bei einem gegebenen Quadrat brauche ich wieviele Personen, damit es überhaupt eine Lösung gibt? Oder umgekehrt:Was ist das grösstmögliche Quadrat, für welches es für eine gegebene Anzahl Personen min. eine Lösung gibt?
 

Zvoni

Erfahrenes Mitglied
hmm, ich glaube ich habe die offizielle Bezeichnung für das vom OP beschriebene Problem gefunden:
Eulersche Quadrate
http://geb.uni-giessen.de/geb/volltexte/2008/5969/pdf/SdF_1986-4_22-23.pdf

Im angehängten Link wird vom Franzosen J. Ozanam berichtet wie dieser Bube, Dame, König, AS in allen 4 Farben gemäss den genannten Forderungen in einem Quadrat angeordnet hat.

Jetzt heissts: Wer findet einen Algorithmus? ^^

Hier noch ein interessanter Link: http://en.wikipedia.org/wiki/Graeco-Latin_square
Dort steht, dass ein griechisch-lateinisches Quadrat (=eulersches Quadrat) in zwei zu einander orthogonale lateinische Quadrate zerlegt werden kann.
Vielleicht als Ansatz ^^
 
Zuletzt bearbeitet:

HonniCilest

Erfahrenes Mitglied
Letztendlich hatte ich ja auch schon den Ansatz mit meiner gerade-ungerade Aussage gehabt. Ich dachte mir da schon, dass man im Prinzip 2 Eigenschaften benötigt, sei es eine ungerade "Eigenschaft" und eine gerade "Eigenschaft" oder eben die Wertigkeit und die Farbe einer Spielkarte.

Mit den Links kann ich nun nachvollziehen wie ich mit den gegebenen lateinischen Quadraten (Zahlen werden jeweils "Eigenschaften" zugeordnet) zu den Lösungen komme. Das habe ich manuell an 5x5 (also 10 Personen) ausprobiert und könnte es auf diese Weise auch mit Code nachstellen. (Eine) Lösung hier:

01 29 47 56 38
58 03 12 49 67
69 78 05 23 14
34 16 89 07 25
27 45 36 18 09


Was ich aber nicht verstehe: Wie generiert man sich ein lateinisches Quadrat beliebiger Ordnung? Das ist mein Hauptproblem nun ^^
Edit: Ich bin nun der Meinung, dass ich jedes lateinische Quadrat erstellen könnte unter der Voraussetzung, ich kenne das lateinische Quadrat jedes Faktors. Im Zuge der Primfaktorzerlegung müsste ich also jedes lateinische Quadrat jedes Primfaktors kennen. Für 9 sähe das latenische Quadrat dann so aus:
1 2 3 4 5 6 7 8 9
2 3 1 5 6 4 8 9 7
3 1 2 6 4 5 9 7 8
5 6 4 7 8 9 1 2 3
6 4 5 8 9 7 2 3 1
3 3 3 9 7 8 3 1 2
7 8 9 1 2 3 4 5 6
8 9 7 2 3 1 5 6 4
9 7 8 3 1 2 6 4 5

Aber wie generiere ich das lateinische Quadrat einer Primzahl? Das verstehe ich (noch) nicht! ^^ Beispiel: Keine Ahnung wie das von 7 aussieht :p

Edit2: Obwohl Für alle primzahlen gilt die Verknüpfungstafel oder? *grübel* Dann müsste ich (glaube ich) eine Lösung für n mit einem Programm genieren können.

PS.: Eigentlich eine schöne Aufgabe für das Coding Quiz meiner Meinung nach :p
 
Zuletzt bearbeitet:

Zvoni

Erfahrenes Mitglied
PS.: Eigentlich eine schöne Aufgabe für das Coding Quiz meiner Meinung nach :p

Au weia! Da hab ich ja jetzt was angestellt *lol*

Edit: honni, du hast gesehen, dass in zeile 6 deines 9-er quadrats, 4 x die 3 vorkommt? Sowie auch diverse andere wiederholungen in den spalten?

Edit 2: ich glaube zeile 6 muss so lauten:
4 5 6 9 7 8 3 1 2
 
Zuletzt bearbeitet: