mini|Ursprüngliche Publikation des Problems
Das Problem der 15 SchulmädchenDie deutsche Bezeichnung findet sich zum Beispiel im Jahrbuch über die Fortschritte der Mathematik, Band 23 von 1894, S. 33. wurde 1850 von Thomas Kirkman formuliert.
Es lautet:
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.Rouse Ball, Mathematical Recreations and Essays, Macmillan 1926, S. 193. 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 gestelltV. I. Query, in: The Lady’s and Gentleman’s Diary for the year 1850, S. 48. und Lösungen wurden von Arthur CayleyCayley: On the triadic arrangements of seven and fifteen things, Phil. Mag. 37, 1850, S. 50–53. und Kirkman selbst gegeben.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. 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,Kirkman, On a problem in combinations, Cambridge and Dublin Math. J., Band 2, 1847, S. 191–204. war Kirkman indigniert.Giovanni Falcone, Marco Pavone: Kirkman's Tetrahedron and the Fifteen Schoolgirls Problem, American Mathematical Monthly, Band 118, Heft 10, 2011, S. 887–900. Kirkmans Beitrag fiel zeitweise fast in Vergessenheit, trotz einer Würdigung durch L. D. Cummings 1918.L. D. Cummings, An undervalued Kirkman paper, Bull. Amer. Math. Soc., Band 24, 1918, S. 336–339. 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,W. Ahrens: Mathematische Unterhaltungen und Spiele, Teubner 1901, S. 274–285. Édouard Lucas,E. Lucas, Récréations Mathématiques, Band 2, Gauthier-Villars, Paris, 1883. W. W. Rouse BallRouse Ball, Mathematical Recreations and Essays, Macmillan 1892. und Henry DudeneyDudeney, Amusements in mathematics, Thomas Nelson and Sons, 1917.
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.Kirkman Triple System, mathworld 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 . 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.Woolhouse: On triadic combinations of 15 symbols. In: Lady’s and Gentleman’s Diary, 1862, S. 84–88 (reprinted in Assurance Magazine, 1862, S. 275–281).Woolhouse: On triadic combinations. In: Lady’s and Gentleman’s Diary, 1863, S. 79–90. 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 1897E. W. Davis, A geometric picture of the fifteen school girl problem, Ann. of Math., Band 11, 1897, S. 156–157. 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.
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 erbrachtRay-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. 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 AnnaFriedaKarin BertaGabiLisa ClaraHannaMoni DoraIngeNena ErnaJuttaOlga Montag AnnaBertaErna ClaraDoraGabi FriedaMoniOlga HannaIngeLisa JuttaKarinNena Dienstag AnnaGabiNena BertaClaraFrieda DoraErnaHanna IngeJuttaMoni KarinLisaOlga Mittwoch AnnaLisaMoni BertaDoraJutta ClaraNenaOlga ErnaFriedaInge GabiHannaKarin Donnerstag AnnaHannaJutta BertaMoniNena ClaraErnaKarin DoraFriedaLisa GabiIngeOlga Freitag AnnaDoraOlga BertaIngeKarin ClaraJuttaLisa ErnaGabiMoni FriedaHannaNena Samstag AnnaClaraInge BertaOlgaHanna DoraKarinMoni ErnaLisaNena FriedaGabiJutta
Für neun Schulmädchen an vier Tagen () z. B. folgende Lösung:Auf dieser Webseite mit S9 bezeichnet Gruppe 1 Gruppe 2 Gruppe 3 Erster Tag AnnaBertaClara DoraErnaFrieda GabiHannaInge Zweiter TagAnnaDoraGabiBertaErnaHannaClaraFriedaInge Dritter TagAnnaErnaIngeBertaFriedaGabiClaraDoraHanna Vierter TagAnnaFriedaHannaBertaDoraIngeClaraErnaGabi
Für drei Schulmädchen an einem Tag () gibt es nur die triviale Lösung: Gruppe 1 Erster Tag AnnaBertaClara
Für 21 Schulmädchen an zehn Tagen () z. B. folgende Lösung: Gruppe 1 Gruppe 2 Gruppe 3 Gruppe 4 Gruppe 5 Gruppe 6 Gruppe 7Erster Tag Anna HannaOlga Berta IngePetra ClaraJuttaRita DoraKarinSusi ErnaLisaThekla FriedaMonaUte GabiNenaViktoriaZweiter Tag Anna Berta Frieda Dora Erna Inge Gabi HannaLisa JuttaKarinOlga MonaNenaSusi PetraRitaViktoria TheklaUte ClaraDritter Tag GabiJuttaPetra HannaKarinRita LisaOlgaViktoria SusiThekla Berta Ute Anna Inge Clara ErnaMona Dora FriedaNenaVierter Tag MonaPetra Anna NenaRita Berta SusiViktoria Frieda Clara Dora Hanna Erna GabiOlga IngeKarinThekla JuttaLisaUteFünfter Tag Dora GabiMona Erna HannaNena IngeLisaSusi OlgaPetraUte RitaThekla Frieda Viktoria BertaJutta Anna ClaraKarinSechster Tag Anna DoraJutta Berta ErnaKarin Frieda IngeOlga LisaMonaRita NenaPetra Clara SusiUte Gabi TheklaViktoria HannaSiebter Tag Berta Clara Gabi Erna FriedaJutta Hanna IngeMona KarinLisaPetra NenaOlgaThekla RitaSusi Anna UteViktoria DoraAchter Tag JuttaMonaThekla KarinNenaUte OlgaSusi Clara Viktoria Anna Erna Berta DoraLisa Frieda HannaPetra Gabi IngeRitaNeunter Tag PetraThekla Dora RitaUte Erna Viktoria Clara Inge Frieda GabiKarin HannaJuttaSusi LisaNena Anna MonaOlga BertaZehnter Tag Thekla Anna Gabi Ute Berta Hanna Clara FriedaLisa IngeJuttaNena KarinMonaViktoria OlgaRita Dora PetraSusi 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 Erica Klarreich: A design dilemma solved, minus designs. Quanta Magazine 2015 Kirkman's Schoolgirl Problem, mathworld
Einzelnachweise
Kategorie:Kombinatorik Kategorie:Geschichte der Mathematik Kategorie:Unterhaltungsmathematik