Navigation Panel: Previous | Up | Forward | Graphical Version | PostScript version | SIMMER Home Page | Fields Institute Home | U of T Math Network Home


March 1997 Presentation Topic (continued)

Kirkman's Schoolgirl Problem

This was posed by the Rev. Kirkman in 1850:
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?
This problem is actually the same as the second part of question 6 above. Stated abstractly, the problem is to find a resolvable combinatorial design in which v=15, b=35, k=3, and r=7. The construction of this design involves an interesting mixture of the patterns in the Fano Plane and the patterns in the n=8 solution to the Tournament Scheduling Problem. We outline below how the design is constructed.

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.

Navigation Panel: 

  Go backward to Delving Into The Concepts
  Go up to Introduction and Contents
  Go forward to References
  Switch to graphical version (better pictures & formulas)
  Access printed version in PostScript format (requires PostScript printer)
  Go to SIMMER Home Page
  Go to The Fields Institute Home Page
  Go to University of Toronto Mathematics Network Home Page