Kirkman's schoolgirl problem
Fifteen schoolgirls go for a walk every day for a week, in five rows of three. Arrange the rows for the seven days so that no two girls walk in the same row more than once.
History and references
Solved in 1850 by Thomas Penyngton Kirkman.
Kirkman posed the puzzle in 1850 in The Lady's and Gentleman's Diary, three years after his paper on triple systems. The schedule is tight, since each girl has 14 possible partners and meets exactly 2 of them each day for 7 days. Kirkman and Arthur Cayley both published solutions, and in 1922 Frank Nelson Cole listed the seven solutions that exist up to relabeling the girls. A solution is a resolvable Steiner triple system on 15 points, now called a Kirkman triple system. The general question of which allow such schedules was answered by Lu Jiaxi in 1965, whose work went unpublished at the time, and independently by Ray-Chaudhuri and Wilson in 1968, the answer being all .
References
Solutions 0
Sign in or create an account to publish a solution