Kirkman's schoolgirl problem

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search
Original publication of the problem

Kirkman's school girl problem is a problem in combinatorics proposed by Rev. Thomas Penyngton Kirkman in 1850 as Query VI in The Lady's and Gentleman's Diary (pg.48). The problem states:

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 shall walk twice abreast.[1]

Solutions[edit]

A solution to this problem is an example of a Kirkman triple system,[2] which is a Steiner triple system having a parallelism, that is, a partition of the blocks of the triple system into parallel classes which are themselves partitions of the points into disjoint blocks. Such Steiner systems that have a parallelism are also called resolvable.

There are exactly seven non-isomorphic solutions to the schoolgirl problem, as originally listed by Frank Nelson Cole in Kirkman Parades in 1922.[3] The seven solutions are summarized in the table below, denoting the 15 girls with the letters A to O.

Solution class Automorphism group Day 1 Day 2 Day 3 Day 4 Day 5 Day 6 Day 7
Solution I Order 168, generated by
(A K G E I L B)(C H M J N O D)
and
(A M L K O C D)(B H N G I E J).
Related to PG(3,2).
ABC
DEF
GHI
JKL
MNO
ADG
BEH
CJM
FKN
ILO
AEO
BIJ
CDN
FHL
GKM
AIM
BDL
CEK
FGO
HJN
AFJ
BKO
CGL
DHM
EIN
AHK
BGN
CFI
DJO
ELM
ALN
BFM
CHO
DIK
EGJ
Solution II Order 168, generated by
(A B I M F C J)(D N H K O L E)
and
(A J M I B F C)(D H G N K E O).
Related to PG(3,2).
ABC
DEF
GHI
JKL
MNO
ADG
BEH
CJM
FKN
ILO
AEO
BIJ
CDN
FHL
GKM
AFJ
BGN
CHO
DIK
ELM
AHK
BFM
CGL
DJO
EIN
AIM
BDL
CEK
FGO
HJN
ALN
BKO
CFI
DHM
EGJ
Solution III Order 24, generated by
(A H E)(B O K)(C F I)(D J L)(G N M)
and
(A J B M)(D L E O)(F I)(G K H N)
ABC
DEF
GHI
JKL
MNO
ADG
BEH
CJM
FKN
ILO
AEO
BIM
CDK
FGL
HJN
AFM
BGN
CHL
DJO
EIK
AHK
BFJ
CGO
DIN
ELM
AIJ
BDL
CEN
FHO
GKM
ALN
BKO
CFI
DHM
EGJ
Solution IV Order 24, generated by
(A J M)(C F I)(D E K)(H O L)
and
(A L B O)(C I)(D K E N)(G J H M)
ABC
DEF
GHI
JKL
MNO
ADG
BEH
CJM
FKN
ILO
AEO
BIM
CDK
FGL
HJN
AFM
BKO
CHL
DIN
EGJ
AHK
BGN
CFI
DJO
ELM
AIJ
BDL
CEN
FHO
GKM
ALN
BFJ
CGO
DHM
EIK
Solution V Tetrahedral group of order 12,
generated by
(A L)(B G)(E O)(F J)(H K)(I M)
and
(A B C)(D L G)(F J I)(E K H)
ABC
DEF
GHI
JKL
MNO
ADG
BEJ
CHM
FKN
ILO
AEM
BDL
CIK
FGO
HJN
AFH
BKM
CGL
DJO
EIN
AIJ
BGN
CEO
DHK
FLM
AKO
BFI
CDN
EHL
GJM
ALN
BHO
CFJ
DIM
EGK
Solution VI Tetrahedral group of order 12,
generated by
(A L)(B G)(E O)(H K)(F J)(I M)
and
(A B C)(D L G)(E K H)(F J I)
ABC
DEF
GHI
JKL
MNO
ADG
BEJ
CHM
FKN
ILO
AEM
BDL
CIK
FGO
HJN
AFH
BKM
CGL
DJO
EIN
AIJ
BHO
CDN
EGK
FLM
AKO
BGN
CFJ
DIM
EHL
ALN
BFI
CEO
DHK
GJM
Solution VII Order 21, generated by
(A B L C G D N)(E H K I O J F)
and
(B G L)(C D N)(E F K)(H I O)
ABC
DEF
GHI
JKL
MNO
ADG
BEJ
CHM
FKN
ILO
AEI
BDN
CJO
FHL
GKM
AFO
BIK
CGN
DHJ
ELM
AHK
BFM
CDL
EGO
IJN
AJM
BGL
CFI
DKO
EHN
ALN
BHO
CEK
FGJ
DIM

