No odd grid holds a perfect tree

The connected cranes of the 1797 Hiden Senbazuru Orikata are folded from one square slit into a grid, the cranes left joined at some of the interior lattice points. A join keeps together the four cranes whose corners meet there, so a grid of $n^2$ cranes can be held in one piece by as few as $\lceil (n^2 - 1)/3 \rceil$ joins, and only if every join merges four pieces that no earlier join had reached. That arrangement, when it exists, is a perfect tree of joins.

The prediction held at eight and broke at ten counted the fewest joins exactly from three by three to fourteen by fourteen, by the join-at-a-time count that the border is where the cranes come apart built for a different question. Perfect trees turned up at four and eight, each in one way; ten, twelve and fourteen had none; sixteen had one by construction, four copies of the eight-by-eight tree with a join in the middle. It ended pointing at seventeen by seventeen, the next grid that is not a power of two and whose floor, ninety-six, is a whole number.

Seventeen does not need a count. No odd grid holds a perfect tree, and the reason is a colouring.

Two joins side by side waste a merge #

Colour the interior lattice points like a checkerboard: a point is one colour if its two coordinates add to an even number and the other colour if they add to an odd one. Neighbouring points across a crane’s edge are opposite colours; points diagonally across a crane are the same colour.

Now take two joins at lattice points side by side, one crane-width apart along a row. The first keeps its four cranes together; the second keeps its four; two of those cranes are the same two, the pair lying between the two points. Once the first join has made those two cranes one piece, the second join can merge them with at most two further cranes — three pieces into one where a perfect tree needs four. A merge is wasted, and a perfect tree wastes none.

So a perfect tree never has two joins side by side. Two joins diagonally across a crane share only that one crane, which is allowed: the second join merges the first’s piece with three new cranes, exactly as it should. Every join of a perfect tree is therefore diagonal to every join it touches, and diagonal points are the same colour. Joins that touch nothing of each other can in principle be any colour — but a perfect tree is a single piece, every join linked to every other through a chain of shared cranes, so the whole tree lies on one colour.

The corners settle it #

A crane at a corner of the sheet touches exactly one interior lattice point — the one diagonally in from the corner. If that point is not a join, the corner crane is attached to nothing. So all four corner points must be joins, in any arrangement that holds the grid together, as which cranes can stay joined already used on the smallest grids.

On an $n$-by-$n$ grid the four corner points are at $(1, 1)$, $(1, n-1)$, $(n-1, 1)$ and $(n-1, n-1)$. Their coordinate sums are $2$, $n$, $n$ and $2n - 2$. When $n$ is even all four sums are even and the four points are one colour; when $n$ is odd two sums are odd and two even. A perfect tree must contain all four and must lie on one colour, and on an odd grid it cannot do both.

That is the whole proof, and it rules out every odd grid at once: five, seven, eleven, thirteen, seventeen, nineteen and every larger odd side, whatever its floor. Combined with the count — the floor $(n^2 - 1)/3$ is a whole number only when $n$ is not divisible by three — it leaves the even sides not divisible by three: two, four, eight, ten, fourteen, sixteen, twenty, twenty-two, and so on. The count to fourteen found no perfect tree on any odd grid for exactly this reason, and part of its work went on confirming, one grid at a time, a result a colouring gives in one line.

A tree on one colour #

The colouring does more than exclude. It turns the question on the even grids into a much smaller one.

Keep only the lattice points of the corners’ colour. Each crane has four corners, two of each colour, so each crane has exactly two corners of the tree’s colour — or one, for a crane on the rim of the sheet, whose other corners lie on the edge. A perfect tree must hold every crane, so every crane must have a join at one of its corners of that colour; and two joins that share a crane are the two same-coloured corners of that crane, so the joins linked by shared cranes are exactly the diagonal neighbours among them. The tree condition is then that those diagonal links form a tree: connected, and with no loop.

The count comes for free. If every crane is held and the links form a tree, then each crane is held by one join or, if it is the crane between two linked joins, by two; with $J$ joins and $J - 1$ links that accounts for $4J - (J - 1) = 3J + 1$ cranes, which is $n^2$ exactly when $J = (n^2 - 1)/3$. A set of one colour’s points that holds every crane and whose diagonal links form a tree is a perfect tree, and nothing else is.

The eight-by-eight tree, drawn that way, is a visible tree: twenty-one joins on one colour, linked by the twenty cranes they share, in the doubled crosses that the quadtree reading describes. Every crane not on a link is held by exactly one join.

