Kirkman's schoolgirl problem
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.
If the girls are numbered from 0 to 14, the following arrangement is one solution:
|0, 5, 10||0, 1, 4||1, 2, 5||4, 5, 8||2, 4, 10||4, 6, 12||10, 12, 3|
|1, 6, 11||2, 3, 6||3, 4, 7||6, 7, 10||3, 5, 11||5, 7, 13||11, 13, 4|
|2, 7, 12||7, 8, 11||8, 9, 12||11, 12, 0||6, 8, 14||8, 10, 1||14, 1, 7|
|3, 8, 13||9, 10, 13||10, 11, 14||13, 14, 2||7, 9, 0||9, 11, 2||0, 2, 8|
|4, 9, 14||12, 14, 5||13, 0, 6||1, 3, 9||12, 13, 1||14, 0, 3||5, 6, 9|
A solution to this problem is an example of a Kirkman triple system, 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.
There are seven non-isomorphic solutions to the schoolgirl problem. Two of these can be visualized as relations between a tetrahedron and its vertices, edges, and faces. An approach using projective geometry of three dimensions over GF(2) is given below.
XOR Triple Solution
This section does not cite any sources. (December 2018) (Learn how and when to remove this template message)
If the girls are numbered in binary numbers 0001 to 1111, the following arrangement is one solution such that for any three girls that form a group, the bitwise XOR of any two is equal to the third:
|0001, 0010, 0011||0001, 0100, 0101||0001, 0110, 0111||0001, 1000, 1001||0001, 1010, 1011||0001, 1100, 1101||0001, 1110, 1111|
|0100, 1000, 1100||0010, 1000, 1010||0010, 1001, 1011||0010, 1100, 1110||0010, 1101, 1111||0010, 0100, 0110||0010, 0101, 0111|
|0101, 1010, 1111||0011, 1101, 1110||0011, 1100, 1111||0011, 0101, 0110||0011, 0100, 0111||0011, 1001, 1010||0011, 1000, 1011|
|0110, 1011, 1101||0110, 1001, 1111||0100, 1010, 1110||0100, 1011, 1111||0101, 1001, 1100||0101, 1011, 1110||0100, 1001, 1101|
|0111, 1001, 1110||0111, 1011, 1100||0101, 1000, 1101||0111, 1010, 1101||0110, 1000, 1110||0111, 1000, 1111||0110, 1010, 1100|
This solution has a geometric interpretation in connection with Galois geometry and PG(3,2). Take a tetrahedron and label its vertices as 0001, 0010, 0100 and 1000. Label its six edge centers as the XOR of the vertices of that edge. Label the four face centers as the XOR of the three vertices of that face, and the body center gets the label 1111. Then the 35 triads of the XOR solution correspond exactly to the 35 lines of PG(3,2). Each day corresponds to a spread and each week to a packing.
The first solution was published by Arthur Cayley. This was shortly followed by Kirkman's own solution which was given as a special case of his considerations on combinatorial arrangements published three years prior. J. J. Sylvester also investigated the problem and ended up declaring that Kirkman stole the idea from him. The puzzle appeared in several recreational mathematics books at the turn of the century by Lucas, Rouse Ball, Ahrens, and Dudeney.
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.: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".: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.: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.:74
Spreads and packing
A partition of points into lines is called a spread, and the partition of the spreads of a geometry is called a packing.:66 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,:91 and he presented two of them.:75
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. It is this generalization of the problem that Kirkman discussed first, while the famous special case was only proposed later. A complete solution to the general case was published by D. K. Ray-Chaudhuri and R. M. Wilson in 1968, though it had already been solved by Lu Jiaxi (Chinese: 陆家羲) in 1965, but had not been published at that time.
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 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.
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.
- Cooperative learning strategy for increasing interaction within classroom teaching
- Progressive dinner party designs
- Speed Networking events
- Sports Competitions
- Graham, Grötschel & Lovász 1995
- Ball & Coxeter 1987, pp. 287−289
- Weisstein, Eric W. "Kirkman's Schoolgirl Problem". MathWorld.
- Cole, F.W. (1922), "Kirkman parades", Bulletin of the American Mathematical Society, 28: 435–437, doi:10.1090/S0002-9904-1922-03599-9
- Falcone, Giovanni; Pavone, Marco (2011), "Kirkman's Tetrahedron and the Fifteen Schoolgirl Problem", American Mathematical Monthly, 118: 887–900, doi:10.4169/amer.math.monthly.118.10.887
- Cayley, A. (1850), "On the triadic arrangements of seven and fifteen things", Philosophical Magazine, 37: 50–53, doi:10.1080/14786445008646550
- Kirkman 1850
- Kirkman 1847
- Lucas 1883, pp. 183–188
- Rouse Ball 1892
- Ahrens 1901
- Dudeney 1917
- Cummings 1918
- George M. Conwell (1910) "The 3-space PG(3,2) and its Groups", Annals of Mathematics 11:60–76 doi:10.2307/1967582
- Hirschfeld, J.W.P. (1985), Finite Projective Spaces of Three Dimensions, Oxford University Press, ISBN 0-19-853536-8
- Ray-Chaudhuri & Wilson 1971
- Lu 1990
- Colbourn & Dinitz 2007, p. 13
- Hartman 1980
- van Dam, E. R., Haemers, W. H., & Peek, M. B. M. (2003). Equitable resolvable coverings. Journal of Combinatorial Designs, 11(2), 113-123.
- Bryant & Danziger 2011
- Ahrens, W. (1901), Mathematische Unterhaltungen und Spiele, Leipzig: Teubner
- Bryant, Darryn; Danziger, Peter (2011), "On bipartite 2-factorizations of and the Oberwolfach problem" (PDF), Journal of Graph Theory, 68 (1): 22–37, doi:10.1002/jgt.20538, MR 2833961
- Colbourn, Charles J.; Dinitz, Jeffrey H. (2007), Handbook of Combinatorial Designs (2nd ed.), Boca Raton: Chapman & Hall/ CRC, ISBN 1-58488-506-8
- Cummings, L.D. (1918), "An undervalued Kirkman paper", Bulletin of the American Mathematical Society, 24: 336–339, doi:10.1090/S0002-9904-1918-03086-3
- Dudeney, H.E. (1917), Amusements in Mathematics, New York: Dover
- Graham, Ronald L.; Grötschel, Martin; Lovász, László (1995), Handbook of Combinatorics, Volume 2, Cambridge, MA: The MIT Press, ISBN 0-262-07171-1
- Hartman, Alan (1980), "Kirkman's trombone player problem", Ars Combinatoria, 10: 19–26
- Lu, Jiaxi (1990), Collected Works of Lu Jiaxi on Combinatorial Designs, Huhhot: Inner Mongolia People's Press
- Kirkman, Thomas P. (1847), "On a Problem in Combinations", The Cambridge and Dublin Mathematical Journal, Macmillan, Barclay, and Macmillan, II: 191–204
- Kirkman, Thomas P. (1850), "Note on an unanswered prize question", The Cambridge and Dublin Mathematical Journal, Macmillan, Barclay and Macmillan, 5: 255–262
- Lucas, É. (1883), Récréations Mathématiques, 2, Paris: Gauthier-Villars, pp. 183–188
- Ray-Chaudhuri, D.K.; Wilson, R.M. (1971), "Solution of Kirkman's schoolgirl problem, in Combinatorics, University of California, Los Angeles, 1968", Proceedings of Symposia in Pure Mathematics, Providence, Rhode Island: American Mathematical Society, XIX: 187–203, doi:10.1090/pspum/019/9959, ISBN 978-0-8218-1419-2
- Rouse Ball, W.W. (1892), Mathematical Recreations and Essays, London: Macmillan