The prediction held at eight and broke at ten

Nearly every cutting fails at one crane ends its count of the slit grid of connected cranes with a pattern it could see and not explain. The fewest joins that hold every crane in one piece meet a counting floor on the even grids and fall short of it on the odd: four joins on three by three against a floor of three, five on four by four against five, ten on five by five against eight, twelve on six by six against twelve — and four and six by six meet the floor in exactly one way each. It closed with a prediction the census could not test: eight by eight would need exactly twenty-one joins, and have one way to spend them.

The border is where the cranes come apart built a count that sweeps the grid one join at a time instead of trying every subset, and noted that the same count, carrying the number of kept joins alongside what it already carries, would test the prediction with no change to the method. Carried that way, the count reaches fourteen by fourteen.

The prediction holds. The pattern it was drawn from does not.

The floor, and what meeting it means #

The 1797 book Hiden Senbazuru Orikata slits a square into a grid and keeps the cranes attached at interior lattice points, each of which holds the four squares meeting there. A kept point — a join — merges the pieces those four cranes belong to. At best it merges four separate pieces into one, and then the number of pieces falls by three. The grid starts as $n^2$ separate cranes and has to end as one piece, so it needs its piece count to fall by $n^2 - 1$, and $k$ joins can make it fall by at most $3k$. That is the floor:

$$k \ge \left\lceil \frac{n^2-1}{3} \right\rceil.$$

The slack of an arrangement is how far short of that best case it falls: $3k - (n^2 - 1)$, the number of merges its joins could have made and did not, because some join touched two cranes that were already in the same piece. A slack of nought means every single join merged four pieces that were separate until it arrived. Call that a perfect tree of joins: kept joins and the cranes they hold form a tree, with no join closing a loop.

When $n$ is a multiple of three, $n^2 - 1$ is not divisible by three and the floor is rounded up, so even the best arrangement has at least one merge to spare. When $n$ is not a multiple of three, the floor is a whole number and meeting it exactly requires a perfect tree. That distinction turns out to matter more than whether the grid is even.

Twenty-one joins on eight by eight, one way #

The count sweeps the joins in order, as before, keeping for each frontier state the fewest joins that reach it and the number of arrangements that do. At eight by eight it finds twenty-one joins, the floor, and exactly one arrangement that uses so few. The prediction was right on both counts.

The arrangement has a shape that says why. Each quarter of it — a four-by-four block of cranes — is held together exactly as the four-by-four grid’s own best arrangement holds it: a join at each corner of the block and one at its middle, five joins merging sixteen cranes into one piece with nothing wasted. Four such blocks are four pieces, and the single join at the very centre of the grid touches one crane of each block and merges all four.

So the eight-by-eight tree is built by doubling. Four perfect trees of half the width, and one join in the middle, gives a perfect tree of the full width, and the joins add up exactly: four times five, plus one, is twenty-one.

Why doubling fits exactly #

The doubling construction is exact rather than lucky, and the reason is how the quarters and the centre sit on the lattice.

A grid of side $2k$ has its interior lattice points in a $(2k-1)$-by-$(2k-1)$ array. Each quarter is a $k$-by-$k$ block of cranes, and its own interior lattice points are a $(k-1)$-by-$(k-1)$ array lying strictly inside the block: every join a quarter’s tree keeps touches only cranes of that quarter. So the four quarter trees can be laid down side by side without any join of one touching a crane of another. They leave four separate pieces and nothing wasted.

What remains is the row and column of lattice points along the two lines dividing the quarters, and exactly one point on them — the centre, at $(k, k)$ — touches a crane from each quarter. Keeping it merges four pieces into one. Keeping any other point on the dividing lines would touch cranes from only two quarters and waste a merge. So the doubled tree is not just a tree of the right size; it is the only way to finish four perfect quarters into a perfect whole with one join.

That is also why four and eight by eight have exactly one perfect tree each. On four by four the four corner joins are compulsory and each already holds a corner block of four cranes, so the only join that finishes with no waste is the centre. On eight by eight each quarter must be the four-by-four tree — any other way of holding a quarter wastes a merge somewhere — and the centre finishes it. A perfect tree has no choices left in it, because every alternative wastes a merge, and a merge wasted is a join more than the floor.

Slack comes in threes #

The table has a regularity that the count shows and arithmetic explains, and it says why ten by ten is exactly one join over and no more.