Searching one colour #

A search over which lattice points to keep joined, on one colour only, is small in a way the full count was not. The eight-by-eight grid has forty-nine lattice points and $2^{49}$ ways to choose among them; its tree’s colour has twenty-five, and twelve of those are decided at once by the rim.

The search takes the colour’s points in diagonal order and decides each one kept or cut. It refuses a choice the moment a loop closes, checked by a union of pieces that merges each new join with the kept joins diagonal to it; it refuses when a crane’s last corner of the colour is decided and none of them is kept; it holds the number of joins to $(n^2 - 1)/3$; and it refuses as soon as some group of kept joins has no undecided neighbour left through which it could reach the others. Every tree it finds is handed back to the same join-by-join check the full count used — every crane held, one piece, no merge wasted.

It reproduces everything the full count found: one perfect tree on two, four and eight by eight, none on ten or fourteen. It then goes past where the full count stopped. Sixteen by sixteen, where a perfect tree was known to exist because it could be built, is now counted: exactly one, eighty-five joins. Twenty by twenty, the next even grid not divisible by three, needs 133 joins for a perfect tree and has none.

So the even grids to twenty with a perfect tree are two, four, eight and sixteen, and each has exactly one. Four sizes of the same answer are more than the full count had, and all of it is now a count rather than a construction: the powers of two and nothing else, each in exactly one way.

Sixteen by sixteen is the doubled tree #

That the sixteen-by-sixteen grid has exactly one perfect tree says something the construction could not: the doubled tree is not merely one perfect tree, it is the only one.

The search finds it without being told about doubling, and it matches the doubled construction — four copies of the eight-by-eight tree in the quarters, one join at the centre — at every one of its 225 lattice points. Uniqueness at four, eight and sixteen is now a measurement rather than a pattern, and the doubled trees are the whole of what exists at those sizes.

That is the half of the earlier essay’s open question that the colour makes answerable by counting. The other half — whether the quadtree is the only perfect tree at every power of two — still wants an argument, and the colour at least says what kind of argument: the tree lives on a rotated grid of one colour, its corner points are forced, and the doubling places four copies of a smaller tree so that their corner points meet at the middle of the larger one.

Why doubling keeps the colour #

The doubling construction and the colour fit together exactly, and seeing why is the clearest way to see what the construction is.

Take a perfect tree on a $k$-by-$k$ grid, with $k$ even, so that its joins lie on the colour whose coordinate sums are even. Place four copies in the quarters of a $2k$-by-$2k$ grid. The copy in the top left keeps its coordinates; the other three are shifted by $k$ along one axis, the other, or both. Shifting by an even number changes no coordinate sum’s parity, so every join of every copy lands on the even colour of the large grid. The one join added at the middle sits at $(k, k)$, whose sum $2k$ is even too. The doubled tree is on one colour because every piece of it is.

The middle join is also where the four copies’ corners meet. Each quarter’s own corner join nearest the centre sits at $(k-1, k-1)$, $(k-1, k+1)$, $(k+1, k-1)$ or $(k+1, k+1)$ in the large grid’s coordinates, and all four are diagonal neighbours of $(k, k)$. The middle join links four trees through four shared cranes, one to each quarter, and merges four pieces — the four quarters — into one, which is exactly the merge a perfect tree needs from it.

On a grid whose side is not a power of two the same picture cannot be drawn, and the colour says what goes wrong with the obvious attempts. Ten by ten would need quarters of five by five, and five is odd: the quarters’ own corners are two colours, so a perfect tree on each quarter does not exist to place. Fourteen would need quarters of seven, odd again. Twenty would need quarters of ten, which are even and have no perfect tree of their own. Every non-power-of-two even side halves, sooner or later, to an odd one, and an odd grid has no perfect tree to contribute. That is not a proof that no other construction exists — the search is what shows there is none to twenty — but it is why doubling alone can only ever reach the powers of two.

The sizes still open #

Between sixteen and thirty-two, which has a perfect tree by doubling, the colour and the floor leave three even sides open: twenty-two, twenty-six and twenty-eight. Each needs its floor in joins — 161, 225 and 261 — on one colour of its lattice, with the rim’s ring forced, and each is out of the present search’s reach in a reasonable time. If the powers of two are the whole story, all three have none; if any of them has a perfect tree, it is a tree built some way other than by doubling, and it would be the first of its kind.

What the rim decides #

