Problem der 15 Schulmädchen

Das Problem der 15 Schulmädchen^[1] 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.^[2] 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^[3] und Lösungen wurden von Arthur Cayley^[4] und Kirkman selbst gegeben.^[5] 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,^[6] war Kirkman indigniert.^[7] Kirkmans Beitrag fiel zeitweise fast in Vergessenheit, trotz einer Würdigung durch L. D. Cummings 1918.^[8] 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^[9], Édouard Lucas^[10], W. W. Rouse Ball^[11] und Henry Dudeney^[12]

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.^[13] 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}}$ .^[7] 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.^[14]^[15] 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.^[7]

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^[16] 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.^[7]

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^[17] 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:^[18]

	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:^[19]

	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

Literatur

W. W. Rouse Ball: Mathematical Recreations and Essays, Macmillan 1926, Kapitel X (Kirkman's School-Girls Problem)
- Digitalisat der Ausgabe 1917, dort Kapitel IX (ab Seite 193)
Martin Gardner: Dinner guests, schoolgirls and handcuffed persons, Scientific American Mai 1980 und in: Gardner The last recreations, Springer 1997, S. 121–138
Giovanni Falcone, Marco Pavone: Kirkman's Tetrahedron and the Fifteen Schoolgirls Problem, American Mathematical Monthly, Band 118, Heft 10, 2011, S. 887–900

Weblinks

Einzelnachweise

↑ Die deutsche Bezeichnung findet sich zum Beispiel im Jahrbuch über die Fortschritte der Mathematik, Band 23 von 1894, S. 33.
↑ Rouse Ball, Mathematical Recreations and Essays, Macmillan 1926, S. 193
↑ Query VI, in: The Lady’s and Gentleman’s Diary for the year 1850, S. 48
↑ Cayley: On the triadic arrangements of seven and fifteen things, Phil. Mag. 37, 1850, S. 50–53
↑ Kirkman: Note on an unanswered prize question, The Cambridge and Dublin Mathematical Journal, Band 5, 1850, S. 255–262. Einen allgemeineren Fall behandelte er schon drei Jahre früher: Cambridge and Dublin Math. J., Band 2, 1847, S. 191–205.
↑ Kirkman, On a problem in combinations, Cambridge and Dublin Math. J., Band 2, 1847, S. 191–204
↑ ^a ^b ^c ^d Giovanni Falcone, Marco Pavone: Kirkman's Tetrahedron and the Fifteen Schoolgirls Problem, American Mathematical Monthly, Band 118, Heft 10, 2011, S. 887–900
↑ L. D. Cummings, An undervalued Kirkman paper, Bull. Amer. Math. Soc., Band 24, 1918, S. 336–339.
↑ W. Ahrens: Mathematische Unterhaltungen und Spiele, Teubner 1901, S. 274–285
↑ E. Lucas, Récréations Mathématiques, Band 2, Gauthier-Villars, Paris, 1883.
↑ Rouse Ball, Mathematical Recreations and Essays, Macmillan 1892
↑ Dudeney, Amusements in mathematics, Thomas Nelson and Sons, 1917
↑ Kirkman Triple System, mathworld
↑ Woolhouse: On triadic combinations of 15 symbols. In: Lady’s and Gentleman’s Diary, 1862, Seiten 84–88 (reprinted in Assurance Magazine, 1862, Seiten 275–281).
↑ Woolhouse: On triadic combinations. In: Lady’s and Gentleman’s Diary, 1863, Seiten 79–90.
↑ E. W. Davis, A geometric picture of the fifteen school girl problem, Ann. of Math., Band 11, 1897, S. 156–157
↑ Ray-Chaudhuri, Wilson: Solution of Kirkman’s schoolgirl problem, in: Combinatorics, University of California, Los Angeles, 1968, Proc. Sympos. Pure Math, American Mathematical Society, Band 19, 1971, S. 187–203
↑ Auf dieser Webseite mit S₉ bezeichnet
↑ W. W. Rouse Ball: Mathematical Recreations and Essays. 4. Auflage. Mac Millan and Co. Ltd., London 1905, S. 103 bis 109 (englisch, gutenberg.org [PDF]).

[1] Die deutsche Bezeichnung findet sich zum Beispiel im Jahrbuch über die Fortschritte der Mathematik, Band 23 von 1894, S. 33.

[2] Rouse Ball, Mathematical Recreations and Essays, Macmillan 1926, S. 193

[3] Query VI, in: The Lady’s and Gentleman’s Diary for the year 1850, S. 48

[4] Cayley: On the triadic arrangements of seven and fifteen things, Phil. Mag. 37, 1850, S. 50–53

[5] Kirkman: Note on an unanswered prize question, The Cambridge and Dublin Mathematical Journal, Band 5, 1850, S. 255–262. Einen allgemeineren Fall behandelte er schon drei Jahre früher: Cambridge and Dublin Math. J., Band 2, 1847, S. 191–205.

[6] Kirkman, On a problem in combinations, Cambridge and Dublin Math. J., Band 2, 1847, S. 191–204

[falcone-7] Giovanni Falcone, Marco Pavone: Kirkman's Tetrahedron and the Fifteen Schoolgirls Problem, American Mathematical Monthly, Band 118, Heft 10, 2011, S. 887–900

[8] L. D. Cummings, An undervalued Kirkman paper, Bull. Amer. Math. Soc., Band 24, 1918, S. 336–339.

[9] W. Ahrens: Mathematische Unterhaltungen und Spiele, Teubner 1901, S. 274–285

[10] E. Lucas, Récréations Mathématiques, Band 2, Gauthier-Villars, Paris, 1883.

[11] Rouse Ball, Mathematical Recreations and Essays, Macmillan 1892

[12] Dudeney, Amusements in mathematics, Thomas Nelson and Sons, 1917

[13] Kirkman Triple System, mathworld

[14] Woolhouse: On triadic combinations of 15 symbols. In: Lady’s and Gentleman’s Diary, 1862, Seiten 84–88 (reprinted in Assurance Magazine, 1862, Seiten 275–281).

[15] Woolhouse: On triadic combinations. In: Lady’s and Gentleman’s Diary, 1863, Seiten 79–90.

[16] E. W. Davis, A geometric picture of the fifteen school girl problem, Ann. of Math., Band 11, 1897, S. 156–157

[17] Ray-Chaudhuri, Wilson: Solution of Kirkman’s schoolgirl problem, in: Combinatorics, University of California, Los Angeles, 1968, Proc. Sympos. Pure Math, American Mathematical Society, Band 19, 1971, S. 187–203

[18] Auf dieser Webseite mit S₉ bezeichnet

[19] W. W. Rouse Ball: Mathematical Recreations and Essays. 4. Auflage. Mac Millan and Co. Ltd., London 1905, S. 103 bis 109 (englisch, gutenberg.org [PDF]).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]