Every kept join offers three merges and the grid needs $n^2 - 1$, so the slack $3k - (n^2 - 1)$ always leaves the same remainder on division by three as $-(n^2 - 1)$. When $n$ is not a multiple of three, $n^2 - 1$ is divisible by three and the slack can only be 0, 3, 6 and so on; when $n$ is a multiple of three, $n^2 - 1$ leaves a remainder of two and the slack can only be 1, 4, 7 and so on. Slack moves in steps of three, because it moves one join at a time.

The counted slacks sit exactly where that arithmetic puts them. Four, eight: nought. Ten and fourteen: three, the smallest step above nought, one join over the floor. Five, seven, eleven, thirteen: six, two joins over. Six and twelve: one, the smallest their arithmetic allows. Three and nine: four.

So a grid whose floor is a whole number either has a perfect tree or wastes at least three merges, and there is no arrangement in between that wastes one or two. Ten by ten wastes the least a non-perfect grid can: its thirty-four joins make three merges they did not need, and 7,076 arrangements find a way to waste exactly three. Twelve by twelve wastes the least its arithmetic permits, one, and 689 arrangements do that. The number of ways grows so quickly past the perfect sizes because a single wasted merge — or three — can be placed almost anywhere, while a perfect tree has nowhere to put one.

Ten by ten needs one join too many #

The obvious reading of four, six and eight was that even grids meet the floor, and that is what ten by ten breaks. Its floor is $\lceil 99/3 \rceil = 33$, a whole number, so meeting it would need a perfect tree. The count finds that no such tree exists: the fewest joins that hold ten by ten are thirty-four, one above the floor, and there are 7,076 ways to choose them.

The doubling construction explains why eight worked and suggests why ten might not. Ten by ten would be four five-by-five blocks and a join in the middle, and five by five has no perfect tree — its fewest joins are ten against a floor of eight, with six merges to spare. There is nothing perfect to double. That is not a proof that no other construction exists, and the count is what supplies the proof: every arrangement of thirty-three joins was, in effect, tried, and none holds.

The same happens at the other whole-number floors the count reaches. Five by five needs two joins above its floor, seven by seven two, eleven by eleven two, thirteen by thirteen two — fifty-eight against fifty-six — and fourteen by fourteen, whose floor of sixty-five is a whole number and whose half-width seven has no perfect tree, needs sixty-six. Among every grid up to fourteen by fourteen whose floor is a whole number, only four and eight by eight meet it.

Twelve by twelve meets its floor in 689 ways #

The multiples of three behave differently, because for them the floor is already rounded up and a perfect tree is impossible by arithmetic.

Six by six has thirty-five merges to make and twelve joins can make thirty-six, so the best it can do is one merge to spare, and it does exactly that, in one way. Nine by nine needs twenty-eight joins against a floor of twenty-seven. Twelve by twelve has 143 merges to make, forty-eight joins can make 144, and the count finds forty-eight joins suffice — the floor — in 689 ways.

So the other half of the old pattern — one way only — breaks too. Six by six’s uniqueness was a property of a grid small enough that one spare merge had almost nowhere to go. On twelve by twelve the spare merge can sit in hundreds of places.

The corrected pattern is two statements. A grid meets its floor with no merge to spare only where a perfect tree exists, and up to fourteen by fourteen that is four and eight. And a grid whose floor is rounded up can meet it with one merge to spare, as six and twelve do, without that saying anything about perfect trees at all.

Sixteen by sixteen, built rather than counted #

The doubling construction does not stop at eight. Take four copies of the eight-by-eight tree, place them in the quarters of a sixteen-by-sixteen grid, and keep the one join at the centre that touches a crane of each: $4 \times 21 + 1 = 85$ joins. The sixteen-by-sixteen floor is $\lceil 255/3 \rceil = 85$, a whole number, so the construction meets it exactly with a perfect tree.

Because the floor is a lower bound, an arrangement that meets it is a fewest arrangement, and this one is checked join by join: every crane held, one piece, eighty-five joins, no merge to spare. The same argument gives thirty-two by thirty-two with 341 joins and every power of two after it, since each doubling multiplies the joins by four and adds one, and the floor does the same:

$$\frac{(2n)^2 - 1}{3} = 4\cdot\frac{n^2 - 1}{3} + 1.$$

The grids that waste no join, among all the sizes counted, are exactly the powers of two, and every larger power of two has one by construction. Whether some larger grid that is not a power of two has a perfect tree is not settled by anything here; the count found none between four and fourteen.

A tree of fours is a quadtree #

The doubling structure has a familiar name outside paper folding, and the familiarity explains why powers of two keep appearing.

