Kirkman's schoolgirl problem
Kirkman's schoolgirl problem is a problem in combinatorics proposed by Thomas Penyngton Kirkman in 1850 as Query VI in The Lady's and Gentleman's Diary (pg.48).
The problem states: 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.
There are exactly seven non-isomorphic solutions to the schoolgirl problem, as originally listed by Frank Nelson Cole in Kirkman Parades in 1922.
[4] The seven solutions are summarized in the table below, denoting the 15 girls with the letters A to O.
This section is based on historical work done at different times by Robin Wilson[5] and by Louise Duffield Cummings.
[6] The history is as follows: James Joseph Sylvester in 1850 asked if 13 disjoint Kirkman systems of 35 triples each could be constructed to use all
No solution was found until 1974 when RHF Denniston at the University of Leicester constructed it with a computer.
He then asked an Elliott 4130 computer to do exactly that search, which took him 7 hours to find this first-week solution,[22] labeling the 15 girls with the letters A to O: He stopped the search at that point, not looking to establish uniqueness.
[22] The American minimalist composer Tom Johnson composed a piece of music called Kirkman's Ladies based on Denniston's solution.
The equivalent of the Kirkman problem for 9 schoolgirls results in S(2,3,9), an affine plane isomorphic to the following triples on each day: The corresponding Sylvester problem asks for 7 different S(2,3,9) systems of 12 triples each, together covering all
This solution was known to Bays (1917) which was found again from a different direction by Earl Kramer and Dale Mesner in a 1974 paper titled Intersections Among Steiner Systems (J Combinatorial Theory, Vol 16 pp 273-285).
There can indeed be 7 disjoint S(2,3,9) systems, and all such sets of 7 fall into two non-isomorphic categories of sizes 8640 and 6720, with 42 and 54 automorphisms respectively.
[26] In 1910 the problem was addressed using Galois geometry by George Conwell.
A plane can be considered a complete quadrilateral together with the line through its diagonal points.
When Hirschfeld considered the problem in his Finite Projective Spaces of Three Dimensions (1985), he noted that some solutions correspond to packings of PG(3,2), essentially as described by Conwell above,[28]: 91 and he presented two of them.
days, with the requirement, again, that no pair of girls walk in the same row twice.
[29] It is this generalization of the problem that Kirkman discussed first, while the famous special case
Alan Hartman solves a problem of this type with the requirement that no trio walks in a row of four more than once[34] using Steiner quadruple systems.
More recently a similar problem known as the Social Golfer Problem has gained interest that deals with 32 golfers who want to get to play with different people each day in groups of 4, over the course of 10 days.