From the number of automorphisms for each solution and the definition of an automorphism group, the total number of solutions including isomorphic solutions is therefore:

.

History[edit]

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:

  • In 1844, Wesley Woolhouse, 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 only giving the numerical answer but said nothing about the conditions on n, p, or q when such a solution could be achieved.
  • In 1846, Woolhouse asked: "How many triads can be made out of n symbols, so that no pair of symbols shall be comprised more than once among them?". This is equivalent to repeating his 1844 question with the values p = 3 and q = 2.[4]
  • In 1847, at age 41, Thomas Kirkman published his paper titled On a Problem in Combinations (Kirkman 1847) which comprehensively described and solved the problem of constructing triple systems of order n where n = 1 or 3 (mod 6). He also considered other values of n even though perfect balance would not be possible. He gave two different sequences of triple systems, one for n = 7, 15, 19, 27, etc, and another for n = 9, 13, 25, etc. Using these propositions, he proved that triple systems exist for all values of n = 1 or 3 (mod 6)[6] (not necessarily resolvable ones, but triple systems in general). He also described resolvable triple systems in detail in that paper, particularly for n = 9 and 15; resolvable triple systems are now known as Kirkman triple systems. He could not conclusively say for what other values of n would resolvable triple systems exist; that problem would not be solved until the 1960s (see below).
  • In 1850, Kirkman posed the 15 schoolgirl problem, which would become much more famous than the 1847 paper he had already written. Several solutions were received. Kirkman himself gave a solution[7] that later would be found to be isomorphic to Solution I above. Kirkman claimed it to be the only possible solution but that was incorrect. Arthur Cayley's solution[8] would be later found to be isomorphic to Solution II. Both solutions could be embedded in PG(3,2) though that geometry was not known at the time.
  • Also in 1850, James Joseph Sylvester asked if there could be 13 different solutions to the 15-schoolgirl problem that would use all 15C3 = 455 triples exactly once overall, observing that 455 = 13 x 35. In words, is it possible for the girls to march every day for 13 weeks, such that every two girls march together exactly once each week and every three girls march together exactly once in the term of 13 weeks? This problem was much harder, and a computational solution would finally be provided in 1974 by RHF Denniston (see below).
  • In 1852, Robert Richard Anstice provided a cyclic solution, made by constructing the first day's five triples to be 0Gg, AbC, aDE, cef, BdF on the 15 symbols 0ABCDEFGabcdefg and then cyclically shifting each subsequent day by one letter while leaving 0 unchanged (uppercase staying uppercase and lowercase staying lowercase).[4] If the four triples without the 0 element (AbC, aDE, cef, BdF) are taken and uppercase converted to lowercase (abc, ade, cef, bdf) they form what would later be called the Pasch configuration. The Pasch configuration would become important in isomorph rejection techniques in the 20th century.
  • In 1853, Jakob Steiner, completely unaware of Kirkman's 1847 paper, published his paper titled Combinatorische Aufgabe which reintroduced the concept of triple systems but did not mention resolvability into separate parallel classes. Steiner noted that it is necessary for n to be 1 or 3 (mod 6) but left an open question as to when this would be realized, unaware that Kirkman had already settled that question in 1847. As this paper was more widely read by the European mathematical establishment, triple systems later became known as Steiner triple systems.[4]
  • In 1859, Michel Reiss answered the questions raised by Steiner, using both methodology and notation similar to Kirkman's 1847 work (without acknowledging Kirkman), that subsequent authors such as Louise Cummings have expressed their reservations about his originality.[9] Kirkman himself expressed his bitterness.
  • In 1860, Benjamin Peirce unified several disparate solutions presented thus far, and showed that there were three possible cyclic solution structures, one corresponding to Anstice's work, one based on Kirkman's solution, and one on Cayley's.[4]
  • In 1861, James Joseph Sylvester revisited the problem and tried to claim that he had invented it, that his Cambridge lectures had been the source of Kirkman's work. Kirkman quickly rebuffed his claims, stating that when he wrote his papers he had never been to Cambridge or heard of Sylvester's work.[4]
  • Until the early 20th century, Kirkman's 1847 paper was largely omitted from the mathematical literature, with credit for triple systems going largely to Steiner and others. In his lifetime, Kirkman would complain about his mathematical work being eclipsed by the popularity of the schoolgirl problem.[14] Kirkman had also had a falling out with Cayley and the Royal Society around 1862 over non-publication of a series of Kirkman's papers on group theory and polyhedra, which may have contributed to his being sidelined.
  • In 1918, Kirkman's serious mathematical work was brought back to wider attention by Louise Duffield Cummings in a paper titled An Undervalued Kirkman Paper[15] which discussed the early history and corrected the omission.
  • At about the same time, Cummings was working with Frank Nelson Cole and Henry Seely White on triple systems. This culminated in their 1919 paper Complete classification of triad systems on 15 elements[16] which was the first paper to lay out all 80 solutions to the Steiner triple system of size 15. These included both resolvable and non-resolvable systems.
  • In 1922, Cole published his paper Kirkman Parades[3] which listed for the first time all seven non-isomorphic solutions to the 15 schoolgirl problem, thus answering a long-standing question since the 1850s. The seven Kirkman solutions correspond to four different Steiner systems when resolvability into parallel classes is removed as a constraint. Three of the Steiner systems have two possible ways of being separated into parallel classes, meaning two Kirkman solutions each, while the fourth has only one, giving seven Kirkman solutions overall.
  • In 1974, RHF Denniston solved the Sylvester problem of constructing 13 disjoint Kirkman solutions and using them to cover all 455 triples on the 15 girls.[20] His solution is discussed below.

