Kombinatorisches Problem: Spielplan

02/03/2009 - 15:39 von Florian Severin | Report spam
Hallo Newsgroup,

für ein Brettspiel-Turnier hat ein Freund mich beauftragt, einen
Spielplan zu erstellen.
Es kann zwischen 16 und 48 Teilnehmer geben,
gespielt werden vier verschiedene Spiele in vier Runden.

Dabei sollen einige Regeln beachtet werden, ich zitiere einfach mal:



1. Jeder Teilnehmer muss jedes Spiel genau einmal spielen.

2. Jedes Spiel wird mit 4 Teilnehmern gespielt. Ist die Teilnehmerzahl nicht durch 4 teilbar, müssen einige Spiele mit drei Teilnehmern gespielt werden.

3. Kein Teilnehmer darf dabei mit einem anderen Teilnehmer zweimal spielen (Ausnahme bei 16 Teilnehmern, da gehts nicht anders)

4. Jeder Teilnehmer bekommt in jedem Spiel eine Startposition von 1-4

5. Jeder Teilnehmer muss jede Startposition (1., 2.,3.,4.) genau einmal haben

6. Was ich jetzt will ist ein Programm das jedem Teilnehmer einen Spielplan gibt, also eine Übersicht in welcher Runde er welches Spiel mit welcher Startposition zockt. Die Ausgabe wàre dabei egal, zur Not schreibe ich das jedem einzeln auf.




Zur Not können die Startpositionen auch unberücksichtigt gelassen
werden, die Spieler würden dann jedes Mal die Positionen unter sich
auslosen.

Die 3. Bedingung kann, glaube ich, auch für mehr als 16 Teilnehmer nicht
immer garantiert werden. Irgendeine Grenze muss es aber geben, wohl auch
unter 48.

Ich habe bereits ein Skript geschrieben, was per Brute-Force sehr viele
Möglichkeiten ausprobiert; einige sind dabei auch schon a
priori ausgeschlossen, dennoch habe ich einen enormen Anstieg der
Laufzeit, da auch nach 24 Stunden noch kein Ergebnis für 16 bzw 18
Teilnehmer zu sehen war (Nichtmal, dass es nicht geht. Also das Skript
lief gar nicht erst zu Ende.), hat es gar keinen Sinn, es für höhere
Zahlen laufen zu lassen.


Auch kombinatorisch bin ich das ganze schon angegangen, auf
verschiedenen Wegen, bin jedoch nie zum Erfolg gekommen.

Hat jemand von euch vielleicht spontan eine Idee dazu oder kennt jemand
Sàtze der Kombinatorik, die das ganze Gesuche stark genug eingrenzen
könnten?
Bin sehr dankbar für jegliche Hilfe,

Florian
 

Lesen sie die antworten

#1 Jens Voß
02/03/2009 - 21:14 | Warnen spam
On 2 Mrz., 15:39, Florian Severin
wrote:

Es kann zwischen 16 und 48 Teilnehmer geben,
gespielt werden vier verschiedene Spiele in vier Runden.

> 1. Jeder Teilnehmer muss jedes Spiel genau einmal spielen.
> 2. Jedes Spiel wird mit 4 Teilnehmern gespielt. Ist die
> Teilnehmerzahl nicht durch 4 teilbar, müssen einige Spiele mit
> drei Teilnehmern gespielt werden.
> 3. Kein Teilnehmer darf dabei mit einem anderen Teilnehmer zweimal
> spielen (Ausnahme bei 16 Teilnehmern, da gehts nicht anders)



Hà, wieso denn nicht? Wenn wir 16 Leute sind, spiele ich in jeder
Runde mit drei anderen zusammen, d.h. wenn alles glatt làuft, habe
ich erst nach 5 Runden mit allen 3 x 5 = 15 anderen gespielt.
Nàheres siehe unten.

> 4. Jeder Teilnehmer bekommt in jedem Spiel eine Startposition von
> 1-4
> 5. Jeder Teilnehmer muss jede Startposition (1., 2.,3.,4.) genau
> einmal haben
> 6. Was ich jetzt will ist ein Programm das jedem Teilnehmer einen
> Spielplan gibt, also eine Übersicht in welcher Runde er welches
> Spiel mit welcher Startposition zockt. Die Ausgabe wàre dabei
> egal, zur Not schreibe ich das jedem einzeln auf.



Was die Verteilung mit 20, 24, 28, ... Spielern angeht, weiß ich so
aus dem Bauch heraus auch erst mal nicht weiter, aber die Situation
mit 16 Spielern ist denkbar simpel: Betrachte die affine Ebene über
dem Körper mit 4 Elementen. Die 16 Punkte werden durchnummeriert,
und die Parallelenscharen bestimmen die Teamzusammensetzungen in
den einzelnen Runden:

1. Runde: {1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}, {13, 14, 15,
16}
2. Runde: {6, 11, 16, 1}, {2, 7, 12, 13}, {14, 3, 8, 9}, {10, 15, 4,
5}
3. Runde: {15, 8, 1, 10}, {7, 16, 9, 2}, {3, 12, 5, 14}, {11, 4, 13,
6}
4. Runde: {12, 1, 14, 7}, {16, 5, 2, 11}, {8, 13, 10, 3}, {4, 9, 6,
15}

Die Startposition ergibt sich jeweils aus der Position in der Menge,
d.h. Spieler 11 bekommt z.B. in Runde 1 die Position 3, danach die 2,
dann die 1 und schließlich die 4.

Zur Not können die Startpositionen auch unberücksichtigt gelassen
werden, die Spieler würden dann jedes Mal die Positionen unter sich
auslosen.



In diesem Fall kann man mit 16 Spielern sogar 5 Runden spielen:

5. Runde: {1, 5, 9, 13}, {2, 6, 10, 14}, {3, 7, 11, 15}, {4, 8, 12,
16}

(kein Wunder, schließlich gibt es in der affinen Ebene der Ordnung 4
ja genau Parallelscharen)

Für die "krummeren" Zahlen gibt es bestimmt auch irgendwelche Rezepte;
nur mir fallen so spontan wie gesagt keine ein.

Herzliche Grüße,
Jens

Ähnliche fragen