xliv. Kirkman's Schoolgirl Problem

Problem (Kirkman, 1850). Fifteen schoolgirls walk out three abreast for seven days. Arrange them so that no two walk together twice.

Answer. Possible. In design language: a Steiner triple system STS($v$) is a set of triples of $v$ points covering every pair exactly once; it is resolvable (a Kirkman triple system, KTS) if the triples split into parallel classes (days), each partitioning the points. Kirkman’s problem asks for a KTS(15): $\left(\genfrac{}{}{0ex}{}{15}{2}\right)/3=35$ triples, 5 per day, 7 days.

Object	Exists iff	Construction
STS($v$)	$v\equiv 1,3(\mathrm{mod}6)$ (Kirkman, 1847)	Bose ($v\equiv 3$), Skolem ($v\equiv 1$) below
KTS($v$)	$v\equiv 3(\mathrm{mod}6)$ (Ray-Chaudhuri and Wilson, 1971)	KTS(15): resolve the lines of the projective space PG(3, 2)
KTS(15) up to isomorphism	7 solutions (from 4 of the 80 STS(15))	computer classification
number of triples of STS($v$)	$v(v-1)/6$; each point in $(v-1)/2$ triples

The 15-girl schedule. Label the girls by the nonzero vectors of ${\mathbb{F}}_2^4$, i.e. $\mathrm{1..15}$ as 4-bit masks. The 35 triples $\{a,b,a\oplus b\}$ are the lines of PG(3, 2): every pair $a\ne b$ lies in exactly the one line $\{a,b,a\oplus b\}$. A short search splits them into 7 days of 5 disjoint lines; with girl $i$ written as the letter $i$ of A..O, kirkman15() returns:

Day	Rows of three
1	ABC, DHL, EJO, FKM, GIN
2	ADE, BHJ, CMN, FIO, GKL
3	AFG, BIK, CLO, DJN, EHM
4	AHI, BLN, CEF, DKO, GJM
5	AJK, BMO, CDG, EIL, FHN
6	ALM, BDF, CIJ, EKN, GHO
7	ANO, BEG, CHK, DIM, FJL

using Triple = array<int, 3>;
 
vector<Triple> boseSTS(int v) {                     // v = 3n, n odd; points x + n * level
    int n = v / 3, h = (n + 1) / 2; vector<Triple> T;
    auto op = [&](int x, int y) { return (x + y) * h % n; };   // idempotent commutative quasigroup: x o x = x
    for (int x = 0; x < n; x++) T.push_back({x, x + n, x + 2 * n});
    for (int i = 0; i < 3; i++) for (int x = 0; x < n; x++) for (int y = x + 1; y < n; y++)
        T.push_back({x + i * n, y + i * n, op(x, y) + (i + 1) % 3 * n});
    return T;
}
 
vector<Triple> skolemSTS(int v) {                   // v = 6n + 1; points x + 2n * level, infinity = 6n
    int n = (v - 1) / 6, m = 2 * n, inf = 6 * n; vector<Triple> T;
    auto op = [&](int x, int y) { int k = (x + y) % m; return k % 2 == 0 ? k / 2 : n + (k - 1) / 2; };   // x o x = x mod n
    for (int x = 0; x < n; x++) T.push_back({x, x + m, x + 2 * m});
    for (int i = 0; i < 3; i++) for (int x = 0; x < n; x++) T.push_back({inf, n + x + i * m, x + (i + 1) % 3 * m});
    for (int i = 0; i < 3; i++) for (int x = 0; x < m; x++) for (int y = x + 1; y < m; y++)
        T.push_back({x + i * m, y + i * m, op(x, y) + (i + 1) % 3 * m});
    return T;
}
 
// Split a Steiner triple system on points 0..v-1 into parallel classes (days); empty if it is not resolvable.
vector<vector<Triple>> resolve(int v, const vector<Triple>& T) {
    int days = (v - 1) / 2; vector<vector<int>> at(v);
    for (int t = 0; t < sz(T); t++) for (int p : T[t]) at[p].push_back(t);
    vector<char> used(sz(T), 0); vector<vector<Triple>> res(days);
    auto go = [&](auto&& self, int d, ll covered) -> bool {     // covered: points already placed on day d
        if (d == days) return true;
        if (covered == (1LL << v) - 1) return self(self, d + 1, 0);
        int p = __builtin_ctzll(~covered);                       // smallest point still walking alone
        for (int t : at[p]) if (!used[t] && !(covered >> T[t][0] & 1) && !(covered >> T[t][1] & 1) && !(covered >> T[t][2] & 1)) {
            used[t] = 1; res[d].push_back(T[t]);
            if (self(self, d, covered | 1LL << T[t][0] | 1LL << T[t][1] | 1LL << T[t][2])) return true;
            used[t] = 0; res[d].pop_back();
        }
        return false;
    };
    if (!go(go, 0, 0)) return {};
    return res;
}
 
