Kirkman's Schoolgirl Problem

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?

Divide the fifteen points of the desired resolvable combinatorial design up into a group of seven (1,2,3,4,5,6,7) and a group of eight (8,9,10,11,12,13,14,15).

On the group of seven construct a Fano Plane. By this I mean take the blocks of the Fano Plane that you found earlier, except now the numbers refer to girls instead of wheat varieties.

Next, construct a tournament schedule for eight teams named 8, 9, 10, 11, 12, 13, 14, and 15. Take the 28 different games played to be additional blocks, except now the numbers will refer to girls instead of sports teams.

Now what we have is seven blocks of size 3 and twenty-eight blocks of size 2. This is a total of 35 blocks, which is exactly how many we need (from the necessary conditions), but we need them all to be of size three. The solution is this. To each block of size two, we add the girl whose number is the same number as the day that game was played. This gives us 35 blocks of size three.

Question 7. Show that every pair appears together in the same block exactly once, proving that we have a combinatorial design.

Finally, we need to show that this combinatorial design is resolvable.

Question 8. Find a way to allocate these 35 blocks of girls into seven groups (days) of five blocks each, such that every girl appears exactly once in each group. Use this to write down a schedule which solves Kirkman's Schoolgirl Problem.

For further reading on Combinatorial Designs try these books.