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 spazieren sieben Tage hintereinander in Dreiergruppen, man teile sie täglich so ein, dass keine zwei Schulmädchen zweimal zusammen spazieren.“
Das Problem wurde 1850 von Kirkman in der Zeitschrift für Unterhaltungsmathematik The Lady’s and Gentleman’s Diary gestellt[1] und Lösungen wurden von Arthur Cayley[2] und Kirkman selbst gegeben.[3] 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.
Das Problem ist ein Spezialfall von Steiner-Systemen 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. 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.[4][5]
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[6] und 2014 wurde sogar allgemeiner ein Existenzbeweis für zulässige Blockpläne von Peter Keevash gegeben. Es gibt nicht für jedes n und jede Kombination von Parametern Lösungen, gewissen natürliche Teilbarkeitsbedingungen müssen erfüllt sein, zum Beispiel muss n durch 3 teilbar sein.[7] Sind diese Bedingungen aber erfüllt, konnte Wilson die Existenz einer Lösung beweisen. Die Anzahl der Lösungen nimmt mit n exponentiell zu. Bei 19 Schulmädchen gibt es bereits über elf Milliarden Möglichkeiten der Einteilung in Dreiergruppen unter der geforderten Bedingung, dass jede Schülerin genau einmal in Anwesenheit jeder anderen in einer Dreiergruppe spaziert.
Kirkmans Schulmädchenproblem war der Beginn der Entwicklung der Theorie der Blockpläne oder kombinatorischen Designs.
Weblinks
Einzelnachweise
- ↑ Query VI, in: The Lady’s and Gentleman’s Diary for the year 1850, S. 48
- ↑ Dayley: 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
- ↑ 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.
- ↑ 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
- ↑ Wenn die Anzahl Schulmädchen nicht ganzzahlig durch 3 teilbar ist, geht nicht jedes Mädchen jeden Tag spazieren.