Kirkman's schoolgirl problem is a problem in
combinatorics
Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many appl ...
proposed by Rev.
Thomas Penyngton Kirkman in 1850 as Query VI in ''
The Lady's and Gentleman's Diary
''The Lady's and Gentleman's Diary'' was a recreational mathematics magazine formed as a successor of ''The Ladies' Diary'' and ''Gentleman's Diary'' in 1841. It was published annually between 1841 and 1871 by the Company of Stationers; its editor ...
'' (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.
Solutions
A solution to this problem is an example of a ''Kirkman triple system'',
which is a
Steiner triple system
250px, thumbnail, The Fano plane is a Steiner triple system S(2,3,7). The blocks are the 7 lines, each containing 3 points. Every pair of points belongs to a unique line.
In combinatorial mathematics, a Steiner system (named after Jakob Steiner) ...
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
In mathematics, an isomorphism is a structure-preserving mapping between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between them. The word is ...
solutions to the schoolgirl problem, as originally listed by
Frank Nelson Cole
Frank Nelson Cole (September 20, 1861 – May 26, 1926) was an American mathematician.
Life and works
Cole was born in Ashland, Massachusetts. When he was very young, the family moved to Marlborough, Massachusetts where he attended school and ...
in ''Kirkman Parades'' in 1922.
The seven solutions are summarized in the table below, denoting the 15 girls with the letters A to O.
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:
= 404,756,352,000
.
History
![LGDiary CoverAndPage](https://upload.wikimedia.org/wikipedia/commons/5/5f/LGDiary_CoverAndPage.jpg)
The problem has a long and storied history. This section is based on historical work done at different times by
Robin Wilson[''The Early History of Block Designs'' by Robin Wilson, Dept of Pure Mathematics, The Open University, UK] and by
Louise Duffield Cummings. The history is as follows:
* In 1844,
Wesley Woolhouse, the editor of
The Lady's and Gentleman's Diary
''The Lady's and Gentleman's Diary'' was a recreational mathematics magazine formed as a successor of ''The Ladies' Diary'' and ''Gentleman's Diary'' in 1841. It was published annually between 1841 and 1871 by the Company of Stationers; its editor ...
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.
* 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.
* In 1847, at age 41, Thomas Kirkman published his paper titled ''On a Problem in Combinations'' 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) (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 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
Arthur Cayley (; 16 August 1821 – 26 January 1895) was a prolific United Kingdom of Great Britain and Ireland, British mathematician who worked mostly on algebra. He helped found the modern British school of pure mathematics.
As a child, C ...
's solution would be later found to be isomorphic to Solution II. Both solutions could be embedded in
PG(3,2)
In finite geometry, PG(3,2) is the smallest three-dimensional projective space. It can be thought of as an extension of the Fano plane.
It has 15 points, 35 lines, and 15 planes. It also has the following properties:
* Each point is contained in 7 ...
though that geometry was not known at the time. However, in publishing his solutions to the schoolgirl problem, Kirkman neglected to refer readers to his own 1847 paper, and this omission would have serious consequences for invention and priority as seen below.
* Also in 1850,
James Joseph Sylvester
James Joseph Sylvester (3 September 1814 – 15 March 1897) was an English mathematician. He made fundamental contributions to matrix theory, invariant theory, number theory, partition theory, and combinatorics. He played a leadership ro ...
asked if there could be 13 different solutions to the 15-schoolgirl problem that would use all
triples exactly once overall, observing that
. 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
RHF may refer to:
* Regional health authority (Norway), Regional health authority or ''Regionalt helseforetak'', of Norway
* Ice Hockey Federation of Russia (Russian Hockey Federation)
* Residence Hall Federation at Virginia Tech campus#Residence ...
(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).
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 th
Pasch configuration The Pasch configuration would become important in isomorph rejection techniques in the 20th century.
* In 1853,
Jakob Steiner
Jakob Steiner (18 March 1796 – 1 April 1863) was a Swiss mathematician who worked primarily in geometry.
Life
Steiner was born in the village of Utzenstorf, Canton of Bern. At 18, he became a pupil of Heinrich Pestalozzi and afterwards st ...
, 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 system
250px, thumbnail, The Fano plane is a Steiner triple system S(2,3,7). The blocks are the 7 lines, each containing 3 points. Every pair of points belongs to a unique line.
In combinatorial mathematics, a Steiner system (named after Jakob Steiner) ...
s.
* In 1859,
Michel Reiss answered the questions raised by Steiner, using both methodology and notation so similar to Kirkman's 1847 work (without acknowledging Kirkman), that subsequent authors such as Louise Cummings have called him out for
plagiarism
Plagiarism is the fraudulent representation of another person's language, thoughts, ideas, or expressions as one's own original work.From the 1995 '' Random House Compact Unabridged Dictionary'': use or close imitation of the language and thought ...
. Kirkman himself expressed his bitterness.
* In 1860,
Benjamin Peirce
Benjamin Peirce (; April 4, 1809 – October 6, 1880) was an American mathematician who taught at Harvard University for approximately 50 years. He made contributions to celestial mechanics, statistics, number theory, algebra, and the philoso ...
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.
* In 1861,
James Joseph Sylvester
James Joseph Sylvester (3 September 1814 – 15 March 1897) was an English mathematician. He made fundamental contributions to matrix theory, invariant theory, number theory, partition theory, and combinatorics. He played a leadership ro ...
revisited the problem and tried to claim that ''he'' had invented it, and 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.
This priority dispute led to a falling out between Sylvester and Kirkman.
* In 1861-1862, Kirkman had a falling out with
Arthur Cayley
Arthur Cayley (; 16 August 1821 – 26 January 1895) was a prolific United Kingdom of Great Britain and Ireland, British mathematician who worked mostly on algebra. He helped found the modern British school of pure mathematics.
As a child, C ...
over an unrelated matter (Cayley's choosing not to publish a series of papers by Kirkman on
group theory
In abstract algebra, group theory studies the algebraic structures known as group (mathematics), groups.
The concept of a group is central to abstract algebra: other well-known algebraic structures, such as ring (mathematics), rings, field ...
and
polyhedra
In geometry, a polyhedron (plural polyhedra or polyhedrons; ) is a three-dimensional shape with flat polygonal faces, straight edges and sharp corners or vertices.
A convex polyhedron is the convex hull of finitely many points, not all on t ...
which cost Kirkman recognition by the mathematical community in Europe), further contributing to his being sidelined by the mathematics establishment. His comprehensive 1847 paper in particular was forgotten, with many subsequent authors either crediting Steiner or Reiss, unaware of the history.
* The schoolgirl puzzle's popularity itself was unaffected by Kirkman's academic conflicts, and in the late 19th and early 20th centuries the puzzle appeared in several recreational mathematics books by
Édouard Lucas
__NOTOC__
François Édouard Anatole Lucas (; 4 April 1842 – 3 October 1891) was a French mathematician. Lucas is known for his study of the Fibonacci sequence. The related Lucas sequences and Lucas numbers are named after him.
Biography
Lucas ...
,
Rouse Ball
Walter William Rouse Ball (14 August 1850 – 4 April 1925), known as W. W. Rouse Ball, was a British mathematician, lawyer, and fellow at Trinity College, Cambridge, from 1878 to 1905. He was also a keen amateur magician, and the founding ...
,
Wilhelm Ahrens
Wilhelm Ahrens (3 March 1872 – 23 May 1927) was a German mathematician and writer on recreational mathematics.
Biography
Ahrens was born in Lübz at the Elde in Mecklenburg and studied from 1890 to 1897 at the University of Rostock, Humboldt U ...
, and
Henry Dudeney
Henry Ernest Dudeney (10 April 1857 – 23 April 1930) was an English author and mathematician who specialised in logic puzzles and mathematical games. He is known as one of the country's foremost creators of mathematical puzzles.
Early life
...
. In his lifetime, Kirkman would complain about his serious mathematical work being eclipsed by the popularity of the schoolgirl problem. Kirkman died in 1895.
* 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'' which discussed the early history of the field and corrected the historical omission.
* At about the same time, Cummings was working with
Frank Nelson Cole
Frank Nelson Cole (September 20, 1861 – May 26, 1926) was an American mathematician.
Life and works
Cole was born in Ashland, Massachusetts. When he was very young, the family moved to Marlborough, Massachusetts where he attended school and ...
and
Henry Seely White
Henry Seely White (May 20, 1861 – May 20, 1943) was an American mathematician. He was born in Cazenovia, New York to parents Aaron White and Isadore Maria Haight. He matriculated at Wesleyan University in Connecticut and graduated with honors ...
on triple systems. This culminated in their famous and widely cited 1919 paper ''Complete classification of triad systems on 15 elements''
["Complete classification of triad systems on 15 elements" by Cole, Cummings and White](_blank)
/ref> 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'' 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 the 1960s, it was proved that Kirkman triple systems exist for ''all'' orders ''n'' = 3 (mod 6). This was first proved by Lu Jiaxi ( zh, s=陆家羲) in 1965, and he submitted it to ''Acta Mathematica Sinica
''Acta Mathematica Sinica'' (English series) is a peer-reviewed mathematics journal published quarterly by Springer.
Founded in 1936 and split into a Chinese series and an English series in 1985, the journal publishes articles on all areas of mat ...
'' but the journal erroneously thought the problem had been solved already and rejected his paper in 1966, which was later found to be a serious mistake. His subsequent academic contributions were disrupted by the Cultural Revolution
The Cultural Revolution, formally known as the Great Proletarian Cultural Revolution, was a sociopolitical movement in the People's Republic of China (PRC) launched by Mao Zedong in 1966, and lasting until his death in 1976. Its stated goal ...
and rejected again. In 1968, the generalized theorem was proven independently by D. K. Ray-Chaudhuri and R. M. Wilson
Richard Michael Wilson (23 November 1945) is a mathematician and a professor emeritus at the California Institute of Technology. Wilson and his PhD supervisor Dijen K. Ray-Chaudhuri, solved Kirkman's schoolgirl problem in 1968. Wilson is known ...
.
* In 1974, RHF Denniston
RHF may refer to:
* Regional health authority (Norway), Regional health authority or ''Regionalt helseforetak'', of Norway
* Ice Hockey Federation of Russia (Russian Hockey Federation)
* Residence Hall Federation at Virginia Tech campus#Residence ...
solved the Sylvester problem of constructing 13 disjoint Kirkman solutions and using them to cover all 455 triples on the 15 girls.[Denniston's solution to Sylvester's problem](_blank)
/ref> His solution is discussed below.
Sylvester's problem
James Joseph Sylvester
James Joseph Sylvester (3 September 1814 – 15 March 1897) was an English mathematician. He made fundamental contributions to matrix theory, invariant theory, number theory, partition theory, and combinatorics. He played a leadership ro ...
in 1850 asked if 13 disjoint Kirkman systems of 35 triples each could be constructed to use all triples on 15 girls. No solution was found until 1974 when RHF Denniston
RHF may refer to:
* Regional health authority (Norway), Regional health authority or ''Regionalt helseforetak'', of Norway
* Ice Hockey Federation of Russia (Russian Hockey Federation)
* Residence Hall Federation at Virginia Tech campus#Residence ...
at the University of Leicester
, mottoeng = So that they may have life
, established =
, type = public research university
, endowment = £20.0 million
, budget = £326 million
, chancellor = David Willetts
, vice_chancellor = Nishan Canagarajah
, head_labe ...
constructed it with a computer. 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. 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, 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.
The American minimalist composer Tom Johnson composed a piece of music called ''Kirkman's Ladies'' based on Denniston's solution.
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
The equivalent of the Kirkman problem for 9 schoolgirls results in S(2,3,9), an affine plane
In geometry, an affine plane is a two-dimensional affine space.
Examples
Typical examples of affine planes are
* Euclidean planes, which are affine planes over the reals equipped with a metric, the Euclidean distance. In other words, an affine pl ...
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 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
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. Similar sets of disjoint Steiner systems have also been investigated for the S(5,8,24) Steiner system in addition to triple systems.
Galois geometry
In 1910 the problem was addressed using Galois geometry
Galois geometry (so named after the 19th-century French mathematician Évariste Galois) is the branch of finite geometry that is concerned with algebraic and analytic geometry over a finite field (or ''Galois field''). More narrowly, ''a'' Ga ...
by George Conwell.
The Galois field
In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) is a field that contains a finite number of elements. As with any field, a finite field is a set on which the operations of multiplication, addition, subtra ...
GF(2)
(also denoted \mathbb F_2, or \mathbb Z/2\mathbb Z) is the finite field of two elements (GF is the initialism of ''Galois field'', another name for finite fields). Notations and \mathbb Z_2 may be encountered although they can be confused with ...
with two elements is used with four homogeneous coordinates
In mathematics, homogeneous coordinates or projective coordinates, introduced by August Ferdinand Möbius in his 1827 work , are a system of coordinates used in projective geometry, just as Cartesian coordinates are used in Euclidean geometry. T ...
to form PG(3,2)
In finite geometry, PG(3,2) is the smallest three-dimensional projective space. It can be thought of as an extension of the Fano plane.
It has 15 points, 35 lines, and 15 planes. It also has the following properties:
* Each point is contained in 7 ...
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
In mathematics, specifically in incidence geometry and especially in projective geometry, a complete quadrangle is a system of geometric objects consisting of any four points in a plane, no three of which are on a common line, and of the six l ...
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 geometry, Plücker coordinates, introduced by Julius Plücker in the 19th century, are a way to assign six homogeneous coordinates to each line in projective 3-space, P3. Because they satisfy a quadratic constraint, they establish a one-to- ...
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
In mathematics, the lines of a 3-dimensional projective space, ''S'', can be viewed as points of a 5-dimensional projective space, ''T''. In that 5-space, the points that represent each line in ''S'' lie on a quadric, ''Q'' known as the Klein q ...
. For each of the 28 points off ''S'' there are 6 lines through it which do not intersect ''S''.[
As there are seven days in a week, the heptad is an important part of the solution:
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
In mathematics, especially in the group theoretic area of algebra, the projective linear group (also known as the projective general linear group or PGL) is the induced action of the general linear group of a vector space ''V'' on the associate ...
PGL(3,2) is isomorphic the alternating group
In mathematics, an alternating group is the group of even permutations of a finite set. The alternating group on a set of elements is called the alternating group of degree , or the alternating group on letters and denoted by or
Basic prop ...
on the 8 heptads.[
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.][
]
Spreads and packing
In PG(3,2), a partition
Partition may refer to:
Computing Hardware
* Disk partitioning, the division of a hard disk drive
* Memory partition, a subdivision of a computer's memory, usually for use by a single job
Software
* Partition (database), the division of a ...
of the points into lines is called a spread
Spread may refer to:
Places
* Spread, West Virginia
Arts, entertainment, and media
* ''Spread'' (film), a 2009 film.
* ''$pread'', a quarterly magazine by and for sex workers
* "Spread", a song by OutKast from their 2003 album ''Speakerboxxx/T ...
, and a partition of the lines into spreads is called a ' or '. 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,[ and he presented two of them.][
]
Generalization
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
250px, thumbnail, The Fano plane is a Steiner triple system S(2,3,7). The blocks are the 7 lines, each containing 3 points. Every pair of points belongs to a unique line.
In combinatorial mathematics, a Steiner system (named after Jakob Steiner) ...
, an S(2, 3, 6''t'' + 3) with parallelism (that is, one in which each of the 6''t'' + 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
Richard Michael Wilson (23 November 1945) is a mathematician and a professor emeritus at the California Institute of Technology. Wilson and his PhD supervisor Dijen K. Ray-Chaudhuri, solved Kirkman's schoolgirl problem in 1968. Wilson is known ...
in 1968, though it had already been solved by Lu Jiaxi ( zh, s=陆家羲) 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.
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
The Oberwolfach problem is an unsolved problem in mathematics that may be formulated either as a problem of scheduling seating assignments for diners,
or more abstractly as a problem in graph theory, on the edge cycle covers of complete graphs. I ...
, of decomposing a complete graph
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices is c ...
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.
Other applications
* Cooperative learning
Cooperative learning is an educational approach which aims to organize classroom activities into academic and social learning experiences. There is much more to cooperative learning than merely arranging students into groups, and it has been desc ...
strategy for increasing interaction within classroom teaching
* Dobble
''Dobble'' is a game in which players have to find symbols in common between two cards. It was the UK’s best-selling game in 2018 and 2019.
The game is sold as ''Dobble'' in Europe and ''Spot It!'' in the US. The name is a play on the word ' ...
card game
* Progressive dinner party designs
* Speed Networking
Speed networking (or speed business meeting) is a meeting format designed to accelerate business contacts.
Speed networking basically involves participants gathering together to exchange information. Participants greet each other in a series of br ...
events
* Sports Competitions
Sport pertains to any form of Competition, competitive physical activity or game that aims to use, maintain, or improve physical ability and Skill, skills while providing enjoyment to participants and, in some cases, entertainment to specta ...
*Combinatorics
Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many appl ...
* R M Wilson
* Dijen K. Ray-Chaudhuri
*Discrete Mathematics
Discrete mathematics is the study of mathematical structures that can be considered "discrete" (in a way analogous to discrete variables, having a bijection with the set of natural numbers) rather than "continuous" (analogously to continuous f ...
Notes
References
*
*
*
*
*
**
*
*
*
*
*
*
*
*
**
External links
*
*
{{Incidence structures
Combinatorial design
Mathematical problems
Families of sets