The schoolgirl problem of Reverend Kirkman (1806-1895)


"Fifteen young ladies in a school walk out three abreast for seven days in succession; it is required to arrange them daily, so that no two will walk twice abreast."

This question, posed by Reverend Kirkman in the middle of the previous century, has stimulated mathematics for a long time and finally led to the development of the concept of a design. In mathematical language, we look for a design on 15 points with block length 3, such that every pair of points is contained in at most one block - in fact, it turns out that (15 \choose 2) = 7 · 5 · (3 \choose 2), so every pair of points is contained in exactly one block.

One solution of the problem is given by the following picture:

The following table gives one of the possible solutions you can find within the picture. The suggested numbering of the points is the following: consider the outer circle; the point at the top is labelled 1, then the other points of the outer circle are labelled counterclockwise from 2 to 7. The same procedure labels the points of the inner circle with 8, ..., 14; finally, the central point is labelled 15.

Monday's constellation consists of 5 different kinds of lines in the picture covering all points (i.e. ladies). The constellations of the other days we receive by rotating this constellation counterclockwise each day by one step.


Monday
Tuesday
Wednesday
Thursday
Friday
Saturday
Sunday
{1, 2, 4}
{2, 3, 5}
{3, 4, 6}
{4, 5, 7}
{1, 5, 6}
{2, 6, 7}
{1, 3, 7}
{3, 11, 13}
{4, 12, 14}
{5, 8, 13}
{6, 9, 14}
{7, 8, 10}
{1, 9, 11}
{2, 10, 12}
{5, 9, 10}
{6, 10, 11}
{7, 11, 12}
{1, 12, 13}
{2, 13, 14}
{3, 8, 14}
{4, 8, 9}
{6, 8, 12}
{7, 9, 13}
{1, 10, 14}
{2, 8, 11}
{3, 9, 12}
{4, 10, 13}
{5, 11, 14}
{7, 14, 15}
{1, 8, 15}
{2, 9, 15}
{3, 10, 15}
{4, 11, 15}
{5, 12, 15}
{6, 13, 15}


In mathematical language we have a 2-(15, 3, 1) design: our pointset is V = {1, ..., 15} and we consider blocks of length 3 (there are 5 · 7 = 35 blocks). The important property of these blocks is that each pair of points - we have (15 \choose 2) = 105 of them - is contained in exactly lambda = 1 block.

Another interesting fact is the property, that the 5 blocks forming the constellation for one day give a partition of the 15 points. That's fairly good for the ladies!


Back to the DISCRETA homepage
last updated: August 31, 1999, Evi Haberberger