Matroids Matheplanet Forum Index
Moderiert von matroid
Mathematik » Kombinatorik & Graphentheorie » Komplexe(r) Gruppenauslosung/Spielplan
Druckversion
Druckversion
Antworten
Antworten
Autor
Kein bestimmter Bereich Komplexe(r) Gruppenauslosung/Spielplan
BeInspired
Neu Letzter Besuch: im letzten Quartal
Dabei seit: 22.09.2020
Mitteilungen: 2
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2020-09-22


Hallo zusammen,

ich hoffe ich bin in diesem Forum richtig mit meiner Frage.

Es geht um eine online Version eines Brettspiels, bei dem in einer Partie 6 Personen gegeneinander spielen. Dabei übernimmt jeder Spieler die Kontrolle über eine der 6 individuellen Fraktionen.

Bei einem Turnier gibt es jetzt 6 Teams mit jeweils 6 Spielern. Jeder Spieler soll nun 6 Partien spielen und dabei jede Fraktion genau einmal spielen. Insgesamt ergeben sich also 36 Partien. In jeder Partie gibt es genau 1 Spieler aus jedem Team.

Soweit so einfach. Bisher wurde keine weitere Einschränkung vorgegeben, dh es war beispielsweise möglich, dass es Spieler 1 aus Team A in 3 Partien mit Spieler 2 aus Team B zu tun bekam; zwar hatten beide jeweils immer eine andere Fraktion inne, aber sie haben in mehreren Spielen zusammen gespielt, während sie vll mit Spieler 3 aus Team C in gar keinem Spiel zusammentreffen.

Jetzt kommt die entscheidende Nebenbedingung: gibt es eine Möglichkeit für einen Spielplan, in dem jeder Spieler in seinen 6 Partien genau einmal auf jeden anderen Spieler aus den anderen Teams trifft?

Ich hoffe meine Beschreibung ist einigermaßen verständlich... Ansonsten gerne nachhaken.

Vielen Dank und viele Grüße
Henrik



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 3632
Aus: Harz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2020-09-24


Hallo BeInspired,

und willkommen auf dem Matheplanet!

Die Problemstellung ist so glaube ich ganz gut verständlich. Ich bin sozusagen am Knobeln, mir ist kein Standardverfahren bekannt um das mal so eben zu lösen. Entweder findet man ein Verfahren, wie man die Spieler in den Runden passend "rotiert", sodass alles passt, oder, was ich alternativ mal angehe, man kann ein Programm schreiben, das versucht nach der "trial and error" Methode eine passende Plazierung zu finden.

Grüße
Gerhard/Gonz


-----------------
Heute: Keine Signatur.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 2440
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, eingetragen 2020-09-24


Hier stand Unsinn ...



-----------------
Why waste time learning when ignorance is instantaneous?
- Bill Watterson -



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 6242
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2020-09-24


Hallo BeInspired,

hier mal eine anfängliche Idee.

(x,y) bezeichne Spieler Nr. x aus Team Nr. y. Hierbei sind x und y Zahlen von 0 bis 5.

Die 6 Spielrunden des Turniers seien ebenfalls von 0 bis 5 nummeriert.

Für zwei Spieler (x,y) und (u,v) definiere dann f((x,y),(u,v)) = x+y+u+v mod 6.

Wir gestalten nun wie folgt den Spielplan:

Spieler (x,y) trifft auf Spieler (u,v) in Spielrunde Nr. f((x,y),(u,v)).

Damit sollte gelten: Jeder Spieler  absolviert genau 6 Partien und trifft auf jeden anderen Spieler der gegnerischen Mannschaften.

