Das Skatturnier-Problem

Inhalt

1 Regeln
2 Wünsche
3 Gesucht
4 Zusatzfrage
5 Hinweis
6 Lösungen
6.1 9 Spieler
6.2 10 Spieler
6.3 11 Spieler
6.4 12 Spieler
6.5 13 Spieler

Regeln

Es soll ein Skatturnier unter Berücksichtigung der folgenden Regeln organisiert werden:
1) An jedem Tisch sollen 3 oder 4 Spieler sitzen.
2) Nach jeder Runde soll jeder gegen neue Gegner spielen, so dass keine zwei Spieler öfter als in 1 Runde gegeneinander spielen.
3) "Aussetzen" ist nicht möglich, jeder Spieler spielt in jeder Runde mit.
4) Es sollen 3 Runden gespielt werden.

Wünsche

a) In jeder Runde schreibt der Spieler, der auf Platz 1 eines Tisches sitzt, die Punkte auf. Dieser Spieler soll in den folgenden Runden möglichst nicht wieder mit Aufschreiben drankommen.
b) Wenn die Anzahl der Spieler nicht durch 4 teilbar ist, sind (die weniger beliebten) 3er-Tische ja unvermeidbar.
Die Verteilung auf die Tische soll dann im Verlauf des Turniers so sein, dass alle möglichst gleich oft (und möglichst oft) an einem 4er-Tisch spielen.

Gesucht

Für verschiedene Spielerzahlen sollen Pläne aufgestellt werden aus denen hervorgeht, wie die Teilnehmer in den einzelnen Runden zu platzieren sind.
Es ist nur nötig, Pläne für Turniere mit 9 bis x Spielern aufzustellen: Bei weniger als 9 Spielern stellt sich diese Frage so nicht, da dann nur 1 Runde gespielt werden kann. Und wenn es mehr als x Spieler gibt, lassen sich diese ohne irgendeine Einbuße in voneinander unabhängige kleinere Gruppen aufteilen.
Wie groß ist dieses x?

Zusatzfrage

Wie gesagt werden immer nur 3 Runden gespielt. Von allgemeinem Interesse ist aber sicherlich noch die Frage nach der größten Zahl von Runden, die eine gegebene Anzahl von Teilnehmern unter Befolgung der Regeln 1-3 spielen kann.

Hinweis

Ein verwandtes Problem ist auf Englisch unter dem Namen Social Golfer Problem bekannt. Das ist so, als wenn es hier nur 3er- oder nur 4er-Tische gäbe, und alle Plätze am Tisch gleichwertig wären:
[1] http://www.cs.brown.edu/people/sello/golf.html

D.h. für Anzahlen von Skatspielern, die durch 3 oder 4 teilbar sind, können die Lösungen des Social Golfer Problem verwendet werden, man muss sich allerdings noch um die Platzverteilungen pro Tisch (Wunsch a) kümmern.

Lösungen

Soweit nicht anders vermerkt, erfüllen die vorgestellten Lösungen auch die beiden Wünsche.
Es reicht mir vorerst, für jede Spieleranzahl eine bestmögliche Lösung zu finden. Wenn hier eine solche Lösung vorgestellt wird, heißt das also nicht unbedingt, dass es sich dabei um die einzig mögliche Lösung handelt.

9 Spieler

        | Tisch 1   Tisch 2   Tisch 3
--------+----------------------------
Runde 1 |  1,2,3     4,5,6     7,8,9
Runde 2 |  2,4,9     5,3,7     8,1,6
Runde 3 |  3,4,8     6,2,7     9,1,5

nach [1]

10 Spieler

Nur 1 Runde möglich!

11 Spieler

Nur 1 Runde möglich!

12 Spieler

        | Tisch 1   Tisch 2   Tisch 3   Tisch 4
--------+--------------------------------------
Runde 1 |  3,1, 2    4,5, 6    7,8,9   10,11,12
Runde 2 |  8,1,10   12,2, 4    5,3,9    6, 7,11
Runde 3 |  1,4, 7    2,5,10   11,3,8    9, 6,12

nach [1]

13 Spieler

        |  Tisch 1   Tisch 2   Tisch 3    Tisch 4
--------+----------------------------------------
Runde 1 |  1,2,3, 4   5,6,7     8,9,10   11,12,13
Runde 2 |  6,1,8,13   2,5,9     7,3,12    4,10,11
Runde 3 | 10,2,7,13   3,5,8    12,4, 6    9, 1,11

Wunsch b kann hier nicht gut erfüllt werden:
Da im Verlauf von 3 Runden höchstens 12 Personen an dem 4er-Tisch sitzen können, muss von 13 Spielern sowieso mindestens einer unberücksichtigt beiben. Die Situation ist aber noch ungerechter: Schon in Runde 2 ist es nicht möglich, den 4er-Tisch ausschließlich mit Personen zu besetzen, die zuvor noch nicht dort gesessen haben. Denn es gibt ja nur 3 andere Tische, und von jedem dieser Tische kann nur 1 Spieler an den 4er-Tisch gesetzt werden. Beim Wechsel von Runde 1 zu Runde 2 muss also ein Spieler am 4er-Tisch sitzen bleiben. Ebenso müssen in Runde 3 ein oder mehrere Spieler am 4er-Tisch sitzen, die dort schon gespielt haben.
Die mögliche Optimierung besteht darin, sicherzustellen dass
- kein Spieler in allen 3 Runden am 4er-Tisch sitzt (im obigen Plan realisiert).
- möglichst wenig Spieler 2 mal am 4er-Tisch sitzen (im obigen Plan sind es 3 Spieler, lässt sich die Zahl verringern?).

Wenn Sie Lösungen oder interessante Anregungen zum Skatturnier-Problem haben, schicken Sie diese bitte an

Zuerst veröffentlicht 29.6.2006, zuletzt aktualisiert 4.7.2006 – Impressum