Wettbewerb Sportligaplanung

Worum geht es?

Für eine Sportliga soll ein Spielplan für die Hinrunde einer Saison aufgestellt werden, wobei es T mögliche Spieltage 1,...,T gibt (nicht an jedem Tag müssen Spiele stattfinden). Die Liga besteht aus einer geraden Anzahl von Mannschaften, die mit den Nummern 1,...,n bezeichnet werden. Für jede dieser n Mannschaften sind zwei Mengen gegeben:

• Die Menge H_i enthält alle Termine, an denen Mannschaft i zu Hause spielen kann.
• Die Menge A_i enthält alle Termine, an denen Mannschaft i nicht auswärts spielen kann.

Gesucht ist ein Spielplan für die Saison, der die folgenden Bedingungen erfüllt:

1. Jede Mannschaft soll genau einmal gegen jede andere Mannschaft spielen.
2. Jede Mannschaft spielt höchstens ein Spiel pro Tag.
3. Mannschaften spielen nur an Tagen, an denen sie verfügbar sind.
4. Jede Mannschaft hat höchstens n/2 Heim- und höchstens n/2 Auswärtsspiele.

Ein Plan, der diese vier Bedingungen erfüllt, heißt ein zulässiger Plan.

Die Mannschaften sollen außerdem möglichst abwechselnd Heim- und Auswärtsspiele haben. Spielt eine Mannschaft zweimal hintereinander zu Hause oder zweimal hintereinander auswärts, so sagt man, dass die Mannschaft ein Break hat. Gesucht ist ein zulässiger Plan mit möglichst wenigen Breaks. (Hinweis: Es ist nicht immer möglich, einen zulässigen Plan ohne Breaks zu erstellen).

Die Aufgaben: Für die vier Problemstellungen   Aufgabe 1 Aufgabe 2 Aufgabe 3 Aufgabe 4

Lösungen: Für Interessierte stellen wir (nach Einsendeschluss) an dieser Stelle optimale Lösungen zu den Aufgaben bereit: Lösung zu Aufgabe 1, 10 Breaks Lösung zu Aufgabe 2, 16 Breaks Lösung zu Aufgabe 3, 41 Breaks Lösung zu Aufgabe 4, keine Breaks

sollen zulässige Spielpläne bestimmt werden, die möglichst wenig Breaks haben. Während sich die ersten beiden Probleme als Denksportaufgabe noch per Hand lösen lassen (ähnlich wie ein Sudoku), empfiehlt es sich für die beiden anderen Probleme, die Hilfe eines Computers in Anspruch zu nehmen.

Die Spielpläne können (auch weiterhin) auf der Seite

auf Zulässigkeit überprüft und eingesendet werden (bitte dabei auch kurz angeben, wie die Lösung bestimmt wurde). Die Lösungen müssen dabei das folgende Format besitzen:
Pro Zeile stehen drei Werte heim gast termin mit der Bedeutung, dass die Mannschaften "heim" und "gast" am Spieltag "termin" gegeneinander spielen, wobei Mannschaft "heim" Heimrecht hat. (siehe Beispiel weiter unten).

Teilnahme:

Teilnehmen können alle interessierten Schülerinnen und Schüler aus Osnabrück und Umgebung (einzeln oder in Gruppen mit maximal drei Personen).

Einsendeschluss:

25. November 2008

Bewertung:

Unter allen eingeschickten Lösungen werden alle zulässigen Pläne in die Wertung mit einbezogen. Es müssen nicht alle vier Aufgaben gelöst werden, auch einzelne Lösungen können eingeschickt werden. Gibt es mehr richtige Einsendungen als Preise, erhalten die besten Einsendungen einen Preis.

Preise:

Es gibt verschiedene Sachpreise für die Teilnehmer zu gewinnen, die Schule mit den meisten Teilnehmern bekommt einen Extrapreis. Die Preisverleihung findet am 8. Dezember 2008 um 17 Uhr im Zimeliensaal der Universitätsbibliothek (Alte Münze 14-16, Osnabrück) statt.

Inzwischen gibt es auch

Kontakt:

Juniorprof. Dr. Sigrid Knust
Fachbereich Mathematik/Informatik
Universität Osnabrück
E-Mail

Beispiel:

Ein erster Plan wäre zum Beispiel folgender:

Schauen wir uns als nächstes den folgenden Plan an:

Doch es geht noch besser: