Kirkman's Schoolgirl Problem

In a boarding school there are fifteen schoolgirls who always take their daily walks in rows of threes. How can it be arranged so that each schoolgirl walks in the same row with every other schoolgirl exactly once a week? Solution of this problem is equivalent to constructing a Kirkman Triple System of order $n=2$. The following table gives one of the 7 distinct (up to permutations of letters) solutions to the problem.

Sun	Mon	Tue	Wed	Thu	Fri	Sat
ABC	ADE	AFG	AHI	AJK	ALM	ANO
DHL	BIK	BHJ	BEG	BDF	BEF	BDG
EJN	CMO	CLN	CMN	CLO	CIJ	CHK
FIO	FHN	DIM	DJO	EHM	DKN	EIL
GKM	GJL	EKO	FKL	GIN	GHO	FJM

(The table of Dörrie 1965 contains a misprint in which the $a_1=B$ and $a_2=C$ entries for Wednesday and Thursday are written simply as $a$.)

See also Josephus Problem, Kirkman Triple System, Steiner Triple System

References

Abel, R. J. R. and Furino, S. C. ``Kirkman Triple Systems.'' §I.6.3 in The CRC Handbook of Combinatorial Designs (Ed. C. J. Colbourn and J. H. Dinitz). Boca Raton, FL: CRC Press, pp. 88-89, 1996.

Ball, W. W. R. and Coxeter, H. S. M. Mathematical Recreations and Essays, 13th ed. New York: Dover, pp. 287-289, 1987.

Dörrie, H. §5 in 100 Great Problems of Elementary Mathematics: Their History and Solutions. New York: Dover, pp. 14-18, 1965.

Frost, A. ``General Solution and Extension of the Problem of the 15 School Girls.'' Quart. J. Pure Appl. Math. 11, 26-37, 1871.

Kirkman, T. P. ``On a Problem in Combinatorics.'' Cambridge and Dublin Math. J. 2, 191-204, 1847.

Kirkman, T. P. Lady's and Gentleman's Diary. 1850.

Kraitchik, M. §9.3.1 in Mathematical Recreations. New York: W. W. Norton, pp. 226-227, 1942.

Peirce, B. ``Cyclic Solutions of the School-Girl Puzzle.'' Astron. J. 6, 169-174, 1859-1861.

Ryser, H. J. Combinatorial Mathematics. Buffalo, NY: Math. Assoc. Amer., pp. 101-102, 1963.