Sylvester's problem[edit]

James Joseph Sylvester in 1850 asked if 13 disjoint Kirkman systems of 35 triples each could be constructed to use all 15C3 = 455 triples on 15 girls. No solution was found until 1974 when RHF Denniston at the University of Leicester constructed it with a computer.[20] Denniston's insight was to create a single-week Kirkman solution in such a way that it could be permuted according to a specific permutation of cycle length 13 to create disjoint solutions for subsequent weeks; he chose a permutation with a single 13-cycle and two fixed points like (1 2 3 4 5 6 7 8 9 10 11 12 13)(14)(15). Under this permutation, a triple like 123 would map to 234, 345, ... (11, 12, 13), (12, 13, 1) and (13, 1, 2) before repeating. Denniston thus classified the 455 triples into 35 rows of 13 triples each, each row being the orbit of a given triple under the permutation.[20] In order to construct a Sylvester solution, no single-week Kirkman solution could use two triples from the same row, otherwise they would eventually collide when the permutation was applied to one of them. Solving Sylvester's problem is equivalent to finding one triple from each of the 35 rows such that the 35 triples together make a Kirkman solution. He then asked an Elliott 4130 computer to do exactly that search, which took him 7 hours to find this first-week solution,[20] labeling the 15 girls with the letters A to O:

Day 1 ABJ CEM FKL HIN DGO
Day 2 ACH DEI FGM JLN BKO
Day 3 ADL BHM GIK CFN EJO
Day 4 AEG BIL CJK DMN FHO
Day 5 AFI BCD GHJ EKN LMO
Day 6 AKM DFJ EHL BGN CIO
Day 7 BEF CGL DHK IJM ANO

He stopped the search at that point, not looking to establish uniqueness.[20]

The American minimalist composer Tom Johnson composed a piece of music called Kirkman's Ladies based on Denniston's solution.[21][22]

As of 2021, it is not known whether there are other non-isomorphic solutions to Sylvester's problem, or how many solutions there are.

9 schoolgirls and extensions[edit]

The equivalent of the Kirkman problem for 9 schoolgirls results in S(2,3,9), an affine plane isomorphic to the following triples on each day:

Day 1: 123 456 789
Day 2: 147 258 369
Day 3: 159 267 348
Day 4: 168 249 357

