Das Problem der 15 Schulmädchen[1] wurde 1850 von Thomas Kirkman formuliert.

Ursprüngliche Publikation des Problems

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 Schulmädchen Tage hintereinander ausgehen, sodass ein Schulmädchen genau einmal mit irgendeinem anderen der Mädchen in einer Dreiergruppe ist. Dabei gilt

entsprechend der Zahl der verschiedenen Paarungen eines Schulmädchens mit den anderen. Das erfordert, dass ein ungerades Vielfaches von drei ist, also

mit und

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 , einem System von Elementen mit einer Einteilung in -elementige Blöcke als Untermengen, so dass jede Untermenge von Elementen in genau einem Block ist (auch --Blockplan genannt). Im Schulmädchenproblem für Schulmädchen hat man es mit Steiner-Tripel-Systemen 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 Elementen genau dann gibt, wenn oder .[7] Es gibt im Fall 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 ü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 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 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 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 ():

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 () 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 () gibt es nur die triviale Lösung:

Gruppe 1
Erster Tag Anna
Berta
Clara

Für 21 Schulmädchen an zehn Tagen () 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

Bearbeiten
  • W. W. Rouse Ball: Mathematical Recreations and Essays, Macmillan 1926, Kapitel X (Kirkman's School-Girls Problem)
  • 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
Bearbeiten

Einzelnachweise

Bearbeiten
  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
  7. 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
  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 S9 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]).