The corners are not the only forced joins. A crane anywhere along the rim of the sheet — not only at a corner — has one corner on the edge and one of each colour inside, so it has exactly one corner of the tree’s colour, and that point must be kept.

The forced joins form a ring of every other point just inside the rim: four of the four-by-four tree’s five joins, twelve of the eight-by-eight’s twenty-one, twenty-eight of the sixteen-by-sixteen’s eighty-five. The share falls from eighty per cent to a third as the grid doubles, so the rim decides less and less of the tree and the middle more — the reverse of the cuttings that come apart, which the border is where the cranes come apart found failing at the rim, and of the ones nearly every cutting fails at one crane found failing at a single crane — and on these grids the middle is still decided completely, in exactly one way.

That is the sense in which local is not global: each forced join is settled by a single crane at the rim, and the remaining joins are settled by nothing local at all, only by the requirement that the whole be one piece with no loop. On ten by ten, fourteen by fourteen and twenty by twenty the rim’s ring is forced exactly as on the powers of two, the count of joins works out, and no way of completing the middle is both one piece and free of loops. The colour does not say why.

What the colour assumes #

The joins are at interior lattice points and each holds four cranes. That is the 1797 book’s arrangement as the earlier essays read it: cranes joined at the corners where four meet. A join along the middle of an edge, holding two cranes, would be a different object with different counts, and the book does not use one.

A perfect tree is defined by its merges. Every join merges four separate pieces, so the tree is a set of $(n^2 - 1)/3$ joins with no merge wasted. An arrangement with a merge to spare is not a near-miss of a perfect tree but a different kind of arrangement entirely — each of the ten-by-ten grid’s 7,076 fewest arrangements has one join more than a perfect tree would, and three merges to spare.

The search is exhaustive within the rules above. It decides every point of the colour and refuses only on conditions that no perfect tree can meet; the number it reports is the number of perfect trees, not a lower bound. It does not reach twenty-two by twenty-two in reasonable time, and nothing here is said about any grid larger than twenty that is not a power of two.

And the book’s plates are not consulted. Whether any arrangement drawn in 1797 is a perfect tree — which would mean a square grid of four, eight or sixteen cranes a side, joined in the doubled pattern — is a question about the plates, and a record is not a proof applies in the other direction as well: a proof about arrangements is not a record of any.

A checkerboard inside a crane pattern #

The surprise here is where the colouring comes from. Two-colouring is the first theorem of flat folding: the panels of any flat-foldable crease pattern can be coloured in two colours so that neighbours differ, and a contradiction is even and its companions are built on it. The slit grid of cranes has a two-colouring of its own, on the lattice points rather than the panels, and it does the same kind of work: it turns a question about a whole arrangement into a question that can be settled at a few places.

It also turns a pattern into a reason. The earlier count found perfect trees on the even grids four and eight and not on the odd grids, and read it first as a fact about evenness, then as a fact about doubling. The colour says both readings had part of it. Evenness is necessary, because of the corners; it is not sufficient, as ten, fourteen and twenty show — the same shape of result even is not enough found for a two-colouring on crease patterns; and the powers of two are, so far, the only even sides on which the middle of the tree can be completed.

Still open: why ten, fourteen and twenty fail #

The search establishes that no perfect tree exists on ten, fourteen or twenty by twenty and does not say why. A hand argument now has a precise target. On one colour of a ten-by-ten grid there are forty-one lattice points, the rim forces sixteen of them, and a perfect tree must keep thirty-three: it must cut exactly eight, no two of them diagonal neighbours, and those eight must break every loop in the colour’s diagonal graph. That graph has twenty-four independent loops and each cut point breaks at most three, so the eight cuts must break exactly three each with nothing wasted — and every loop must still be broken by them, not merely the right number of loops. Showing that no eight points of that colour can do it on a ten-by-ten would be the argument, and it would very probably say what is special about a power of two, where on eight by eight four cuts do it in exactly one way.

The other direction is the next sizes. Twenty-two by twenty-two is beyond the search as it stands; a transfer along the diagonals, carrying only the pieces the last diagonal touches, would reach it and the sizes after, and would say whether the powers of two stay alone as far as anybody cares to count.

The habit worth carrying is about searching before thinking. When an exhaustive count keeps confirming a pattern, look for the invariant that would make the count unnecessary. The count from three to fourteen spent most of its work on odd grids that a colouring rules out in a line, and the colouring, once found, made the even grids small enough to count further than the full search could reach.