+3 Daumen
360 Aufrufe

Ich habe gestern Nacht eine Real-Life-Aufgabe von einem Bekannten bekommen und bin noch nicht sicher, ob mein Ansatz sinnvoll ist.

Aufgabe:

Es gibt ein großes Kennenlern-Seminar mit 4 Runden (Touren). Das Seminar hat x Räume und y Teilnehmer. Nun ist es Aufgabe, die Teilnehmer so je Runde in den Räumen zu verteilen, dass sich so viele Leute wie möglich miteinander treffen - bzw. anders gesagt, sich jeder Teilnehmer bestmöglich mit allen anderen Teilnehmern einmal sieht.


Mein Ansatz

Ich habe versucht, es erst mal einfach mit 3 Räumen A, B, C und 9 Personen anzugehen:

Runde 1 (einfach der Personennummer nacheinander aufgeteilt): 

ABC
147
258
369



Für die nächsten Runden darf also Person 1 nicht mehr Personen 2 und 3 begegnen. Bestmöglich. 


Runde 2 horizontale Verschiebungen I 
Ich verschiebe die Indexe für die 2. horizontale Reihe um +1 und für die 3. Reihe um +2:

ABC
147
8
2
5
6
93


Runde 3 horizontale Verschiebungen II 
Ich verschiebe erneut die Indexe für die 2. horizontale Reihe um +1 und für die 3. Reihe um +2: 

ABC
147
58
2
9
36


Eine weitere horizontale Verschiebung ist jetzt nicht mehr möglich, sonst würden sich Teilnehmer erneut sehen. 

Runde 4 - Horizontal zu Vertikal 
Person 1 war noch nicht mit Person 4 und Person 7 in einem Zimmer - drehen wir horizontal also zu vertikal: 

ABC
18
6

2
9
7
53


So scheint es also in einfachster Weise zu klappen.

Meine Aufgabe ist es, hierfür einen sinnvollen "Algorithmus" zu finden - oder besser: direkt in ein Programm umzusetzen, wie gesagt, mit beliebig vielen x Räumen und y Teilnehmern. Und hier liegt der Knackpunkt, die Index-Verschiebung (neue Positionen je Runde) sollte kein Problem sein, aber kann ich bspw. diese Drehung von Horizontal zu Vertikal immer durchführen, ohne auf Probleme zu stoßen?

Nebenbei wird es noch eine Nummer schwieriger, wenn wir die Anzahl an Teilnehmern je Raum anders festlegen ... aber das für später. Erst mal ist das obige zu verstehen und eine allgemeine Lösung zu finden.

Danke vorab für eure Ansätze und Ideen!
Kai


PS: Aufgabe erinnert irgendwie an Kombinatorik und Matrizen ...

Avatar von 1,7 k

Das sieht mir sehr nach (affinen) endlichen Geometrien aus.

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community