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 15.
The visualization above represents each day's five triples by arcs of one color, using seven colors in all (E. Pegg, Jr., pers. comm., Jan. 29, 2022). The
illustrated solution is isomorphic to system 1a in
the classification of Pavone (2023, p. 10). Falcone and Pavone (2011) give visual
solutions of systems 1a and 1b based on a tetrahedron.
Pavone (2023, pp. 9-15) gives visual solutions representing all seven non-isomorphic
systems.
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 in the illustrated solution as a graph vertex 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 Combinations."
Cambridge and Dublin Math. J.2, 191-204, 1847.Kirkman,
T. P. Lady's and Gentleman's Diary. 1850.Pavone, M. "On
the Seven Non-Isomorphic Solutions of the Fifteen Schoolgirl Problem." Disc.
Math.346, 113316, 2023. https://doi.org/10.1016/j.disc.2023.113316.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.
and 
entries for Wednesday and Thursday are written simply
as 
.)
(E. Pegg, Jr., pers. comm., Jan. 29, 2022).
