# Problem der 15 Schulmädchen

Das Problem der 15 Schulmädchen wurde 1850 von Thomas Kirkman formuliert.
Es lautet:
   “Fifteen young ladies in a school walk out three abreast for seven days in succession: it is required to arrange them daily, so that no two shall walk twice abreast.”
   „Fünfzehn Schulmädchen [wörtlich: junge Damen] spazieren sieben Tage hintereinander in Dreiergruppen: Es wird gefordert, sie täglich so einzuteilen, dass keine zwei Schulmädchen zweimal zusammen spazieren.“
Im allgemeinen Fall sollen $n$ Schulmädchen $y$ Tage hintereinander ausgehen, sodass ein Schulmädchen genau einmal mit irgendeinem anderen der Mädchen in einer Dreiergruppe ist. Dabei gilt
    $y={\frac {n-1}{2}}$
entsprechend der Zahl der verschiedenen Paarungen eines Schulmädchens mit den anderen. Das erfordert, dass $n$ ein ungerades Vielfaches von drei ist, also
    $y={\frac {6k+2}{2}}$ mit $6k+3=n$ und $k\in \mathbb {N} _{0}$
gültig ist. Gültige Werte für k, n und y sind:
| k | 0 | 1 | 2 | 3 |
| n | 3 | 9 | 15 | 21 |
| y | 1 | 4 | 7 | 10 |
Das Problem wurde 1850 von Kirkman in der Zeitschrift für Unterhaltungsmathematik The Lady’s and Gentleman’s Diary gestellt und Lösungen wurden von Arthur Cayley und Kirkman selbst gegeben. Später gab es einen Streit zwischen Kirkman und dem berühmten Mathematiker James Joseph Sylvester, der ebenfalls die Einführung des Problems für sich in Anspruch nahm. Auch als Jakob Steiner 1853 Probleme über Steiner-Systeme stellte (mit einer Lösung von Reiss 1859), sechs Jahre nach der Veröffentlichung von Kirkman von 1847 über von ihm so genannte Triaden-Systeme, war Kirkman indigniert. Kirkmans Beitrag fiel zeitweise fast in Vergessenheit, trotz einer Würdigung durch L. D. Cummings 1918. Das Schulmädchenproblem findet sich Ende des 19. und Anfang des 20. Jahrhunderts in verschiedenen klassischen Büchern über Unterhaltungsmathematik wie dem von Wilhelm Ahrens, Édouard Lucas, W. W. Rouse Ball und Henry Dudeney
Das Schulmädchen-Problem ist ein Spezialfall des Oberwolfach-Problems und der Steiner-Systeme $S(t,k,n)$, einem System von $n$ Elementen mit einer Einteilung in $k$-elementige Blöcke als Untermengen, so dass jede Untermenge von $t$ Elementen in genau einem Block ist (auch $t$-$(n,k,1)$-Blockplan genannt). Im Schulmädchenproblem für $n$ Schulmädchen hat man es mit Steiner-Tripel-Systemen $S(2,3,n)$ zu tun, genauer einem solchen mit Parallelismus (Kirkman-Tripel-System) und von der Ordnung 2. Kirkman-Tripel-Systeme sind Steiner-Tripel-Systeme, bei denen die Tripel so in disjunkte Klassen eingeteilt werden können, dass jede Klasse eine Zerlegung der Gesamtmenge ergibt. Das Problem der 15 Schulmädchen fragt nach der Existenz eines Kirkman-Tripel-Systems für 15 Elemente. Kirkman war der erste, der bewies, dass es Steiner-Tripel-Systeme mit $n$ Elementen genau dann gibt, wenn $n\equiv 1{\pmod {6}}$ oder $n\equiv 3{\pmod {6}}$. Es gibt im Fall $n=15$ insgesamt sieben Möglichkeiten, die Schulmädchengruppen so wie gefordert einzuteilen. Diese wurden 1862/1863 von Wesley Woolhouse in derselben Zeitschrift veröffentlicht, in der Kirkman das Problem stellte. Die Frage, ob eine Lösung isomorph zu einer anderen ist, ist nicht einfach: bis 1881 wurden 11 Lösungen veröffentlicht, aber erst 1917 bzw. 1922 wurde bewiesen, dass es nur 7 nicht-isomorphe Lösungen gibt.
Eine geometrische Darstellung der 7 Lösungen des 15-Schulmädchen-Problems über die 8 Ecken, 6 Seiten eines Würfels und den Gesamtwürfel gab E. W. Davis 1897 und bewies, dass es keinen Automorphismus der Ordnung 7 gibt. Pavone und Falcone gaben zwei weitere geometrische Beschreibungen über die 4 Ecken, 6 Kanten, 4 Seitenflächen eines Tetraeders und den Gesamt-Tetraeder. Dies war gleichzeitig ein Modell der dreidimensionalen projektiven Geometrie $\operatorname {PG} (3,2)$ über dem endlichen Körper mit zwei Elementen.
Die allgemeine Lösung solcher Probleme erwies sich als schwieriger als ursprünglich angenommen. Der Beweis der Existenz einer Lösung im allgemeinen Fall wurde von Richard M. Wilson und D. K. Ray-Chaudhuri 1968 erbracht und 2014 wurde sogar allgemeiner ein Existenzbeweis für zulässige Blockpläne von Peter Keevash gegeben (mit endlich vielen Ausnahmen). Es gibt nicht für jedes $n$ und jede Kombination von Parametern Lösungen: Gewisse natürliche Teilbarkeitsbedingungen müssen erfüllt sein, zum Beispiel muss im Fall der Schulmädchen wie erwähnt deren Anzahl $n$ ein ungerades Vielfaches von drei sein. Sind diese Bedingungen aber erfüllt, konnte Wilson die Existenz einer Lösung beweisen. Die Anzahl der Lösungen nimmt nach Keevash mit $n$ exponentiell zu.
Kirkmans Schulmädchenproblem war der Beginn der Entwicklung der Theorie der Blockpläne oder kombinatorischen Designs.
Mit der zusätzlichen Bedingung, dass am ersten Tag die Mädchen der Reihe nach (z. B. alphabetisch) in Gruppen unterwegs sind, werden durch Permutation der Personen generierte weitere Lösungen ausgeschlossen.
Explizit lautet eine der Lösungen für die 15 Schulmädchen an sieben Tagen ($k=2$):
| | Gruppe 1 | Gruppe 2 | Gruppe 3 | Gruppe 4 | Gruppe 5 |
| Sonntag | Anna Frieda Karin | Berta Gabi Lisa | Clara Hanna Moni | Dora Inge Nena | Erna Jutta Olga |
| Montag | Anna Berta Erna | Clara Dora Gabi | Frieda Moni Olga | Hanna Inge Lisa | Jutta Karin Nena |
| Dienstag | Anna Gabi Nena | Berta Clara Frieda | Dora Erna Hanna | Inge Jutta Moni | Karin Lisa Olga |
| Mittwoch | Anna Lisa Moni | Berta Dora Jutta | Clara Nena Olga | Erna Frieda Inge | Gabi Hanna Karin |
| Donnerstag | Anna Hanna Jutta | Berta Moni Nena | Clara Erna Karin | Dora Frieda Lisa | Gabi Inge Olga |
| Freitag | Anna Dora Olga | Berta Inge Karin | Clara Jutta Lisa | Erna Gabi Moni | Frieda Hanna Nena |
| Samstag | Anna Clara Inge | Berta Olga Hanna | Dora Karin Moni | Erna Lisa Nena | Frieda Gabi Jutta |
Für neun Schulmädchen an vier Tagen ($k=1$) z. B. folgende Lösung:
| | Gruppe 1 | Gruppe 2 | Gruppe 3 |
| Erster Tag | Anna Berta Clara | Dora Erna Frieda | Gabi Hanna Inge |
| Zweiter Tag | Anna Dora Gabi | Berta Erna Hanna | Clara Frieda Inge |
| Dritter Tag | Anna Erna Inge | Berta Frieda Gabi | Clara Dora Hanna |
| Vierter Tag | Anna Frieda Hanna | Berta Dora Inge | Clara Erna Gabi |
Für drei Schulmädchen an einem Tag ($k=0$) gibt es nur die triviale Lösung:
| | Gruppe 1 |
| Erster Tag | Anna Berta Clara |
Für 21 Schulmädchen an zehn Tagen ($k=3$) z. B. folgende Lösung:
| | Gruppe 1 | Gruppe 2 | Gruppe 3 | Gruppe 4 | Gruppe 5 | Gruppe 6 | Gruppe 7 |
| Erster Tag | Anna Hanna Olga | Berta Inge Petra | Clara Jutta Rita | Dora Karin Susi | Erna Lisa Thekla | Frieda Mona Ute | Gabi Nena Viktoria |
| Zweiter Tag | Anna Berta Frieda | Dora Erna Inge | Gabi Hanna Lisa | Jutta Karin Olga | Mona Nena Susi | Petra Rita Viktoria | Thekla Ute Clara |
| Dritter Tag | Gabi Jutta Petra | Hanna Karin Rita | Lisa Olga Viktoria | Susi Thekla Berta | Ute Anna Inge | Clara Erna Mona | Dora Frieda Nena |
| Vierter Tag | Mona Petra Anna | Nena Rita Berta | Susi Viktoria Frieda | Clara Dora Hanna | Erna Gabi Olga | Inge Karin Thekla | Jutta Lisa Ute |
| Fünfter Tag | Dora Gabi Mona | Erna Hanna Nena | Inge Lisa Susi | Olga Petra Ute | Rita Thekla Frieda | Viktoria Berta Jutta | Anna Clara Karin |
| Sechster Tag | Anna Dora Jutta | Berta Erna Karin | Frieda Inge Olga | Lisa Mona Rita | Nena Petra Clara | Susi Ute Gabi | Thekla Viktoria Hanna |
| Siebter Tag | Berta Clara Gabi | Erna Frieda Jutta | Hanna Inge Mona | Karin Lisa Petra | Nena Olga Thekla | Rita Susi Anna | Ute Viktoria Dora |
| Achter Tag | Jutta Mona Thekla | Karin Nena Ute | Olga Susi Clara | Viktoria Anna Erna | Berta Dora Lisa | Frieda Hanna Petra | Gabi Inge Rita |
| Neunter Tag | Petra Thekla Dora | Rita Ute Erna | Viktoria Clara Inge | Frieda Gabi Karin | Hanna Jutta Susi | Lisa Nena Anna | Mona Olga Berta |
| Zehnter Tag | Thekla Anna Gabi | Ute Berta Hanna | Clara Frieda Lisa | Inge Jutta Nena | Karin Mona Viktoria | Olga Rita Dora | Petra Susi Erna |