Allowed, and Impossible

A counting condition is always necessary for a thing to exist — and sometimes it is the whole story. But not always. Here are objects that pass particular necessary counting tests and still cannot be built. The arithmetic gives permission; permission is not existence.

In 1782 Leonhard Euler posed a parade-ground puzzle. Take thirty-six officers — six ranks drawn from each of six regiments — and seat them in a 6×6 square so that every row and every column shows each rank once and each regiment once. No two officers in any line share a rank; none share a regiment. Euler tried, and failed, and conjectured it was impossible. He was right about 6 — but for the wrong reason, and the proof would wait more than a century.

Nothing in the counting forbids it. Six ranks fit in six columns; six regiments fit in six rows; the books balance perfectly. The square should be there. Try to find it.

The parade ground

Each cell is an officer: a regiment (colour + letter A–F) over a rank (the digit 1–6). Tap a cell to advance its rank. Your goal: make both the colours and the digits form a Latin square (each appears once per row and column) and have all 36 officers be different. The readout tracks how close you are.

You will get close. You can make the regiments a perfect Latin square and the ranks a perfect Latin square — that part is easy. What you cannot do is make all thirty-six officers distinct at the same time. Two of them always collide: somewhere, the same rank from the same regiment appears twice, and fixing it breaks something else. The hunt button throws three thousand random rank-squares at your regiments and keeps the best it finds; watch the distinct count crowd toward 36 and stop short, every time.

Proof, in your browser

"I couldn't find it" is not "it isn't there." So here is the actual proof: not an argument, a search. A Latin square of order 6 has an orthogonal mate exactly when it can be cut into six disjoint transversals (a transversal picks one cell per row, all in different columns, all different symbols — these are the cells the partner square would mark with a single symbol). And "can be cut into transversals" is unchanged when you permute rows, permute columns, or rename symbols — the very moves that reduce a Latin square to standard form (first row and first column in order). So checking every reduced square checks every square there is.

There are exactly 9408 reduced Latin squares of order 6. The button below generates all of them and asks each whether it splits into six disjoint transversals. It runs in a fraction of a second, right here:

Zero. Not one of the 9408 has an orthogonal partner, so no 6×6 Latin square does, so the thirty-six officers cannot be seated. Gaston Tarry announced the result in 1900 and published the detailed account in 1901, sorting the order-6 squares into cases; the loop above does the same census in the time it takes to blink. (As a sanity check the same routine confirms order 4 and order 5 do have orthogonal pairs — the failure is special to 6, not a bug in the search.)

Where the officers do stand: order 5

The property is real and reachable — just not at six. At order 5 the officers line up with room to spare. Build the two squares from arithmetic: regiment (i+j) mod 5, rank (i+2j) mod 5. Because the map (i,j) ↦ (i+j, i+2j) is invertible mod 5, every one of the 25 rank-and-regiment pairs is different. All twenty-five officers stand:

The pattern: necessary is cheap, sufficient is dear

Pull back. A counting condition — a sum that must come out even, a volume that must divide a power, a number that must be a sum of two squares — is something a valid object is forced to satisfy. Checking it is arithmetic, and free. The trap is reading the implication backwards: passing the count is permission, not a certificate. Here are two more places the count says yes and the answer is no.

The phantom code whose sphere volumes add up

An error-correcting code surrounds each message with a sphere of near-misses; the code is perfect when those spheres tile the whole space of strings with no gap and no overlap — which forces an exact identity, M · (volume of one sphere) = 2ⁿ. Set the radius to 2 and the length to 90 and watch it close to the bit:

The plane the arithmetic let through

A finite projective plane of order n is a perfectly balanced incidence of points and lines. The Bruck–Ryser–Chowla theorem supplies a counting gate: for n ≡ 1 or 2 (mod 4), a plane can exist only if n is a sum of two squares. Try it on any order:

Order 6 is stopped at the gate: 6 is not a sum of two squares, so no plane of order 6 (consistent with the officers). Order 10 strolls straight through — 10 = 1² + 3² — and the gate is satisfied. Yet in 1989 Lam, Thiel and Swiercz ended a search of thousands of computer-hours with the verdict that no projective plane of order 10 exists. The count had nothing more to say; only the exhaustion did. Order 12 is past the gate too, and to this day nobody knows whether its plane exists — the count's silence, still unbroken.

And where the count is the whole story

Lest this read as a sermon against counting: often the necessary condition is also sufficient, and then the arithmetic settles everything. A Langford pairing — lay 1,1,2,2,…,n,n so the two k's have k numbers between them — exists exactly when the triangular number T_n = n(n+1)/2 is even, i.e. n ≡ 0 or 3 (mod 4). The parity is forced (necessary); a construction by Roy Davies (1959) covers every case it allows (sufficient). The verifier below checks both halves agree through n = 11 — there, the count is the truth, no gap left to fall into.

The honest shape, then, is this: a counting condition is a filter, never a maker. It can rule a thing out for free; it can never, by itself, rule it in. The distance between "the books balance" and "the object exists" is exactly where the mathematics lives — sometimes nothing, sometimes a century of cases, sometimes a question still open.

The check

Everything quantitative here is recomputed from scratch and kept apart from what is cited. The order-6 census above runs live; the same routine runs offline in research/allowed-and-impossible/verify.mjs (33/33): the reduced-square counts 1, 1, 4, 56, 9408 (a self-test of the generator); MOLS existing for orders 3, 4, 5 and failing for 2 and 6; the order-5 superposition with all 25 pairs distinct; the phantom's 1 + 90 + C(90,2) = 4096 = 2¹² and 2⁷⁸ · 2¹² = 2⁹⁰; the sum-of-two-squares facts behind Bruck–Ryser; and the Langford parity matched to brute force through n = 11. Proven here: the non-existence of order-6 orthogonal squares (exhaustive), every arithmetic identity, the order-5 construction. Cited, not re-derived: the perfect-code classification (van Lint, Tietäväinen); the non-existence of the order-10 plane (Lam, Thiel & Swiercz, 1989); the Bose–Shrikhande–Parker resolution of Euler's conjecture; Langford sufficiency (Davies, 1959) — each far beyond a from-scratch check.

A layer of Artificial Wasteland. Related: A Message That Heals Itself (the phantom in full), The Arrangement You Can't Always Make (where the count decides), and Each Interval, a Different Number of Times (a count that turned out older than it looked).