Kirkman's schoolgirl problem

From Wikipedia, the free encyclopedia

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.^[1]

[edit] Solution

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

Sun.	Mon.	Tues.	Wed.	Thurs.	Fri.	Sat.
01, 06, 11	01, 02, 05	02, 03, 06	05, 06, 09	03, 05, 11	05, 07, 13	11, 13, 04
02, 07, 12	03, 04, 07	04, 05, 08	07, 08, 11	04, 06, 12	06, 08, 14	12, 14, 05
03, 08, 13	08, 09, 12	09, 10, 13	12, 13, 01	07, 09, 15	09, 11, 02	15, 02, 08
04, 09, 14	10, 11, 14	11, 12, 15	14, 15, 03	08, 10, 01	10, 12, 03	01, 03, 09
05, 10, 15	13, 15, 06	14, 01, 07	02, 04, 10	13, 14, 02	15, 01, 04	06, 07, 10

A solution to this problem is an example of a Kirkman triple system.^[3]

[edit] 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, 6t + 3)

with parallelism (that is, one in which each of the 6t + 3 elements occurs exactly once in each block of 3-element sets).^[2] It is this generalization of the problem which Kirkman first discussed, with the particular case $n = 15$ proposed later.^[4] A complete solution to the general case was given by D. K. Ray-Chaudhuri and R. M. Wilson in 1969.^[2]

[edit] References

^ Graham, Ronald L.; Martin Grötschel, László Lovász (1995). Handbook of Combinatorics, Volume 2. Cambridge, MA: The MIT Press. ISBN 0-262-07171-1.
^ ^a ^b ^c Ball, W.W. Rouse; H.S.M. Coxeter (1974). Mathematical Recreations & Essays. Toronto and Buffalo: University of Toronto Press. ISBN 0-8020-1844-0.
^ Eric W. Weisstein, Kirkman's Schoolgirl Problem at MathWorld.
^ Kirkman, Thomas P. (1847). "On a Problem in Combinations". The Cambridge and Dublin Mathematical Journal II: 191–204. Macmillan, Barclay, and Macmillan.