Kirkman's schoolgirl problem
From Wikipedia, the free encyclopedia
Kirkman's schoolgirl problem is a problem in combinatorics proposed by Thomas Kirkman in 1850 as Query VI in The Lady's and Gentleman's Diary. 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]
[edit] Solution
If the girls are numbered from 00 to 14, the following arrangement is one solution:[2]
| Sun. | Mon. | Tues. | Wed. | Thurs. | Fri. | Sat. |
|---|---|---|---|---|---|---|
| 00, 05, 10 | 00, 01, 04 | 01, 02, 05 | 04, 05, 08 | 02, 04, 10 | 04, 06, 12 | 10, 12, 03 |
| 01, 06, 11 | 02, 03, 06 | 03, 04, 07 | 06, 07, 10 | 03, 05, 11 | 05, 07, 13 | 11, 13, 04 |
| 02, 07, 12 | 07, 08, 11 | 08, 09, 12 | 11, 12, 00 | 06, 08, 14 | 08, 10, 01 | 14, 01, 07 |
| 03, 08, 13 | 09, 10, 13 | 10, 11, 14 | 13, 14, 02 | 07, 09, 00 | 09, 11, 02 | 00, 02, 08 |
| 04, 09, 14 | 12, 14, 05 | 13, 00, 06 | 01, 03, 09 | 12, 13, 01 | 14, 00, 03 | 05, 06, 09 |
A solution to this problem is an example of a Kirkman triple system.[3]
[edit] Generalization
The problem can be generalized to n girls, where n is an odd multiple of 3, 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
- 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).[2] It is this generalization of the problem which Kirkman first discussed, with the particular case n = 15 proposed later.[4] A complete solution to the general case was given by D. K. Ray-Chaudhuri and R. M. Wilson in 1969.[2]
[edit] References
- ^ 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.
- ^ a b c Ball, W.W. Rouse; H.S.M. Coxeter (1974). Mathematical Recreations & Essays. Toronto and Buffalo: University of Toronto Press. ISBN 0-8020-1844-0.
- ^ Eric W. Weisstein, Kirkman's Schoolgirl Problem at MathWorld.
- ^ Kirkman, Thomas P. (1847). "On a Problem in Combinations". The Cambridge and Dublin Mathematical Journal II: 191-204.
