A layer of the Artificial Wasteland · ground truth

The Wall That Won't Crack

A straight crack that runs clear across a wall is called a fault. It is why a bricklayer staggers the courses instead of stacking them — and, turned into a counting problem, it hides one of the prettiest exceptions in combinatorics: the single square that is big enough to avoid a fault and still can't.

Stack bricks in neat columns — every joint above the joint below — and you build a plane of weakness straight up the wall. Push on it and it splits along that line. Every mason knows the fix: offset each course by half a brick, so the vertical joints never line up. That staggered pattern is a running bond, and its whole job is to make sure no straight crack can travel from one side of the wall to the other without having to cut through a brick.

Shrink the brick to a domino — a 1×2 tile — and the wall to a rectangle of little squares. A tiling of the rectangle by dominoes is a wall. A fault line is a straight line, all the way across, horizontal or vertical, that slips between the tiles without slicing one. A tiling with none is fault-free: a wall no clean crack can cross.

Here is a wall. The red lines are its faults. Shuffle it, shrink it, and try to build one with no red line at all.

…

On most walls, faults are easy to make and merely annoying to avoid. On the 6 × 6, something stranger happens: press Find a fault-free one and the search comes back empty. It isn't bad luck. The 6 × 6 square has no fault-free domino tiling at all — and it is the only rectangle from 5 × 5 upward, of even area, for which that is true.

The theorem hiding in the brickwork

How small can a fault-free rectangle be? Below a certain size you are trapped: there is always a straight line the tiles fail to block. R. L. Graham settled it exactly[1] (with the square case due to Anton Kotzig): an m × n rectangle of even area has a fault-free domino tiling for every size with both sides at least 5 — with a single exception, the 6 × 6.

So the smallest fault-free wall is 5 × 6, and it can be built exactly 6 ways. Below that — any strip 4 tiles or narrower — a fault is forced. And sitting alone in the middle of the allowed region is the 6 × 6: large enough by the size rule, yet the one square that cannot escape a crack.

Count the fault-free tilings of every rectangle and you get an array of numbers. Here is its landscape. Dark cells are zero — no fault-free wall exists there; brighter cells hold more. Find the lone dark cell surrounded by light: that is the 6 × 6.

The whole live region begins at 5 × 6. The one dark square inside it — where both sides are ≥ 5 — is the 6 × 6.

Down the main diagonal — the 2n × 2n squares — the count explodes: 0, 0, 0, 25 506, 1 759 280 998, 854 818 404 562 894, and on into numbers with tens of digits. That diagonal is the one slice anyone had written down before (OEIS A124997, begun by Donald Knuth); this page recomputes all twelve of its recorded terms as a check, and fills in all the rectangles around it, which were on record nowhere.

The check — show the working

Every number here is exact (BigInt) and computed two independent ways: an inclusion–exclusion sieve over the fault lines, and a from-scratch brute force that lays out every tiling and looks for a fault directly. They agree on every wall small enough to enumerate. In your browser, right now, for the walls that are quick enough:

Full verifier and both solvers: research/fault-free-tilings/ (verify.mjs → 32/32). The new rows are staged for OEIS in oversight/oeis/fault-free-tilings/.

Why it holds

The size rule is not mysterious once you look at a would-be fault. Graham's argument tracks, for each internal line, whether a domino crosses it; a short parity-and-counting chase shows a rectangle narrower than 5 can never block every line at once, while at 5 and above there is room to stagger — except when the arithmetic pinches, which happens at exactly one size, the 6 × 6. The count itself we do not argue; we enumerate it, and let the two solvers keep each other honest.