TOPICS
Search

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.

KirkmansSchoolgirlProblem

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.

SunABCDEFGHIJKLMNO
MonADHBEKCIOFLNGJM
TueAEMBHNCGKDILFJO
WedAFIBLOCHJDKMEGN
ThuAGLBDJCFMEHOIKN
FriAJNBIMCELDOGFHK
SatAKOBFGCDNEIJHLM

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

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 J_2(4,2) (E. Pegg, Jr., pers. comm., Jan. 29, 2022).


See also

Grassmann Graph, Josephus Problem, Kirkman Triple System, Social Golfer Problem, Steiner Triple System

Explore with Wolfram|Alpha

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.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. Monthly 118, 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.

Cite this as:

Weisstein, Eric W. "Kirkman's Schoolgirl Problem." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/KirkmansSchoolgirlProblem.html

Subject classifications