A schedule where every pair meets once

Nine people are to be sorted into groups of three, several times over, so that every two of them share a group exactly once. It can be done, in twelve groupings, and the reason nine works and eight does not is two divisions.

The condition, from counting alone #

Suppose such a schedule exists on $n$ points, with triples covering every pair exactly once. Two counts follow immediately, and they are the whole answer.

Count from one point. A given point $P$ must meet each of the other $n-1$ points, and each triple containing $P$ introduces it to two of them. So $P$ lies in $(n-1)/2$ triples, and that number must be a whole number: $n$ must be odd.

Count all pairs. There are $\binom{n}{2} = n(n-1)/2$ pairs to cover, and each triple covers three of them. So the number of triples is $n(n-1)/6$, and that too must be whole.

The first condition says $n$ is odd. The second says $6$ divides $n(n-1)$; since $n$ is odd, $n-1$ is even, so it remains that $3$ divides $n(n-1)$, which happens when $n \equiv 0$ or $1$ modulo $3$.

Combining: $n$ odd and $n \equiv 0$ or $1 \pmod 3$ gives

$$n \equiv 1 \text{ or } 3 \pmod 6.$$

So the possible sizes are $3, 7, 9, 13, 15, 19, 21, 25, 27, \ldots$ and nothing else.

The figure computes the verdict from the divisions — checking whether $(n-1)/2$ and $n(n-1)/6$ are whole numbers — and separately from the residue rule, and asserts that the two agree at every size. That is a check on the derivation above rather than a restatement of it.

And then the condition is enough #

Necessary conditions are cheap. What makes this problem satisfying is that this one is also sufficient: at every size the divisions permit, a system exists.

That was proved by Thomas Kirkman in 1847, six years before Jakob Steiner asked the question the systems are now named after. Kirkman’s paper gives constructions for both residue classes and is one of the first substantial results in what is now called design theory. It is also a small lesson in attribution: Steiner posed the question independently in 1853 and the objects carry his name, while Kirkman’s own name attached to the harder variant he asked in the same paper and could not fully solve. The pattern — a result named for the person who asked rather than the one who answered — is common enough in this subject to be unremarkable.

The contrast with the projective planes of the previous essay is stark. There the necessary condition — Bruck and Ryser’s — rules out some orders and permits many that nobody has been able to construct or refute. Here the necessary condition is exactly right, and the gap between “the counting permits it” and “it exists” is empty.

There is no general reason to expect one outcome rather than the other. The two problems look similar, their necessary conditions are both counting arguments, and one of them happens to be the whole story.

The two smallest failures, and why they fail differently #

It is worth looking at the sizes just below the first interesting one, because the two conditions fail separately and the failures do not look alike.

Five points. $(5-1)/2 = 2$, whole. But $5 \times 4 / 6 = 10/3$, not whole. There are ten pairs to cover and each triple covers three, so no number of triples covers ten exactly. The obstruction is the total, and it is visible in one division.

Eight points. $8 \times 7 / 6 = 28/3$, not whole either — but the more immediate failure is the first condition: $(8-1)/2 = 3.5$. A given person would have to meet seven others two at a time, and seven is odd, so somebody gets met twice or not at all. That obstruction is local, visible from a single point, and no amount of cleverness about the rest of the schedule repairs it.

The distinction matters because a local obstruction is much easier to spot and much easier to trust. It is the same argument as the pigeonhole principle: a fixed number of things being sorted two at a time into an odd-sized requirement cannot come out level, and no arrangement is exempt.

Found rather than assumed #

The figures on this page take two different routes to a system, and which route is used is stated in each caption because the routes carry different weight.

For small sizes, a search. The generator backtracks: find the first pair not yet covered, try every third point that completes it without repeating a pair, recurse, and undo on failure. If the search returns a system, the system exists; if it exhausted the tree, none does. That is a decision, not a construction, and it is what the figures use at $n = 7$ and $n = 9$.

For larger sizes, a construction, then a verification. A search over $\binom{15}{3}$ candidate triples is not a page build’s business, so at $n = 13$ the generator uses the cyclic construction — take the base triples $\{0,1,4\}$ and $\{0,2,7\}$ and rotate each of them through all thirteen shifts — and at $n=15$ it uses the points of a four-dimensional space over $GF(2)$ with the triples $\{a, b, a+b\}$.

In both cases the result is then checked from scratch: every pair counted, every count required to be one, the number of triples required to be $n(n-1)/6$, and every point required to lie in $(n-1)/2$ of them. A construction that is quoted is a claim; a construction that is verified is a measurement.

Two constructions that were already here #

Both of the larger constructions are objects this field has already built, wearing different clothes.

At $n = 7$ the system is the Fano plane, whose seven lines are triples and whose axioms say precisely that every pair of points is on exactly one. That the backtracking search rediscovers it is not a coincidence: the system on seven points is unique up to relabelling, so any search that succeeds must find it.

At $n = 15$ the construction is the projective space of dimension three over $GF(2)$: fifteen points, and the triples are the lines. A line through two points $a$ and $b$ in that space contains exactly one more, namely $a + b$, because the field has characteristic two and $a+b$ is the only other non-zero combination. Every pair determines its third member, which is the defining property, delivered by arithmetic rather than by search.

At $n = 9$ the system is the affine plane of order three — nine points, twelve lines of three, which is what is left of the projective plane of order three after deleting one line and its points. That is why the count came out at twelve rather than thirteen: thirteen lines, minus the deleted one, is twelve.

