CAN KIRKMAN’S SCHOOLGIRLS WALK ABREAST BY FORMING ARITHMETIC PROGRESSIONS?

A Kirkman triple system of order v, whose point set is consecutively numbered, is called smooth, if for each parallel class there is a number d, such that each triple of the parallel class forms an arithmetic progression modulo v with common difference d. It will be shown that smooth Kirkman triple systems of order v exist, if and only if v is a power of 3. 1 Smooth Kirkman triple systems The following problem, known as Kirkman’s schoolgirl problem, was introduced in 1850 by Reverend Thomas J. Kirkman (1806–1895) as “Query 6 ” on page 48 of the Ladies and Gentleman’s Diary [2] (see [3] for his statement of the general problem): 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 walk twice abreast. The general setting of the problem is the following: One wants to find 3n+1 arrangements of 6n + 3 girls in rows of three, such that any two girls belong to the same row in exactly one arrangement. In modern terms of block designs, the generalized Kirkman’s schoolgirl problem is equiva-lent to finding a resolution of some balanced incomplete block design with block size 3: For positive integers b, v, r, k, λ with r = λ(v−1)k−1 and b = λv(v−1) k(k−1) , a (v, k, λ)-Balanced Incomplete Block Design BIBD consists of a finite set Z of v elements, called points, and b subsets Z1, Z2,..., Zb of Z, called blocks, such that the following hold: every point occurs in exactly r blocks, every block contains exactly k points, and every pair of points occurs together in exactly λ blocks