The corresponding Sylvester problem asks for 7 different S(2,3,9) systems of 12 triples each, together covering all 9C3 = 84 triples. This solution was known to Bays (1917) which was found again from a different direction by Earl Kramer and Dale Mesner in a 1974 paper titled Intersections Among Steiner Systems (J Combinatorial Theory, Vol 16 pp 273-285). There can indeed be 7 disjoint S(2,3,9) systems, and all such sets of 7 fall into two non-isomorphic categories of sizes 8640 and 6720, with 42 and 54 automorphisms respectively.

Solution 1:
             Day 1          Day 2          Day 3          Day 4
Week 1    ABC.DEF.GHI    ADG.BEH.CFI    AEI.BFG.CDH    AFH.BDI.CEG
Week 2    ABD.CEH.FGI    ACF.BGH.DEI    AEG.BCI.DFH    AHI.BEF.CDG
Week 3    ABE.CDI.FGH    ACG.BDF.EHI    ADH.BGI.CEF    AFI.BCH.DEG
Week 4    ABF.CEI.DGH    ACD.BHI.EFG    AEH.BCG.DFI    AGI.BDE.CFH
Week 5    ABG.CDE.FHI    ACH.BEI.DFG    ADI.BCF.EGH    AEF.BDH.CGI
Week 6    ABH.CDF.EGI    ACI.BDG.EFH    ADE.BFI.CGH    AFG.BCE.DHI
Week 7    ABI.CFG.DEH    ACE.BFH.DGI    ADF.BEG.CHI    AGH.BCD.EFI

Solution 1 has 42 automorphisms, generated by the permutations (A I D C F H)(B G) and (C F D H E I)(B G). Applying the 9! = 362880 permutations of ABCDEFGHI, there are 362880/42 = 8640 different solutions all isomorphic to Solution 1.

Solution 2:
             Day 1          Day 2          Day 3          Day 4
Week 1    ABC.DEF.GHI    ADG.BEH.CFI    AEI.BFG.CDH    AFH.BDI.CEG
Week 2    ABD.CEH.FGI    ACF.BGH.DEI    AEG.BCI.DFH    AHI.BEF.CDG
Week 3    ABE.CGH.DFI    ACI.BFH.DEG    ADH.BGI.CEF    AFG.BCD.EHI
Week 4    ABF.CGI.DEH    ACE.BDG.FHI    ADI.BCH.EFG    AGH.BEI.CDF
Week 5    ABG.CDI.EFH    ACH.BDF.EGI    ADE.BHI.CFG    AFI.BCE.DGH
Week 6    ABH.CEI.DFG    ACD.BFI.EGH    AEF.BCG.DHI    AGI.BDE.CFH
Week 7    ABI.CDE.FGH    ACG.BDH.EFI    ADF.BEG.CHI    AEH.BCF.DGI

Solution 2 has 54 automorphisms, generated by the permutations (A B D)(C H E)(F G I) and (A I F D E H)(B G). Applying the 9! = 362880 permutations of ABCDEFGHI, there are 362880/54 = 6720 different solutions all isomorphic to Solution 2.

Thus there are 8640 + 6720 = 15360 solutions in total, falling into two non-isomorphic categories.

In addition to S(2,3,9), Kramer and Mesner examined other systems that could be derived from S(5,6,12) and found that there could be up to 2 disjoint S(5,6,12) systems, up to 2 disjoint S(4,5,11) systems, and up to 5 disjoint S(3,4,10) systems. All such sets of 2 or 5 are respectively isomorphic to each other.

Larger systems and continuing research[edit]

In the 21st century, analogues of Sylvester's problem have been visited by other authors under terms like "Disjoint Steiner systems" or "Disjoint Kirkman systems" or "LKTS" (Large Sets of Kirkman Triple Systems), for n > 15.[23] Similar sets of disjoint Steiner systems have also been investigated for the S(5,8,24) Steiner system in addition to triple systems.[24]

Galois geometry[edit]

In 1910 the problem was addressed using Galois geometry by George Conwell.[25]

The Galois field GF(2) with two elements is used with four homogeneous coordinates to form PG(3,2) which has 15 points, 3 points to a line, 7 points and 7 lines in a plane. A plane can be considered a complete quadrilateral together with the line through its diagonal points. Each point is on 7 lines, and there are 35 lines in all.

