Kirkman's schoolgirl problem

Kirkman's schoolgirl problem is a problem in combinatorics proposed by Thomas Kirkman in 1850 as Query VI in "The Lady's and Gentleman's Diary". 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.cite book |last= Graham |first= Ronald L. |authorlink= Ronald Graham |coauthors= Martin Grötschel, László Lovász |title= Handbook of Combinatorics, Volume 2 |year= 1995 |publisher= The MIT Press |location= Cambridge, MA |isbn= 0-262-07171-1 ]

Solution

If the girls are numbered from 01 to 15, the following arrangement is one solution:

A solution to this problem is an example of a Kirkman triple system.MathWorld |title= Kirkman's Schoolgirl Problem |urlname= KirkmansSchoolgirlProblem]

Generalization

The problem can be generalized to $n$ girls, where $n$ is an odd multiple of 3, walking in triplets for

:$frac\{1\}\{2\}(n-1)$

days, with the requirement, again, that no pair of girls walk in the same row twice. The solution to this generalisation is a Steiner triple system

:"S"(2, 3, 6"t" + 3)

with parallelism (that is, one in which each of the 6"t" + 3 elements occurs exactly once in each block of 3-element sets).cite book |last= Ball |first= W.W. Rouse |authorlink= W. W. Rouse Ball |coauthors= H.S.M. Coxeter |title=Mathematical Recreations & Essays |year= 1974 |publisher= University of Toronto Press |location= Toronto and Buffalo |isbn= 0-8020-1844-0] It is this generalization of the problem which Kirkman first discussed, with the particular case $n=15$ proposed later. cite journal |last= Kirkman |first=Thomas P. |authorlink= Thomas Kirkman |title= On a Problem in Combinations |journal= The Cambridge and Dublin Mathematical Journal |volume= II |pages= 191–204 | publisher = Macmillan, Barclay, and Macmillan |date= 1847] A complete solution to the general case was given by D. K. Ray-Chaudhuri and R. M. Wilson in 1969.

References