Problem of the 15 school girls

from Wikipedia, the free encyclopedia
Original publication of the problem

The 15 schoolgirl problem was formulated by Thomas Kirkman in 1850 .

It is said:

"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."

"Fifteen schoolgirls walk in groups of three for seven days in a row, they are divided daily so that no two schoolgirls walk together twice."

The problem was in 1850 by Kirkman in the Journal of Recreational Mathematics The Lady's and Gentleman's Diary asked and solutions of Arthur Cayley given and Kirkman himself. There was later an argument between Kirkman and the famous mathematician James Joseph Sylvester , who also claimed the introduction of the problem for himself.

The problem is a special case of Steiner systems S (t, k, n), a system of n elements with a division into k-element blocks as subsets, so that every subset of t elements is in exactly one block (also t- (n, k, 1) called block plan ). In the schoolgirl problem for n schoolgirls one has to do with Steiner-Tripel systems S (2,3, n). In the case of n = 15 there are a total of seven options for dividing the schoolgirl groups as required. These were published in 1862/1863 by Wesley Woolhouse in the same journal in which Kirkman posed the problem.

The general solution to such problems proved to be more difficult than originally thought. The proof of the existence of a solution in the general case was given by Richard M. Wilson and DK Ray-Chaudhuri in 1968, and in 2014 even more general proof of the existence of feasible block plans was given by Peter Keevash . There are not solutions for every n and every combination of parameters, certain natural divisibility conditions must be fulfilled, for example n must be divisible by 3. If these conditions are met, Wilson could prove the existence of a solution. The number of solutions increases exponentially with n. With 19 school girls there are already over eleven billion ways of dividing them into groups of three, provided that each student walks in a group of three in the presence of every other student exactly once.

Kirkman's school girl problem was the beginning of the development of block diagram or combinatorial design theory.

Web links

Individual evidence

  1. ^ Query VI, in: The Lady's and Gentleman's Diary for the year 1850, p. 48
  2. ↑ Dayley: On the triadic arrangements of seven and fifteen things, Phil. Mag. 37, 1850, pp. 50-53
  3. ↑ Kirkman, Note on an unanswered prize question, The Cambridge and Dublin Mathematical Journal, Volume 5, 1850, pp. 255-262
  4. ↑ Woolhouse: On triadic Combinations of 15 symbols. In: Lady's and Gentleman's Diary, 1862, pages 84-88 (reprinted in Assurance Magazine, 1862, pages 275-281).
  5. ↑ Woolhouse: On triadic combinations. In: Lady's and Gentleman's Diary, 1863, pp. 79-90.
  6. ^ Ray-Chaudhuri, Wilson: Solution of Kirkman's schoolgirl problem, in: Combinatorics, University of California, Los Angeles, 1968, Proc. Sympos. Pure Math, American Mathematical Society, Volume 19, 1971, pp. 187-203
  7. ↑ If the number of schoolgirls is not a whole number divisible by 3, not every girl goes for a walk every day.