Kirkman's schoolgirl problem
- Kirkman's schoolgirl problem
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.[cite book |last= Graham |first= Ronald L. |authorlink= Ronald Graham |coauthors= Martin Grötschel, László Lovász |title= Handbook of Combinatorics, Volume 2 |year= 1995 |publisher= The MIT Press |location= Cambridge, MA |isbn= 0-262-07171-1 ] ]
Solution
If the girls are numbered from 01 to 15, the following arrangement is one solution:
A solution to this problem is an example of a Kirkman triple system.[MathWorld |title= Kirkman's Schoolgirl Problem |urlname= KirkmansSchoolgirlProblem] ]
Generalization
The problem can be generalized to n girls, where n is an odd multiple of 3, walking in triplets for
:frac{1}{2}(n-1)
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, 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).[cite book |last= Ball |first= W.W. Rouse |authorlink= W. W. Rouse Ball |coauthors= H.S.M. Coxeter |title=Mathematical Recreations & Essays |year= 1974 |publisher= University of Toronto Press |location= Toronto and Buffalo |isbn= 0-8020-1844-0] It is this generalization of the problem which Kirkman first discussed, with the particular case n=15 proposed later. ][cite journal |last= Kirkman |first=Thomas P. |authorlink= Thomas Kirkman |title= On a Problem in Combinations |journal= The Cambridge and Dublin Mathematical Journal |volume= II |pages= 191–204 | publisher = Macmillan, Barclay, and Macmillan |date= 1847] A complete solution to the general case was given by D. K. Ray-Chaudhuri and R. M. Wilson in 1969.]
References
Wikimedia Foundation.
2010.
Look at other dictionaries:
Thomas Kirkman — Infobox Person name = Thomas Penyngton Kirkman image size = caption = birth date = birth date|1806|3|31 birth place = Bolton, Lancashire death date = death date and age|1895|2|3|1806|3|31 death place = death cause = occupation = Mathematician… … Wikipedia
Dwijendra Kumar Ray-Chaudhuri — D. K. Ray Chaudhuri Born 1933 Narayanganj, India Residence USA Citizenship … Wikipedia
Dikran Tahta — Dikran Dick Tahta Born 7 August 1928(1928 08 07) Manchester, England Died 2 December 2006(2006 12 02) (aged 78) England Occupation Mathematician, teacher, author … Wikipedia
List of combinatorics topics — This is a list of combinatorics topics.A few decades ago it might have been said that combinatorics is little more than a way to classify poorly understood problems, and some standard remedies. Great progress has been made since 1960.This page is … Wikipedia
Combinatorics — is a branch of mathematics concerning the study of finite or countable discrete structures. Aspects of combinatorics include counting the structures of a given kind and size (enumerative combinatorics), deciding when certain criteria can be met,… … Wikipedia
List of mathematics articles (K) — NOTOC K K approximation of k hitting set K ary tree K core K edge connected graph K equivalence K factor error K finite K function K homology K means algorithm K medoids K minimum spanning tree K Poincaré algebra K Poincaré group K set (geometry) … Wikipedia
Steiner system — In combinatorial mathematics, a Steiner system (named after Jakob Steiner) is a type of block design.A Steiner system with parameters l , m , n , written S( l , m , n ), is an n element set S together with a set of m element subsets of S (called… … Wikipedia
Combinatorial design — theory is the part of combinatorial mathematics that deals with the existence and construction of systems of finite sets whose intersections have specified numerical properties. For instance, a balanced incomplete block design (usually called for … Wikipedia
combinatorics — /keuhm buy neuh tawr iks, tor , kom beuh /, n. (used with singular v.) See combinatorial analysis. * * * Branch of mathematics concerned with the selection, arrangement, and combination of objects chosen from a finite set. The number of possible… … Universalium
Dijen Ray-Chaudhuri — Dijen Kumar Ray Chaudhuri, eigentlich Dwijendra Ray Chaudhuri, (* 1. November 1933 in Narayangang in Indien) ist ein indisch US amerikanischer Mathematiker, der sich mit Kombinatorik beschäftigt. Ray Chaudhuri studierte an der Universität von… … Deutsch Wikipedia