Kirkman's schoolgirl problem
Kirkman's schoolgirl problem is a problem in combinatorics proposed by Thomas Penyngton Kirkman in 1850 as Query VI in The Lady's and Gentleman's Diary (pg.48). The problem states:
In 1844, , the editor of The Lady's and Gentleman's Diary at the time, asked the general question: "Determine the number of combinations that can be made out of n symbols, p symbols in each; with this limitation, that no combination of q symbols, which may appear in any one of them shall be repeated in any other." Only two answers were received, one incorrect and the other correctly answering the question with . As the question did not ask for anything more than the number of combinations, nothing was received about the conditions on n, p, or q when such a solution could be achieved.
Wesley Woolhouse
The problem has a long and storied history. This section is based on historical work done at different times by Robin Wilson[4] and by Louise Duffield Cummings.[5] The history is as follows:
Spreads and packing[edit]
In PG(3,2), a partition of the points into lines is called a spread, and a partition of the lines into spreads is called a packing or parallelism.[26]: 66 There are 56 spreads and 240 packings. When Hirschfeld considered the problem in his Finite Projective Spaces of Three Dimensions (1985), he noted that some solutions correspond to packings of PG(3,2), essentially as described by Conwell above,[26]: 91 and he presented two of them.[26]: 75
Generalization[edit]
The problem can be generalized to girls, where must be an odd multiple of 3 (that is ), walking in triplets for days, with the requirement, again, that no pair of girls walk in the same row twice. The solution to this generalisation is a Steiner triple system, an S(2, 3, 6t + 3) with parallelism (that is, one in which each of the 6t + 3 elements occurs exactly once in each block of 3-element sets), known as a Kirkman triple system.[27] It is this generalization of the problem that Kirkman discussed first, while the famous special case was only proposed later.[28] A complete solution to the general case was published by D. K. Ray-Chaudhuri and R. M. Wilson in 1968,[29] though it had already been solved by Lu Jiaxi (Chinese: 陆家羲) in 1965,[30] but had not been published at that time.[31]
Many variations of the basic problem can be considered. Alan Hartman solves a problem of this type with the requirement that no trio walks in a row of four more than once[32] using Steiner quadruple systems.
More recently a similar problem known as the Social Golfer Problem has gained interest that deals with 32 golfers who want to get to play with different people each day in groups of 4, over the course of 10 days.
As this is a regrouping strategy where all groups are orthogonal, this process within the problem of organising a large group into smaller groups where no two people share the same group twice can be referred to as orthogonal regrouping. [33]
The Resolvable Coverings problem considers the general girls, groups case where each pair of girls must be in the same group at some point, but we want to use as few days as possible. This can, for example, be used to schedule a rotating table plan, in which each pair of guests must at some point be at the same table.[34]
The Oberwolfach problem, of decomposing a complete graph into edge-disjoint copies of a given 2-regular graph, also generalizes Kirkman's schoolgirl problem. Kirkman's problem is the special case of the Oberwolfach problem in which the 2-regular graph consists of five disjoint triangles.[35]