Das sähe dann so aus:
Spielrunde 0:
(0,0) (1,5) (2,4) (3,3) (4,2) (5,1) 
(0,1) (1,4) (2,3) (3,2) (4,1) (5,0) 
(0,2) (1,3) (2,2) (3,1) (4,0) (5,5) 
(0,3) (1,2) (2,1) (3,0) (4,5) (5,4) 
(0,4) (1,1) (2,0) (3,5) (4,4) (5,3) 
(0,5) (1,0) (2,5) (3,4) (4,3) (5,2) 
Spielrunde 1:
(0,0) (1,0) (2,5) (3,4) (4,3) (5,2) 
(0,1) (1,5) (2,4) (3,3) (4,2) (5,1) 
(0,2) (1,4) (2,3) (3,2) (4,1) (5,0) 
(0,3) (1,3) (2,2) (3,1) (4,0) (5,5) 
(0,4) (1,2) (2,1) (3,0) (4,5) (5,4) 
(0,5) (1,1) (2,0) (3,5) (4,4) (5,3) 
Spielrunde 2:
(0,0) (1,1) (2,0) (3,5) (4,4) (5,3) 
(0,1) (1,0) (2,5) (3,4) (4,3) (5,2) 
(0,2) (1,5) (2,4) (3,3) (4,2) (5,1) 
(0,3) (1,4) (2,3) (3,2) (4,1) (5,0) 
(0,4) (1,3) (2,2) (3,1) (4,0) (5,5) 
(0,5) (1,2) (2,1) (3,0) (4,5) (5,4) 
Spielrunde 3:
(0,0) (1,2) (2,1) (3,0) (4,5) (5,4) 
(0,1) (1,1) (2,0) (3,5) (4,4) (5,3) 
(0,2) (1,0) (2,5) (3,4) (4,3) (5,2) 
(0,3) (1,5) (2,4) (3,3) (4,2) (5,1) 
(0,4) (1,4) (2,3) (3,2) (4,1) (5,0) 
(0,5) (1,3) (2,2) (3,1) (4,0) (5,5) 
Spielrunde 4:
(0,0) (1,3) (2,2) (3,1) (4,0) (5,5) 
(0,1) (1,2) (2,1) (3,0) (4,5) (5,4) 
(0,2) (1,1) (2,0) (3,5) (4,4) (5,3) 
(0,3) (1,0) (2,5) (3,4) (4,3) (5,2) 
(0,4) (1,5) (2,4) (3,3) (4,2) (5,1) 
(0,5) (1,4) (2,3) (3,2) (4,1) (5,0) 
Spielrunde 5:
(0,0) (1,4) (2,3) (3,2) (4,1) (5,0) 
(0,1) (1,3) (2,2) (3,1) (4,0) (5,5) 
(0,2) (1,2) (2,1) (3,0) (4,5) (5,4) 
(0,3) (1,1) (2,0) (3,5) (4,4) (5,3) 
(0,4) (1,0) (2,5) (3,4) (4,3) (5,2) 
(0,5) (1,5) (2,4) (3,3) (4,2) (5,1) 

EDIT: Ich sehe jetzt, dass meine Idee noch nicht funktioniert. Aus f((x,y),(a,b))=i und f((x,y),(c,d))=i folgt nämlich nicht, dass f((a,b),(c,d))=i 🤔


[Die Antwort wurde nach Beitrag No.1 begonnen.]



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 3632
Aus: Harz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, eingetragen 2020-09-24


Per Programm konstruiert (und um erstmal abzuprüfen ob alles richtig verstanden) ist hier eine Paarungstabelle für vier Mannschaften (A..D) mit je vier Spielern (1..4):

Paarungen in Runde 1
Tisch 1 : A-1,B-1,C-1,D-1
Tisch 2 : A-2,B-2,C-2,D-2
Tisch 3 : A-3,B-3,C-3,D-3
Tisch 4 : A-4,B-4,C-4,D-4
Paarungen in Runde 2
Tisch 1 : B-1,A-2,D-3,C-4
Tisch 2 : B-2,A-1,D-4,C-3
Tisch 3 : B-3,A-4,D-1,C-2
Tisch 4 : B-4,A-3,D-2,C-1
Paarungen in Runde 3
Tisch 1 : C-1,D-3,A-4,B-2
Tisch 2 : C-2,D-4,A-3,B-1
Tisch 3 : C-3,D-1,A-2,B-4
Tisch 4 : C-4,D-2,A-1,B-3
Paarungen in Runde 4
Tisch 1 : D-1,C-4,B-2,A-3
Tisch 2 : D-2,C-3,B-1,A-4
Tisch 3 : D-3,C-2,B-4,A-1
Tisch 4 : D-4,C-1,B-3,A-2

Leider funktioniert das Programm für N>4 noch nicht.


-----------------
Heute: Keine Signatur.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
BeInspired
Neu Letzter Besuch: im letzten Quartal
Dabei seit: 22.09.2020
Mitteilungen: 2
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, vom Themenstarter, eingetragen 2020-09-24


Hey. Vielen Dank für eure Antworten und dass ihr euch damit befasst :)

Deine Lösung, gonz, für N=4 sieht genau nachdem aus, was wir für N=6 benötigen.

Habe schon fast "befürchtet", dass man es mit der Brechstange angehen muss. Leider lassen meine nicht vorhandenen Programmierskills es nicht zu, dass ich sowas mal eben selber schreibe... Falls du es für N=6 hinbekommen solltest, wäre das großartig!

