Block design existence
A Socratic walk-through of block design existence — reasoned out one step at a time, not lectured.
The question we started with
THE QUESTION #Why can a schedule pairing every team exactly once exist for some team counts and for no others?
A club wants a season in which every pair of players competes exactly once, in groups of three. It sounds like an organiser's problem — fiddly, but the sort of thing patience and a spreadsheet eventually solve.
For nine players it works. For thirteen it works. For eleven, no arrangement exists, and no amount of patience will produce one. That is a strange thing for a scheduling problem to say, so the question worth chasing is not how to build such a schedule but how anyone can be certain, without searching, that for eleven there is nothing to find.
Reasoning it through
REASONING #Start with the easy version, groups of two — an ordinary round robin. There are n(n − 1)/2 pairings to get through, and if each round is to use everybody at once, a round holds n/2 matches, so n must be even; odd n forces a bye. That is the whole obstruction, and it is arithmetic rather than ingenuity.
Now groups of three, and the same move works harder. Fix one player, x. Every block containing x pairs x with two other players, and every other player must be paired with x exactly once across the season. So if x appears in r blocks, those blocks supply 2*r* partners, and they must be exactly the other n − 1 players, each once. Therefore 2r = n − 1, and
r = (n − 1)/2.
That is already a constraint: r is a count of blocks, so it must be a whole number, and n must be odd. Eleven passes this test.
Count once more, differently. How many blocks are there altogether? Each of the n players sits in r blocks, so there are n × r player-slots to fill; each block holds three players and so consumes three slots. Hence
b = n · r / 3 = n(n − 1)/6,
and b, being a count, must also be a whole number. Test eleven: 11 × 10 / 6 = 110/6 = 18⅓. Not a whole number. There is no schedule, and we did not look at a single arrangement to know it — we counted a quantity every valid schedule would have to possess and found it could not exist.
Which counts survive both tests? Odd n means n ≡ 1, 3 or 5 modulo 6. For n ≡ 1, take n = 7: 7 × 6/6 = 7 blocks, r = 3. For n ≡ 3, take n = 9: 9 × 8/6 = 12 blocks, r = 4. For n ≡ 5, take n = 5: 5 × 4/6 = 3⅓ — fails, and it fails for every n ≡ 5 modulo 6, since then n(n − 1) leaves remainder 2. So the surviving counts are exactly n ≡ 1 or 3 modulo 6: 7, 9, 13, 15, 19, 21, and so on. Eleven and seventeen are out.
Here is the part that does not follow from any of the above, and is the real theorem: for every one of those surviving counts, a schedule genuinely exists. Kirkman proved it in 1847. The arithmetic was only ever an eliminator; that it eliminates nothing else is a separate and much harder fact.
Ask for more and the arithmetic tightens again. Want the blocks grouped into rounds, each round using every player exactly once — a resolvable design — and three must divide n as well, which with the earlier condition leaves n ≡ 3 modulo 6. Fifteen qualifies, giving Kirkman's schoolgirls: 105 pairs, 5 triples a day covering 15 pairs, so 7 days — and each girl appears in r = 7 triples, one per day, which is the two counts agreeing.
The analogy
THE ANALOGY #Think of tiling a floor with L-shaped pieces of three squares. Before cutting anything, count: each piece covers three squares, so the floor's area must divide by three. A floor of 100 squares is settled immediately, with no arrangement attempted. But a floor of 99 is not thereby tileable — the count merely failed to forbid it, and whether the pieces actually fit is a different question needing a different kind of argument.
tiling is a geometric problem where the pieces have shape and position, whereas a block design has neither — any three players may form a block — so the obstructions here are purely arithmetic and structural, never about anything failing to fit into a corner.
Clarifying the model
THE MODEL #Two refinements, and the second is where the folklore is wrong.
First, note the asymmetry in what counting can do: it proves non-existence outright and proves existence never. Every count above says "any valid schedule would need this many blocks, and no whole number does" — an argument needing no schedule to exist in order to work. It is the mirror image of the pigeonhole principle, which uses counting to force something to exist without exhibiting it.
Second, and the important correction: it is tempting to conclude that the divisibility conditions decide these questions in general. They do not. Consider a projective plane of order 10 — 111 points, 111 lines, 11 points to a line, every pair of points on exactly one line. Every divisibility condition passes, and the Bruck-Ryser-Chowla theorem, which rules out order 6 because 6 is not a sum of two squares, has nothing to say about 10, which is 1 + 9. Yet no such plane exists. That was established by Lam, Thiel and Swiercz in 1989 through an exhaustive computer search costing years of processor time, and no human-checkable proof is known. Triple systems, where the necessary conditions happen also to be sufficient, are the fortunate case rather than the pattern.
What observation would refute all this? Someone hands you a schedule for eleven players in triples. Do not search it for the error — count its blocks, since a complete schedule needs 110/6 of them, which is not a whole number, so the sheet either omits a pair or repeats one. Find the failure by counting each player's appearances; one will not be 5. A verified eleven-player schedule, checked pair by pair, would demolish the argument entirely.
A picture of it
THE PICTURE #How to readThe three boxes are the kinds of thing being counted, and the two derivations in the text are two ways of reading the same picture. Follow TEAM to PAIR to BLOCK: a team belongs to n − 1 pairs, each pair sits in exactly one block, and each block containing that team supplies two of its pairs — forcing r = (n − 1)/2. Now follow TEAM to BLOCK directly and count from the other end: n teams times r blocks each equals b blocks times 3 teams each, giving b = n(n − 1)/6. The crucial cardinality is the "exactly one" on PAIR, since that is what makes both counts exact rather than approximate.
What became clearer
WHAT CLEARED #Whether a schedule exists is decided before any scheduling begins, by counting a quantity every valid schedule would have to possess and asking whether it can be a whole number. Count each player's blocks and n must be odd; count the blocks themselves and n(n − 1) must divide by 6, leaving n ≡ 1 or 3 modulo 6 and eliminating eleven with no search at all. But counting only ever forbids. That every surviving count really does admit a schedule is Kirkman's theorem, a genuinely separate achievement — and the projective plane of order 10, arithmetically impeccable and non-existent, is the reminder that passing the count buys nothing on its own.
Where to go next
ONWARD #- How finite fields construct projective planes for every prime-power order, and why no other order has ever produced one.
Key terms
TERMS #| Term | What it means |
|---|---|
| Steiner triple system | a set of triples from n points in which every pair of points appears in exactly one triple. |
| Bruck-Ryser-Chowla theorem | a number-theoretic condition ruling out certain symmetric designs, including projective planes of order 6. |
Every term the collection defines is gathered in the glossary.