schoolgirls problem

The schoolgirls problem is a problem in combinatorics posed by the Thomas Kirkman in 1847:1


A school mistress has fifteen girl pupils and she wishes to take them on a daily walk. The girls are to walk in five rows of three girls each. It is required that no two girls should walk in the same row more than once per week. Can this be done?


In fact, provided n is divisible by 3, we can ask the more general question about n schoolgirls walking for (n - 1)/2 days so that no girl walks with any other girl in the same triplet more than once. Solutions for n = 9, 15, and 27 were given in 1850 and much work was done on the problem thereafter. It is important in the modern theory of combinatorics.



1. Kirkman, T. P. "On a Problem in Combinatorics." Cambridge and Dublin Math. J., 2: 191-204 (1847).