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 01 to 15, the following arrangement is one solution:
|01, 06, 11||01, 02, 05||02, 03, 06||05, 06, 09||03, 05, 11||05, 07, 13||11, 13, 04|
|02, 07, 12||03, 04, 07||04, 05, 08||07, 08, 11||04, 06, 12||06, 08, 14||12, 14, 05|
|03, 08, 13||08, 09, 12||09, 10, 13||12, 13, 01||07, 09, 15||09, 11, 02||15, 02, 08|
|04, 09, 14||10, 11, 14||11, 12, 15||14, 15, 03||08, 10, 01||10, 12, 03||01, 03, 09|
|05, 10, 15||13, 15, 06||14, 01, 07||02, 04, 10||13, 14, 02||15, 01, 04||06, 07, 10|
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 are packings of the finite projective space PG(3,2). A packing of a projective space is a partition of the lines of the space into spreads, and a spread is a partition of the points of the space into lines. These "packing" solutions can be visualized as relations between a tetrahedron and its vertices, edges, and faces.
A square, rather than tetrahedral, model may also be used:
For the origin of the square model, see the Cullinane diamond theorem.
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 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 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 20 golfers who want to get to play with different people each day in groups of 4.
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 isn't a common name for the process.
- Progressive dinner party designs
- Speed Networking events
- Cooperative learning strategy for increasing interaction within classroom teaching
- Sports Competitions
- (Graham, Grötschel & Lovász 1995)
- (Ball & Coxeter 1974)
- Weisstein, Eric W., "Kirkman's Schoolgirl Problem", MathWorld.
- (Cole 1922)
- (Hirschfeld 1985, pg.75)
- Falcone & Pavone 2011
- Cayley 1850
- Kirkman 1850
- Kirkman 1847
- Lucas 1883
- Rouse Ball 1892
- Ahrens 1901
- Dudeney 1917
- Cummings 1918
- Ray-Chaudhuri & Wilson 1971
- Jiaxi 1990
- Colbourn & Dinitz 2007, p. 13
- (Hartman 1980)
- Ahrens, W. (1901), Mathematische Unterhaltungen und Spiele, Leipzig: Teubner
- Ball, W.W. Rouse; H.S.M. Coxeter (1974), Mathematical Recreations & Essays, Toronto and Buffalo: University of Toronto Press, ISBN 0-8020-1844-0 Cite uses deprecated parameter
- Cayley, A. (1850), "On the triadic arrangements of seven and fifteen things", Phil. Mag. 37: 50–53, doi:10.1080/14786445008646550
- Colbourn, Charles J.; Dinitz, Jeffrey H. (2007), Handbook of Combinatorial Designs (2nd ed.), Boca Raton: Chapman & Hall/ CRC, ISBN 1-58488-506-8
- Cole, F.W. (1922), "Kirkman parades", Bulletin of the American Mathematical Society 28: 435–437, doi:10.1090/S0002-9904-1922-03599-9
- 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
- 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
- Graham, Ronald L.; Martin Grötschel, László Lovász (1995), Handbook of Combinatorics, Volume 2, Cambridge, MA: The MIT Press, ISBN 0-262-07171-1 Cite uses deprecated parameter
- Hartman, Alan (1980), "Kirkman's trombone player problem", Ars Combinatoria 10: 19–26
- Hirschfeld, J.W.P. (1985), Finite Projective Spaces of Three Dimensions, Oxford: Oxford University Press, ISBN 0-19-853536-8
- Jiaxi, Lu (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
- Ray-Chaudhuri, D.K.; Wilson, R.M. (1971), "Solution of Kirkman's schoolgirl problem, in Combinatorics, University of California, Los Angeles, 1968", Proc. Sympos. Pure Math. (Providence, R.I.: American Mathematical Society) XIX: 187–203
- Rouse Ball, W.W. (1892), Mathematical Recreations and Essays, London: Macmillan