Tennis-Mixed-Turnier < Kombinatorik < Stochastik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Bei einem Mixed-Tennisturnier sind sechs Frauen und sechs Männer am Start. Die Männer erhalten die Startnummern M1-M6, die Frauen F1-F6. Drei Tennisplätze stehen zur Verfügung.
In jedem Spiel stehen sich jeweils eine Frau und ein Mann einem anderen gemischten Paar gegenüber. Gespielt werden 5 Runden (also 15 Matches), so daß jeder Teilnehmer 5 Matches bestreitet. |
Aufgabe:
Austellung eines Spielplans unter folgenden Bedingungen:
a1) Jeder Mann soll in jedem Match einen anderen männlichen Gegner haben. Damit hat jeder Mann gegen jeden anderen Mann genau einmal gespielt.
a2) Jede Frau soll in jedem Match einen anderen weiblichen Gegner haben. Damit hat jede Frau gegen jede andere Frau genau einmal gespielt.
b1) Jeder Mann soll in jedem Match eine andere Partnerin haben. Damit hat jeder Mann mit jeder Frau bis auf eine (fünf Runden, sechs Frauen) gespielt.
b2) Jede Frau soll in jedem Match einen anderen Partner haben. Damit hat jede Frau mit jedem Mann bis auf einen (fünf Runden, sechs Männer) gespielt.
c1) Jeder Mann soll in jedem Match einen anderen weibliche Gegner haben. Damit hat jeder Mann gegen jede Frau bis auf eine (fünf Runden, sechs Frauen) gespielt.
c2) Jede Frau soll in jedem Match einen anderen männlichen Gegner haben. Damit hat jede Frau gegen jeden Mann bis auf einen (fünf Runden, sechs Männer) gespielt.
========
Kurz zusammengefaßt: In jedem Match hat ein Teilnehmer einen neuen Partner, einen neuen Gegner und eine neue Gegnerin.
========
Gibt es überhaupt eine Lösung? Wie könnte ein Algorithmus aussehen? Ich habe leider nur einen Ansatz, der keine richtige Lösung liefert.
Falscher Lösungsversuch:
M1 bleibt auf seiner Position, die anderen Männer drehen sich nach jeder Runde gegen den Uhrzeigersinn.
F6 bleibt auf ihrer Position, die anderen Frauen drehen sich nach jeder Runde im Uhrzeigersinn.
Daraus ergibt sich folgener Spielplan.
----------------------
01 M1/F1 - M2/F2
02 M3/F3 - M4/F4
03 M5/F5 - M6/F6
----------------------
04 M1/F3 - M4/F1
05 M2/F5 - M6/F2
06 M3/F4 - M5/F6
----------------------
07 M1/F5 - M6/F3
08 M4/F4 - M5/F1
09 M2/F2 - M3/F6
----------------------
10 M1/F4 - M5/F5
11 M6/F2 - M3/F3
12 M4/F1 - M2/F6
----------------------
13 M1/F2 - M3/F4
14 M5/F1 - M2/F5
15 M6/F3 - M4/F6
----------------------
Die Bedingungen a1 und a2 sind erfüllt, b1 - c2 leider nicht.
Ich habe auch schon andere Vorgehensweisen probiert, leider ohne Erfolg.
=========================================
Ich wäre über jeden Löungsansatz dankbar.
Grüße aus Ostdeutschland
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Hallo und guten Tag,
nur ein Ansatz zum Vorgehen:
Mal Dir die Paare als 6 x 6 Gitter auf. Die vertikalen Linien sind Maenner, die horizontalen Linien sind Frauen.
Regeln:
Keine zwei vertikalen oder horizontalen Linien duerfen zweimal verbunden werden. Keine horizontale oder vertikale Linie darf mit sich selbst verbunden werden.
Jede horizontale und jede vertikale Linie soll Grad 5 bekommen.
Dann schau Dir vllt die Knotengrade an, und ich denke, mit diesem Bild kann man systematisch eine Loesung generieren, wenn es eine gibt.
Vielleicht spaeter mehr....
Gruss,
Mathias
|
|
|
| |
|
Sorry, das war sehr unbedacht. Ich habe mich schon im anderen Forum beim Moderator per eMail dafür entschuldigt. Möchte dies hiermit auch bei euch tun.
Danke natürlich an Matthias für seine Mühe. Habe versucht seinen Lösungsansatz aufzugreifen, bin aber ganz ehrlich, daß ich ihn nicht ganz verstehe (bin wahrscheinlich zu blöd, da kein Mathematiker).
Also, bitte nicht böse sein 
|
|
|
| |
|
Hallo nochmal,
also ich sehe momentan kein kompaktes graphentheoretisches Argument, das die Antwort liefert, ob es geht, und im Falle der ''Ja''-Antwort die Loesung.
Also wie schon geschrieben: Eine Moeglichkeit ist es, das von Hand zu probieren.
Eine weitere besteht darin, das Verfahren zu automatisieren. Zwei Loesungsansaetze liegen auf der Hand:
(1) Backtracking. D.h. man versucht systematisch, die Partien zu generieren, indem man Paare mapt, und wenn es mal nicht klappt, geht man im Suchbaum zurueck und versucht die naechste Alternative.
(2) Man kann das Problem als ILP (Integer Linear Program) formulieren. Hat man einen ILP-Solver
in Form einer Software bei der Hand, kann man das auf dieser Instanz einfach mal laufen lassen.
Ansonsten ist das ein Matching-Problem mit Restriktionen, ueber das ich in allgemeiner Form momentan
nicht viel weiss.
Mir fallen spontan Matching-Experten ein, die man fragen koennte, zB via Email an ml@cs.uni-bonn.de (der Inhaber
dieser Email-Adresse moege mir nicht allzu boese sein !).
An Karl:
Waer das hier nicht was fuer Dich zum Implementieren ?
Gruss,
Mathias
|
|
|
|
![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]")
![[]](/images/popup.gif){kind=small}
http://www.matheboard.de/thread.php?threadid=29659