vector<vector<Triple>> kirkman15() {                // girls 0..14 = nonzero 4-bit vectors minus 1
    vector<Triple> lines;
    for (int a = 1; a < 16; a++) for (int b = a + 1; b < 16; b++) if ((a ^ b) > b) lines.push_back({a - 1, b - 1, (a ^ b) - 1});
    return resolve(15, lines);
}

Proof: STS(v) exists iff v ≡ 1, 3 (mod 6)

Necessity. A point $p$ lies in triples that pair it with the other $v-1$ points two at a time, so $v-1$ is even. The number of triples is $\left(\genfrac{}{}{0ex}{}{v}{2}\right)/3=v(v-1)/6$, so $3\mid v(v-1)$, i.e. $v\equiv 0,1(\mathrm{mod}3)$. Together, $v\equiv 1,3(\mathrm{mod}6)$. A KTS also needs $3\mid v$ (each day partitions the points into triples), so $v\equiv 3(\mathrm{mod}6)$.

Bose ($v=3n$, $n$ odd). $x\circ y=\frac{n+1}{2}(x+y)\mathrm{mod}n$ is commutative, idempotent ($x\circ x=(n+1)x\equiv x$) and Latin ($\frac{n+1}{2}$ is invertible mod $n$). Pairs inside a level $i$: $\{(x,i),(y,i)\}$ lies only in the triple $\{(x,i),(y,i),(x\circ y,i+1)\}$. Pairs across levels $i,i+1$: $\{(x,i),(z,i+1)\}$ lies in the vertical triple if $z=x$; otherwise in $\{(x,i),(y,i),(z,i+1)\}$ for the unique $y$ with $x\circ y=z$, and $y\ne x$ because $x\circ x=x\ne z$; never in both, since $y=x$ would force $z=x$. Every pair is covered exactly once.

Skolem ($v=6n+1$). On ${\mathbb{Z}}_{2n}$, $x\circ y=\sigma (x+y)$ with $\sigma (2t)=t$, $\sigma (2t+1)=n+t$ is commutative and Latin ($\sigma$ is a bijection) and half-idempotent: $x\circ x=(n+x)\circ (n+x)=x$ for $0\le x<n$, i.e. $u\circ u=u\mathrm{mod}n$. Pairs with $\infty$: $(n+x,i)$ and $(x,i+1)$ lie in the triple $\{\infty ,(n+x,i),(x,i+1)\}$, and these triples contain each finite point once. Same-level pairs lie only in $\{(x,i),(y,i),(x\circ y,i+1)\}$. For a cross pair $\{(u,i),(z,i+1)\}$ let $y$ be the unique element with $u\circ y=z$. If $y\ne u$, the pair lies in the triple $\{(u,i),(y,i),(z,i+1)\}$; the vertical and $\infty$-triples contain only cross pairs with $z=u\mathrm{mod}n=u\circ u$, which would force $y=u$. If $y=u$, i.e. $z=u\mathrm{mod}n$, the pair lies in the vertical triple when $u<n$ or in the $\infty$-triple when $u\ge n$, and in no triple of the third kind. Every pair is covered exactly once.

PG(3, 2). For distinct nonzero $a,b$, $a\oplus b$ is nonzero and differs from both, and $\{a,b,c\}$ is a line iff $a\oplus b\oplus c=0$; so each pair lies in exactly one line, and the lines form an STS(15). The search resolve tries, for the smallest point not yet placed today, every unused triple through it that is disjoint from today’s triples: every resolution is reachable this way, so the search is exhaustive and the schedule it returns is valid. Checked: Bose and Skolem systems cover every pair exactly once for all valid $v\le 99$, and kirkman15() returns 7 days, each a partition of the 15 girls, with no pair repeated.

Related notes

• Constructive Algorithms
• Latin Squares and Euler’s 36 Officers (quasigroups are Latin squares)
• Exact Cover and Dancing Links