The fifteen schoolgirls problem was long regarded as one of the most famous problems in combinatorics. It was proposed by Thomas Pennyngton Kirkman (1806–1895), an English mathematician and algebraist, and a Fellow of the Royal Society of London (1881). His works provided the first systematic presentation of the elements of group theory in English. He also made a major contribution to combinatorics.
The fifteen schoolgirls problem appeared in 1850 as Question VI in The Lady’s and Gentleman’s Diary, a recreational mathematics journal published between 1841 and 1871.
The problem is stated as follows:
“Fifteen young girls at a school go for a walk in rows of three each day for seven days. Arrange them for each walk so that no two girls walk in the same row twice.”
(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).
Its deceptive simplicity quickly made the problem famous.
One possible solution is shown in the table below. The girls are numbered from 0 to 14.
There are known to be seven non-isomorphic solutions to this fifteen schoolgirls problem.
(An isomorphism is a bijective mapping between sets with the same structure that preserves that structure.)
The first solution was published by Arthur Cayley in 1850, quickly followed by Kirkman’s own solution that year. Kirkman presented it as a special case of his combinatorial arrangement published three years earlier, in 1847. J. J. Sylvester also studied the problem. The puzzle appeared in several recreational mathematics books.
Combinatorial designs became very popular and were even used in gambling fraud. In one reported case, a criminal cartel earned millions of dollars over seven years by buying tickets covering every possible combination of 5 out of 46 in a 6-out-of-46 lottery whenever the ticket cost was lower than the additional bonuses for matching 5 out of 46 plus the chance of winning the jackpot.
Another solution uses XOR triples. If the girls are relabelled with binary numbers from 0001 to 1111, the following arrangement is a solution in which, for any group of three girls, the bitwise XOR of two numbers gives the third.
(Bitwise exclusive OR, or XOR, is a binary operation equivalent to applying logical exclusive OR to each pair of bits in matching positions in the operands’ binary representations.)
The problem was generalised to other initial conditions: given n schoolgirls, form groups of size k so that no set of t girls appears together in a group twice. This formulation is called an (n, k, t) design. The problem is solvable under some conditions and unsolvable under others. Over the years, solutions have become known for many combinations of (n, k, t), verified either algebraically or by exhaustive computer search.
The schoolgirl puzzle thus helped to establish a new field of mathematics: combinatorial designs. These designs became a method now used in error-correcting codes in computer science, cryptography, agriculture, sport and design. For example, the classical Hamming error-correcting code uses a solution of the schoolgirl problem.