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.
Solutions
A solution to this problem is an example of a Kirkman triple system, which is a Steiner triple system having a parallelism, that is, a partition of the blocks of the triple system into parallel classes which are themselves partitions of the points into disjoint blocks. Such Steiner systems that have a parallelism are also called resolvable.
There are exactly seven non-isomorphic solutions to the schoolgirl problem, as originally listed by Frank Nelson Cole in Kirkman Parades in 1922. The seven solutions are summarized in the table below, denoting the 15 girls with the letters A to O.
From the number of automorphisms for each solution and the definition of an automorphism group, the total number of solutions including isomorphic solutions is therefore:
.
History
The problem has a long and storied history. This section is based on historical work done at different times by Robin Wilson and by Louise Duffield Cummings. The history is as follows:
In 1844, Wesley Woolhouse, the editor of The Lady's and Gentleman's Diary at the time, asked the general question: "Determine the number of combinations that can be made out of n symbols, p symbols in each; with this limitation, that no combination of q symbols, which may appear in any one of them shall be repeated in any other." Only two answers were received, one incorrect and the other correctly answering the question with . As the question did not ask for anything more than the number of combinations, nothing was received about the conditions on n, p, or q when such a solution could be achieved.
In 1846, Woolhouse asked: "How many triads can be made out of n symbols, so that no pair of symbols shall be comprised more than once among them?". This is equivalent to repeating his 1844 question with the values p = 3 and q = 2.
In 1847, at age 41, Thomas Kirkman published his paper titled On a Problem in Combinations which comprehensively described and solved the problem of constructing triple systems of order n where n = 1 or 3 (mod 6). He also considered other values of n even though perfect balance would not be possible. He gave two different sequences of triple systems, one for n = 7, 15, 19, 27, etc., and another for n = 9, 13, 25, etc. Using these propositions, he proved that triple systems exist for all values of n = 1 or 3 (mod 6) (not necessarily resolvable ones, but triple systems in general). He also described resolvable triple systems in detail in that paper, particularly for n = 9 and 15; resolvable triple systems are now known as Kirkman triple systems. He could not conclusively say for what other values of n would resolvable triple systems exist; that problem would not be solved until the 1960s (see below).
In 1850, Kirkman posed the 15 schoolgirl problem, which would become much more famous than the 1847 paper he had already written. Several solutions were received. Kirkman himself gave a solution that later would be found to be isomorphic to Solution I above. Kirkman claimed it to be the only possible solution but that was incorrect. Arthur Cayley's solution would be later found to be isomorphic to Solution II. Both solutions could be embedded in PG(3,2) though that geometry was not known at the time. However, in publishing his solutions to the schoolgirl problem, Kirkman neglected to refer readers to his own 1847 paper, and this omission would have serious consequences for invention and priority as seen below.
Also in 1850, James Joseph Sylvester asked if there could be 13 different solutions to the 15-schoolgirl problem that would use all triples exactly once overall, observing that . In words, is it possible for the girls to march every day for 13 weeks, such that every two girls march together exactly once each week and every three girls march together exactly once in the term of 13 weeks? This problem was much harder, and a computational solution would finally be provided in 1974 by RHF Denniston (see below).