The lines of PG(3,2) are identified by their Plücker coordinates in PG(5,2) with 63 points, 35 of which represent lines of PG(3,2). These 35 points form the surface S known as the Klein quadric. For each of the 28 points off S there are 6 lines through it which do not intersect S.[25]: 67

As there are seven days in a week, the heptad is an important part of the solution:

When two points as A and B of the line ABC are chosen, each of the five other lines through A is met by only one of the five other lines through B. The five points determined by the intersections of these pairs of lines, together with the two points A and B we designate a "heptad".[25]: 68

A heptad is determined by any two of its points. Each of the 28 points off S lies in two heptads. There are 8 heptads. The projective linear group PGL(3,2) is isomorphic the alternating group on the 8 heptads.[25]: 69

The schoolgirl problem consists in finding seven lines in the 5-space which do not intersect and such that any two lines always have a heptad in common.[25]: 74

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. However, this term is currently not commonly used and evidence suggests that there is no common name for the process.

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.[33]

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.[34]

Other applications[edit]

Notes[edit]

  1. ^ Graham, Grötschel & Lovász 1995
  2. ^ Weisstein, Eric W. "Kirkman's Schoolgirl Problem". MathWorld.
  3. ^ a b Cole, F.N. (1922), "Kirkman parades", Bulletin of the American Mathematical Society, 28 (9): 435–437, doi:10.1090/S0002-9904-1922-03599-9
  4. ^ a b c d e f The Early History of Block Designs by Robin Wilson, Dept of Pure Mathematics, The Open University, UK
  5. ^ Cummings 1918
  6. ^ Cummings 1918
  7. ^ Kirkman 1850
  8. ^ Cayley, A. (1850), "On the triadic arrangements of seven and fifteen things", Philosophical Magazine, 37 (247): 50–53, doi:10.1080/14786445008646550
  9. ^ Cummings 1918
  10. ^ Lucas 1883, pp. 183–188
  11. ^ Rouse Ball 1892
  12. ^ Ahrens 1901
  13. ^ Dudeney 1917
  14. ^ Cummings 1918
  15. ^ Cummings 1918
  16. ^ "Complete classification of triad systems on 15 elements" by Cole, Cummings and White
  17. ^ Lu 1990
  18. ^ Colbourn & Dinitz 2007, p. 13
  19. ^ Ray-Chaudhuri & Wilson 1971
  20. ^ a b c d e Denniston's solution to Sylvester's problem
  21. ^ Kirkman's Ladies audio
  22. ^ Scholarly article by Johnson and Jedrzjeweski
  23. ^ Junling Zhou and Yanxun Chang: A new result on Sylvester's Problem, Discrete MAthematics Vol 331, pp 15-19
  24. ^ Araya, Makoto & Harada, Masaaki. (2010). Mutually Disjoint Steiner Systems S(5, 8, 24) and 5-(24, 12, 48) Designs. Electr. J. Comb.. 17.
  25. ^ a b c d e Conwell, George M. (1910). "The 3-space PG(3,2) and its Group". Annals of Mathematics. 11 (2): 60–76. doi:10.2307/1967582. JSTOR 1967582.
  26. ^ a b c Hirschfeld, J.W.P. (1985), Finite Projective Spaces of Three Dimensions, Oxford University Press, ISBN 0-19-853536-8
  27. ^ Ball & Coxeter 1987, pp. 287−289
  28. ^ Kirkman 1847
  29. ^ Ray-Chaudhuri & Wilson 1971
  30. ^ Lu 1990
  31. ^ Colbourn & Dinitz 2007, p. 13
  32. ^ Hartman 1980
  33. ^ van Dam, E. R., Haemers, W. H., & Peek, M. B. M. (2003). Equitable resolvable coverings. Journal of Combinatorial Designs, 11(2), 113-123.
  34. ^ Bryant & Danziger 2011
  35. ^ McRobbie, Linda Rodriguez. "The Mind-Bending Math Behind Spot It!, the Beloved Family Card Game". Smithsonian Magazine. Retrieved 2020-03-01.

References[edit]

External links[edit]