The deletion is worth understanding because it runs the construction of the previous essay backwards. Adding a line at infinity to an ordinary plane makes it projective; deleting any line from a projective plane makes it affine, and the lines that met on the deleted line become parallel. Nine points and twelve lines is therefore the same object as the card game Set with one attribute removed — three values, two attributes, and a line being three cards that agree or differ everywhere.

So three of the four systems drawn here come from finite fields. That is the usual situation: constructions in design theory are overwhelmingly algebraic, and the searches are for the sizes where no algebra is available.

Kirkman’s harder question #

Kirkman also asked a sharper version, and it is the one his name is usually attached to.

Fifteen schoolgirls walk in five rows of three each day for seven days. Arrange it so that every two of them walk together exactly once.

The triples are a Steiner system on fifteen points — thirty-five of them, seven days of five rows — but there is an extra condition: the triples must be sortable into days, with each day’s five triples covering all fifteen girls exactly once.

A system with that property is called resolvable, and it is a genuinely stronger requirement. Not every Steiner triple system on fifteen points is resolvable; there are eighty of them up to relabelling and only some resolve. The general answer — a resolvable system on $n$ points exists exactly when $n \equiv 3 \pmod 6$ — was not settled until 1971, over a century after the question was posed.

The extra condition is a parallelism condition, and it is what converts a design into a schedule in the ordinary sense: a set of rounds, each of which uses everybody at once. Sports leagues, tournament brackets and experimental designs all want the resolvable version, and the ordinary one is not enough.

How many there are #

Existence is settled; counting is not, and the counts behave badly enough to be worth recording.

Up to relabelling there is exactly one system on $7$ points and one on $9$. There are two on $13$ points, eighty on $15$, and $11{,}084{,}874{,}829$ on $19$ — a number obtained by computer search in 2004. Nobody knows the count at $21$.

That explosion is the reason the small cases are so misleading. The system on seven points is unique, so anything true of it is true of the system of that size, and it is tempting to imagine designs as rigid objects. By fifteen points there are eighty of them, with different symmetry groups and different properties — some resolvable, some not — and the notion of “the” system has already dissolved.

The general growth is known to be enormous: the number of systems on $n$ points is roughly $n^{n^2/6}$, which was proved by Keevash in 2018 by the same method that settled existence. So the objects are simultaneously very constrained — only two sizes in six admit any — and very numerous at the sizes that work.

Beyond triples #

The natural generalisation is to ask for blocks of size $k$ covering every $t$-subset exactly once, and it has been open for most of the subject’s history.

The counting conditions generalise directly: for each $i$ below $t$, a certain binomial ratio must come out whole. Whether they suffice was conjectured for a century and proved only in 2014, by Peter Keevash, who showed that for every $t$ and $k$ the conditions are sufficient at all sufficiently large $n$.

Two qualifications matter and both are the kind this collection insists on stating. The result is asymptotic — it says the conditions suffice eventually, without saying from where — so a specific medium-sized case can still be open. And the proof is a probabilistic construction with a correction step, which shows a design exists without producing one; it is an existence proof rather than a construction, in exactly the sense that makes those proofs unsatisfying to anybody who wanted the object.

For triples none of that is needed. Kirkman’s constructions are explicit, they run to a page, and the figures on this page rebuild them.

What the pictures do and do not settle #

The drawings here place the points on a circle and draw each triple as a closed path. That arrangement carries no information: the points have no order, no position, and no distance, and rotating the circle gives an equally correct picture.

What the picture does carry is the incidence, and what the generator verifies is the incidence: every pair in exactly one triple, counted. The claim is checkable in full at every size drawn, and it is checked in full.

What no picture here settles is the sufficiency theorem, which is a statement about all $n \equiv 1$ or $3$ mod $6$ and therefore about infinitely many cases. Four systems are exhibited; the general claim is Kirkman’s and is argued in prose. The grid of sizes shows which sizes could work, decided by arithmetic, and is silent about all but the four where a system was actually built.

That division of labour is the standing arrangement in this field. A finite check settles a finite claim exactly; the infinite claim beside it has to be a theorem, and saying which is which on the page is the whole of the discipline.

Where the schedules are used #

A design is a scheduling device and the applications are older than the theory.

Experimental design. To compare $n$ treatments in blocks of three — three plots to a field, three samples to a batch — a balanced arrangement is one where every pair of treatments occurs together the same number of times, so that no pair is compared more precisely than any other. That is exactly this object, and it is why the general name for the family is balanced incomplete block design: incomplete because a block does not hold everything, balanced because the pairs are treated alike.

Tournaments. The resolvable version is a round-robin schedule with games of three players, and the resolvability is the requirement that everybody plays in every round.

Software testing. Covering every pair of parameter settings at least once — rather than exactly once — is the standard technique for testing a system with too many configurations to try exhaustively. The exact version here is the tight case of a family whose practical members allow some pairs to repeat.

Error correction. The incidence matrix of a design is a matrix over the two-element field with a controlled number of ones in each row and column, which is exactly what a sparse parity-check code wants. Several code families are built from designs, and the design’s guarantee that two rows share exactly one position is what stops the code’s checks from being redundant.

In all four the appeal is the same. A design is the arrangement in which no pair is favoured, and “no pair is favoured” is a fairness condition that can be stated as a count and therefore checked.

Where this anchor goes #

Designs and finite planes are two views of the same kind of object, and there is a third, older than either.

Two Latin squares of the same order are orthogonal when superimposing them produces every ordered pair of symbols exactly once. A complete set of $n-1$ mutually orthogonal squares of order $n$ is equivalent to a projective plane of order $n$; a single orthogonal pair is a much weaker and much older question, asked by Euler in 1782 about thirty-six officers and answered, in the negative, only in 1900 — by an exhaustive search done by hand.