Gruppeneinteilung bei Radtour: kombinatorisches Problem

20/06/2009 - 17:44 von Uwe Bosse | Report spam
Hallo mittenand,
In den Pfingstferien habe ich eine Schülergruppe (35 Schüler) auf einer
Radtour über die Alpen bis kurz vor Neapel begleitet. Die Schüler waren in
5 Gruppen mit je 7 Schülern unterwegs, wobei die Gruppen tàglich neu
zusammengestellt wurden. Am Ende stellten die Schüler fest, dass sie mit
manchen nie, mit anderen hàufig in der gleichen Gruppe gefahren sind. Das
provoziert natürlich eine kombinatorische Fragestellung: nach wie viel
Tagen kann bei geschicktem Durchmischen frühestens jeder mal mit jedem in
einer Gruppe gefahren sein? Wie muss man durchmischen, damit das möglichst
bald der Fall ist?

Zunàchst schien mir das ein nicht soo schwieriges Problem zu sein.
Mittlerweile denke ich anders darüber.

Meine Überlegungen hierzu bisher: Ich habe mir die Aufgabe erheblich
vereinfacht, indem ich fünf Gruppen mit fünf Schülern betrachte.
(Allgemein: n Gruppen mit n Schülern). Um eine Untergrenze für die Anzahl
der Tage zu finden, betrachte ich die Anzahl der Begegnungen, die die 25
Schüler haben müssen: jeder mit jedem bedeutet 25*24/2 = 300 Begegnungen.
In jeder der fünf Gruppen kommt es tàglich zu maximal 5*4/2P Begegnungen,
somit braucht es mindestens 6 Tage. Diese reichen aber nur, wenn kein
einziger Schüler ein zweites Mal mit einem zusammen fàhrt, mit dem er schon
gefahren ist. (allgemein ergibt diese Rechnung bei n Gruppen mit n Schülern
n+1 Tage.) Tatsàchlich gibt es eine Lösung mit 6 Tagen. Dazu stelle ich die
Schüler auf eine 5 mal 5 - Matrix und wiederhole diese Aufstellung durch
Klone nach unten. Also in Matrixschreibweise: a_11=a_61=...
also a_ij=a_kj wenn i=k mod 5.

Für die Gruppeneinteilung am ersten Tag ziehe ich Geraden durch dieses
Gitter: 5 parallele Geraden senkrecht nach unten.
also Gruppe 1: a_11, a_21, a_31, a_41, a_51
Gruppe 2: a_12, a_22, a_32, a_42, a_52
u.s.w.
Für den zweiten Tag nehme ich parallele horizontale Geraden
Gruppe 1: a_11, a_12, a_13, a_14, a_15
Gruppe 2: a_21, a_22, a_23, a_24, a_25
u.s.w.
Am dritten Tag parallele diagonale Geraden (jetzt brauche ich die Klone)
Gruppe 1: a_11, a_22, a_33, a_44, a_55
Gruppe 2: a_21, a_32, a_43, a_54, a_65
u.s.w.
Am vierten Tag gehts los mit
Gruppe 1: a_11, a_32, a_53, a_74, a_95
Gruppe 1: a_21, a_42, a_63, a_84, a_10.5
u.s.w.
Am fünften Tag
a_11, a_42, a_73, a_10.4, a_13.5
a_21, a_52, a_83, u.s.w.
u.s.w.

Dieses Verfahren funktioniert so aber nur, wenn n eine Primzahl ist.
Für n=4 scheitert es. Ich bezweifle sogar, dass es überhaupt irgendeine
Lösung für 4 Gruppen mit 4 Schülern gibt, die mit 5 Tagen auskommt, kanns
aber nicht beweisen. Kanns jemand?

Was auch, wenn es mehr Schüler in einer Gruppe als Gruppen gibt?

Wàre froh, wenn hier einer mitdenken würde.

Gruß, Uwe.
 

Lesen sie die antworten

#1 Christopher Creutzig
20/06/2009 - 18:58 | Warnen spam
Uwe Bosse wrote:

provoziert natürlich eine kombinatorische Fragestellung: nach wie viel
Tagen kann bei geschicktem Durchmischen frühestens jeder mal mit jedem in
einer Gruppe gefahren sein? Wie muss man durchmischen, damit das möglichst
bald der Fall ist?



Ich komme partout nicht auf den Namen, den das Problem in der Literatur
hat, aber das ist IIRC eines der Dinger, zu denen Martin Gardner
Wichtiges beigetragen hat. (Bei ihm begann die Untersuchung wohl mit
Schulmàdels, die in Dreierreihen herumliefen.) Vielleicht hilft das ja
schon weiter.

Freiheit ist eine Zumutung. Aber sie ist zumutbar.

Ähnliche fragen