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 .
Falcone and Pavone (2011) give a number of attractive visualizations together with a visual proof of the problem. The visualization above shows a solution with each day's triples as a set of (seven) differently colored arcs (E. Pegg, Jr., pers. comm., Jan. 29, 2022).
The following table gives one of the 7 distinct (up to permutations of letters) solutions to the problem.
Sun
ABC
DEF
GHI
JKL
MNO
Mon
ADH
BEK
CIO
FLN
GJM
Tue
AEM
BHN
CGK
DIL
FJO
Wed
AFI
BLO
CHJ
DKM
EGN
Thu
AGL
BDJ
CFM
EHO
IKN
Fri
AJN
BIM
CEL
DOG
FHK
Sat
AKO
BFG
CDN
EIJ
HLM
(The table of Dörrie 1965 contains four omissions in which the and entries for Wednesday and Thursday are written simply
as .)
Interestingly, treating each of the 35 triples that solve the problem as the vertex of a graph and drawing edges between vertices that share a schoolgirl results in
a graph that is isomorphic to the Grassmann graph
(E. Pegg, Jr., pers. comm., Jan. 29, 2022).
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.Carpmael.
Proc. London Math. Soc.12, 148-156, 1881.Cole, F. N.
"Kirkman Parades." Bull. Amer. Math. Soc.28, 435-437, 1922.Dörrie,
H. §5 in 100
Great Problems of Elementary Mathematics: Their History and Solutions. New
York: Dover, pp. 14-18, 1965.Falcone, G. and Pavone, M. "Kirkman's
Tetrahedron and the Fifteen Schoolgirl Problem." Amer. Math. Monthly118,
887-900, 2011.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.Woolhouse.
Lady's and Gentleman's Diary. 1862-1863.