Vielen Dank nochmal und viele Grüße
Henrik



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
cramilu
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 09.06.2019
Mitteilungen: 457
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, eingetragen 2020-09-25


Hallo BeInspired,

so wie ich Dein Vorhaben verstanden habe,
hege ich die zarte Befürchtung, dass es nicht machbar ist!

Es erscheint mir deutlich artverwandt zum Problem der 36 Offiziere,
an dem sich bereits Leonhard Euler lange "die Zähne ausgebissen" hatte...

Natürlich kann ich mich böse täuschen, aber ein eingehender Problemvergleich
könnte Stunden fruchtloser Algorithmik ersparen ;)


-----------------

ODERINT DUM NERVOS NE VEXENT!




Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 3632
Aus: Harz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, eingetragen 2020-09-25


Hallo Cramilu,

es trifft nicht ganz genau das Problem der "Euler Quadrate", den für N=2 gibt es ja hier eine Lösung:

Paarungen in Runde 1
Tisch 1 : A-1,B-1
Tisch 2 : A-2,B-2
Paarungen in Runde 2
Tisch 1 : B-1,A-2
Tisch 2 : B-2,A-1

Der Verweis ist aber interessant, Mathematik ist so vielseitig :)
Grüße - Gonz


-----------------
Heute: Keine Signatur.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
haegar90
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 18.03.2019
Mitteilungen: 444
Aus: Gog
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, eingetragen 2020-09-25


Hallo zusammen,

täusche ich mich oder wäre hierfür die Cantorsche Paarungsfunktion (etwas abgewandelt) nützlich ?


-----------------
Gruß haegar



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 3632
Aus: Harz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.9, eingetragen 2020-09-25


Nebenbemerkung: ich habe den Fehler im Programm gefunden, aber bei n>4 beisst es sich die Zähne aus. Ich habe einen Backtracking Mechanismus gebaut, der bei n=4 noch in wenigen Sekunden eine Lösung findet, bei n=5 (und damit erst recht bei n=6) von der Laufzeit her gleichsam explodiert. Vielleicht kann man versuchen, die Lösung für n=4 zu analysieren und daraus abzuleiten, wie man Lösungen für größeres n konstruieren kann (wenn sie denn existieren).


-----------------
Heute: Keine Signatur.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 3632
Aus: Harz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.10, eingetragen 2020-09-25


Ah und vielleicht kann man es dann einfach damit lösen, dass 6=3x2 und die bekannten Lösungen für n=3 und n=2 kombinieren. Wir teilen auf:

Teams A,B,C,D,E,F in Gruppe ALMA: A,B,C und Gruppe BERTA: D,E,F
Mitspieler 1,2,3,4,5,6 in Gang I : 1,2,3 und Gang II : 4,5,6

Diese setzen wir jetzt nach folgendem Schema:

in Runden 1-3 spielen:

ALMA-I an Positionen 1-3 der Tische 1-3
   vs BERTHA-I an den Positionen 4-6 der Tische 1-3
und
ALMA-II an Positionen 1-3 der Tische 4-6
   vs BERTHA-II an den Positionen 4-6 der Tische 4-6

in den Runden 4-6 spielen:

BERTHA-II an den Positionen 1-3 der Tische 1-3
   vst ALMA-I and den Positionen 4-6 der Tische 1-3

BERTHA-I an den Positionen 1-3 der Tische 4-6
   vst ALMA-II and den Positionen 4-6 der Tische 4-6

innerhalb der 3 Runden wird innerhalb der Gangs jeweils nach dem Schema für n=3 auf den vorgegebenen Positionen rotiert...

Das könnte man sogar händisch zusammenbauen. Ich würde es aber eher mittels Programm realsieren...

Und hier ist noch für n=3:

Paarungen in Runde 1
Tisch 1 : A-1,B-1,C-1
Tisch 2 : A-2,B-2,C-2
Tisch 3 : A-3,B-3,C-3
Paarungen in Runde 2
Tisch 1 : B-1,C-2,A-3
Tisch 2 : B-2,C-3,A-1
Tisch 3 : B-3,C-1,A-2
Paarungen in Runde 3
Tisch 1 : C-1,A-3,B-2
Tisch 2 : C-2,A-1,B-3
Tisch 3 : C-3,A-2,B-1



-----------------
Heute: Keine Signatur.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 2440
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.11, eingetragen 2020-09-25


Lösung nach wie vor verbuggt. GRRRHHHH


-----------------
Why waste time learning when ignorance is instantaneous?
- Bill Watterson -



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
BeInspired hat die Antworten auf ihre/seine Frage gesehen.
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2020 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]