A quadtree divides a square into four quarters, divides each quarter into four again, and so on down to single cells: a tree in which every internal node has exactly four children. It is how a map or an image is indexed when regions of it need to be looked up quickly, and it fits a grid exactly only when the grid’s side is a power of two, because only then does halving always land on a whole number of cells. Graphics hardware long preferred textures whose sides were powers of two for the same reason: a stack of successively halved copies, each a quarter the size of the last, comes out even only if the original halves cleanly all the way down.

A perfect tree of joins is a quadtree turned inside out. Instead of splitting a square into four, each join merges four pieces into one, and the arrangement that does it with no waste merges quarters into halves into the whole, one join per merge, from single cranes up. A grid whose side is a power of two can be merged the way a quadtree splits, and the count says that, up to fourteen by fourteen, no other grid can be merged without waste at all.

That also puts the 1797 arrangements in a new light, though only as a question. The book’s plates draw particular arrangements of connected cranes, and whether any square grid among them is held by a tree of fours — the arrangement that keeps the least uncut paper, in the currency what one cut buys prices, and that exists only on sides of four, eight or sixteen — is something only the plates can say, and a record is not a proof is clear that a computation is no substitute for looking.

The corners and the tree #

The perfect trees also answer a small puzzle the earlier census noticed about corners.

A corner crane touches exactly one lattice point, so its join is compulsory — a fact settled at one place, in the sense local is not global draws the line: every arrangement that holds the grid keeps all four corner joins. In a perfect tree each of those four joins must merge four separate pieces, so each corner join holds the corner crane together with three cranes that no other kept join has yet reached. On four by four the four corner joins hold the four corner blocks of four cranes, and the centre join merges them. On eight by eight each quarter’s corner joins do the same inside the quarter, and the pattern repeats at every scale. The corners are where every perfect tree starts, and the doubling is the corners’ constraint applied again at each level.

On ten by ten the corner joins are compulsory as always, and something between them forces a join to close a loop. The count establishes that it must happen and does not say where or why; the drawn arrangement is one of the 7,076 ways the cost can be paid, and a hand argument that finds the forced loop is still wanting.

What the count leaves open #

The table stops at twelve by twelve and the count at sixteen. Fourteen by fourteen takes about a minute and sixteen by sixteen about nine, and the same count run that far finds sixteen by sixteen’s fewest joins to be eighty-five, the floor, in exactly one way — so the perfect tree is unique at four, eight and sixteen, and the construction above is the only one. Past sixteen each size costs several times more, and the powers of two above it are known to meet the floor by construction and not known to meet it uniquely.

It counts arrangements, not plates. Every arrangement that holds the cranes together counts the same, whether its joins are spread evenly or crowded — and a sheet held by the fewest joins is one cut short of falling apart at every one of them — and a folder choosing an arrangement would weigh how strongly each crane is held, which the census of joins already noted a count of this kind ignores.

And it says nothing about why ten by ten fails other than that it does. The half-width argument — five by five has no perfect tree to double — explains why the construction does not reach ten, not why no other construction does. The proof that none does is the exhaustive count, which is a proof of the fact and not an explanation of it.

How the fewest joins were counted #

The joins are taken one at a time, a column at a time and down each column, and each state records which frontier cranes are held and which are joined, as in the count of sound cuttings. What is added is two numbers per state: the fewest kept joins that reach it, and how many arrangements reach it with that few.

One predecessor is kept per state, so an arrangement achieving the fewest can be read back from the end. Every arrangement drawn is then checked independently — every crane held, one piece, the number of joins claimed — and the four-, five- and six-by-six counts are required to agree with the exhaustive census.

And the doubled sixteen-by-sixteen tree is checked the same way, join by join, against the floor it claims to meet.

Still open: the next whole-number floor #

Sixteen by sixteen settles its own size by construction, and the first open size is the next grid that is not a power of two and has a whole-number floor: seventeen by seventeen, with a floor of 96. Whether any grid that is not a power of two holds a perfect tree of joins is the question the count now points at, and a negative answer would make the powers of two the whole story. The count reaches it only with a larger frontier or a cleverer state, and the second is probably the way: a perfect tree’s joins never close a loop, which is a much stronger constraint than holding the grid together, and a count built around it could carry far less.

The other question is uniqueness beyond what was counted. Four, eight and sixteen by sixteen each have exactly one perfect tree, and it is the doubled one. Whether that holds for every power of two — whether the quadtree is the only way to hold a grid of side $2^k$ with no join to spare — is a statement the counts support at three sizes and that an argument about the compulsory corner joins, applied at every level of the doubling, might prove.

The habit worth carrying is about extrapolating from small cases. When a pattern holds on the first few sizes, ask which property of those sizes it is really about. Four, six and eight are even; four and eight are also powers of two; and only one of those descriptions survived ten.