An odd strip can hook its own ends

A strip of equal stamps folded flat is a pile, read from the bottom stamp to the top, with every crease an arc at one end of the pile joining the two stamps it divides. The weakest folding machine in the subject makes one move: it chooses a line across the partly folded strip and turns everything on one side over onto the other, every layer at once. Where the machine catches up found that it makes every pile of six stamps or fewer, and nine stamps have piles of their own found the first misses that were new at their length rather than inherited. The machine’s misses have no short list counted what that machine cannot make, up to thirteen stamps, and found a structure and a puzzle.

The structure was a closure. Whatever the machine can make, it can make with an end stamp missing, so every pile it misses contains a smallest miss — a pile it cannot make although it makes both piles left when either end stamp is taken off. Those smallest misses are the machine’s forbidden configurations, and there was no short list of them: 14 at seven stamps, none at eight, 160 at nine, 12 at ten, 1,194 at eleven, 116 at twelve and 7,786 at thirteen.

The puzzle was the alternation in that list. Odd lengths add obstructions by the thousand and even lengths by the hundred, and the ratio between neighbours was not settling. The only construction known to need an odd length was the tuck — an accordion with its last stamp wrapped round it and slid into the first fold — and it accounted for one pile at each odd length. Something else was making the other thousands.

A fan with an odd number of panels opens both ways #

Anybody who has folded a paper fan knows the fact the answer rests on. Pleat a strip into an accordion and look at its two ends. With an even number of panels both ends leave the folded stack on the same side; with an odd number they leave on opposite sides. That is all parity has to say about a fan, and it turns out to be most of what it has to say about the machine.

The figure states it for stamps. Crease $k$ joins stamps $k$ and $k+1$, and because the stamps are equal every crease lies exactly at one end of the pile — crease 0 on the right, crease 1 on the left, and so on alternately. Stamp 0 is joined only by crease 0, so its other edge, the free edge, is on the left. The last stamp, stamp $n-1$, is joined only by crease $n-2$, which is on the right when $n$ is even and on the left when $n$ is odd, so its free edge is on the left for an even strip and on the right for an odd one.

Now put the two ends together. On an odd strip stamp 0’s free edge is on the left, which is where the last crease lies, and the last stamp’s free edge is on the right, which is where the first crease lies. Each end of an odd strip points its free edge at the crease that holds the other end. On an even strip both free edges point left and both end creases are on the right, so each free edge points away from the other end’s fold.

That alone makes possible an arrangement only odd strips have. Call an end stamp hooked when it lies inside the fold of the far end’s crease — strictly between the two stamps that crease joins — with its free edge pointing into the fold. On an odd strip any end stamp inside the far fold is hooked, since its free edge is automatically on the fold’s side. On an even strip an end stamp can sit inside the far fold too, but its own crease is on the same side as the far one and has to nest inside it; the stamp is enclosed, not hooked, and its free edge faces the open side.

The tuck was a single hook #

Read with that word, the tuck is not a curiosity. Stamp 6 of the pile 0 6 1 2 3 4 5 lies between stamp 0 at the bottom and stamp 1 above it, which is to say inside the fold of crease 0, and its free edge points into that fold from the right. It is a hooked end. The other end, stamp 0, sits on the outside of the pile and is not hooked. Take either end stamp off and the hook disappears with it, leaving a pile the machine makes by doing the obvious thing.

The earlier essay’s explanation of why the tuck needs an odd length — on an even strip the wrap would cross the crease that joins the first two stamps — is the same fact said for one pile. What the hook adds is a description that applies to piles that look nothing like a tuck. Seven stamps have 462 foldings and 202 of them carry at least one hook; most are piles the machine makes perfectly well. The question is how the hook is distributed among the misses.

Nine in ten of the odd strips’ obstructions are hooked #

The table is the answer to the question the counts left. At seven stamps 12 of the 14 smallest misses are hooked: 8 at both ends and 4 at one. At nine, 148 of 160 — 92 at both ends, 56 at one. At eleven, 1,112 of 1,194, of which 668 are hooked at both ends. The same count at thirteen stamps, run outside the figure on the same listing, gives 7,344 of 7,786, with 4,392 hooked at both ends. The share of an odd strip’s smallest misses that carry a hook is 86, 92, 93 and 94 per cent at seven, nine, eleven and thirteen stamps, rising slowly.

An even strip contributes nothing to those columns, because it cannot: the hooked end is an arrangement only odd strips have. So the alternation in the totals is in large part the presence and absence of one arrangement, and the right comparison is the last column, the smallest misses that carry no hook. It reads 2, 0, 12, 12, 82 and 116 from seven stamps to twelve, and the counts at thirteen and fourteen, run the same way, are 442 and 740.

Those numbers still rise, and they still rise faster across an odd step than an even one: from twelve to 82 between ten and eleven stamps, from 82 to 116 between eleven and twelve, then 116 to 442 and 442 to 740. But the swing has collapsed. The totals jump by a factor of a hundred between ten and eleven stamps and by a factor of sixty-seven between twelve and thirteen; the unhooked misses jump by 6.8 and 3.8 across the same steps, and the odd step’s advantage is shrinking. Over two stamps the unhooked counts grow by 5.4 from eleven to thirteen and by 6.4 from twelve to fourteen — roughly the same rate on either parity.

The thousands at odd lengths were hooks. What is left after removing them is a list of obstructions that grows steadily with the strip, and is still not short.

A hooked pair lies face to face #

The doubly hooked piles have a shape worth seeing once. In 1 8 0 7 6 5 4 3 2, stamp 8 lies between stamps 1 and 0, inside the fold of crease 0 on the right, and stamp 0 lies between stamps 8 and 7, inside the fold of crease 7 on the left. The two end stamps touch. Each is wrapped by the other’s crease, from opposite sides, like two hooks closed on each other.

That is not peculiar to this pile. In every smallest miss hooked at both ends, at seven, nine, eleven and thirteen stamps, the two end stamps lie face to face, each inside the other’s fold, and the same is true of all but a few of the singly hooked ones — 2,896 of the 2,952 at thirteen stamps, for instance. A doubly hooked smallest miss is two hooks engaged.

The gap between the two touching end stamps has one more property, and it may be the start of an account of why the machine finds such piles hard. The gap is crossed by crease 0 on the right, since stamp 8 lies inside that fold, and by crease 7 on the left, since stamp 0 lies inside that one. The last fold of any sequence the machine makes splits the finished pile at a height crossed by creases on one side only — it folds one half over the other at a single end — so it can never fall between the two engaged ends. That is true and easy, and it falls well short of a proof that the machine misses the pile: plenty of piles have gaps crossed on both sides and are made anyway. It is offered as a reading, not an explanation.

A hook raises the odds of a miss and does not decide it #

The smallest misses are a small and special population, and it is fair to ask whether the hook matters among all the piles or only among those. The figure counts every pile. At seven stamps the machine misses 0.8 per cent of piles with no hook, 2.3 per cent of piles hooked at one end and 31 per cent of piles hooked at both. At nine the three shares are 5.1, 14.1 and 56 per cent; at eleven, 14.8, 29.4 and 72 per cent; and at thirteen, counted outside the figure, 27.5, 44.6 and 84 per cent.

So a pile hooked at both ends is several times likelier to be out of reach than a pile with no hook, at every odd length counted, and the doubly hooked piles are becoming nearly all misses. But none of the shares is a hundred per cent. At seven stamps the machine makes 18 of the 26 piles hooked at both ends, and at eleven it still makes 514 of 1,828. A hook is not a forbidden configuration in the sense the earlier essays wanted — a shape whose presence alone rules a pile out. It is the place obstructions concentrate.

The even rows say something else. A strip of eight stamps, which can carry no hook, loses 4.6 per cent of its piles; a strip of ten, 14.4; a strip of twelve, 27.0. Those are close to the unhooked rate of the odd strip one stamp longer — 5.1 at nine, 14.8 at eleven, 27.5 at thirteen. Read that way, an odd strip is an even strip’s worth of difficulty plus a set of hooked piles that the machine finds much harder, and the alternation in the smallest misses is the hooked piles’ contribution arriving every other length.

The obstructions without a hook hold their ends outside #

If the hooked piles are one family, the remaining smallest misses ought to have shapes of their own, and they do — sorted, again, by parity. The twelve unhooked smallest misses of nine stamps all put both end stamps on the outside of the pile, one at the bottom and one at the top. In 0 7 6 5 4 3 2 1 8, stamp 0 lies at the bottom, crease 0 carries the strip round to stamp 1 near the top, an accordion runs back down, and crease 7 carries it out to stamp 8 on top. The ends do not engage each other. They clasp the whole pile between them.

All 82 unhooked smallest misses of eleven stamps have that shape too, and 422 of the 442 at thirteen; the other twenty, first seen at thirteen, have both ends buried in the pile without either being hooked.

An even strip’s smallest misses have the other shape. Every one of the twelve at ten stamps and the 116 at twelve has exactly one end stamp on the outside of the pile and the other inside it. In 0 9 2 3 6 7 8 5 4 1, stamp 0 is at the bottom, and stamp 9 lies directly above it, inside the pile but not hooked — its free edge points left, and the crease that would hook it, crease 0, is on the right. At fourteen stamps 724 of the 740 smallest misses keep one end outside, and sixteen have both ends inside.

So the obstructions fall into three families by where the end stamps go — engaged with each other, clasping the pile from outside, or one out and one in — and parity decides which families a length can have. Odd strips get the first two; even strips get the third. Each family has stragglers that first appear at thirteen or fourteen stamps, which is a reminder that these are descriptions of the counts, not theorems about them.

Why the counts alternate, in one sentence #

Put together, the alternation that the machine’s misses have no short list could not explain has a short account. A strip of equal stamps has its free edges facing the far folds exactly when its length is odd; a pile with an end hooked into the far fold is much harder for the all-layers machine to make; so odd lengths acquire a family of obstructions even lengths cannot have. The hooked family is most of every odd length’s list, and the lists left when it is removed grow at much the same rate on either parity.

The account is partly proved and partly measured, and the line between the two is worth drawing. That only odd strips can hook is a theorem, and it takes one line: the sides of the first and last creases. That the machine’s reach is closed under removing an end stamp, so that smallest misses are meaningful at all, is a theorem from the earlier essay. Everything else is counted — the hooked share of the smallest misses, the miss rates by number of hooks, the three families and their stragglers — and the counts stop at fourteen stamps.

Fourteen states are one pile found the first smallest miss by grouping the misses into classes under turning. Turning is not a symmetry of the machine, which is why those classes broke at nine stamps; but turning a pile moves its bottom stamp to the top, which changes which stamps are on the outside and whether an end is hooked, so the hook is one concrete way a turn can carry a pile into or out of the machine’s reach. Whether it is the main way is a count nobody has made.

The hand’s lock and the machine’s blind spot #

There is a practical reading, the same one the earlier essay found for the tuck and wider. A hooked end is the arrangement a hand uses to lock a folded strip: slide the loose end into a fold so that the friction of the layers holds it. Paper fans, folded tickets, the closures of wrapped packets — the end tucked into a pleat is the oldest fastening in folding. On an odd strip both ends can be locked into each other’s folds at once, which is the doubly hooked pile.

That is the arrangement the press finds hardest: a laminator or a folding machine that only makes whole-stack folds misses 31 per cent of seven-stamp piles locked at both ends and 84 per cent of thirteen-stamp ones. The hand makes the lock last, by sliding an end into a fold that is already there — a move that is not a fold across the pile at all. The machine has to arrive at the same arrangement by whole-stack folds alone, and the machine that may choose its block of layers shows what is missing: given that one freedom, a machine reaches every folding of every strip tried, locks included. The arithmetic of a fan’s ends decides which strips can be locked, and the lack of that freedom decides that a whole-stack folder mostly cannot lock them.

What the counts cannot show #

Why a hook makes a pile hard is not explained. The gap between two engaged ends cannot be the last fold’s line, which is a true remark and not an argument; a pile hooked at both ends is still made by the machine 69 per cent of the time at seven stamps and 16 per cent at thirteen. A proof that a hook obstructs would have to say which hooked piles the machine reaches, and the counts here do not.

The families are descriptions with stragglers. Every doubly hooked smallest miss through thirteen stamps has its ends face to face; every unhooked odd one through eleven clasps the pile from outside and twenty at thirteen do not; every even one through twelve keeps one end out and sixteen at fourteen do not. A statement that held on every case counted until the next length is a hypothesis with a sample size — the lesson every cheap test misses a shape drew from a list of local obstructions that kept acquiring members.

The unhooked counts still alternate a little. The odd steps are 6.8 and 3.8 against the even steps’ 1.4 and 1.7; the gap is closing, but no count here says it closes.

Equal stamps, no thickness, every layer at once #

The stamps are equal, which is what puts every crease exactly at one end of the pile and makes the parity of the free edges a clean fact; on an unevenly creased strip, as the fold a machine can make treated it, a crease sits wherever its position falls and there is no hook to speak of. Paper has no thickness, so a fold turns a stack over exactly in place and an end slides into a fold without displacing it; a real lock relies on the thickness this model throws away. The machine takes every layer on one side of its line, and the counts belong to it alone; the crimping machine and the depth-limited machines of the easiest strip needs the deepest reach would need counting afresh.

The piles are the classical stamp foldings, the objects whose number Lucas asked about and Lunnon computed, counted here by building piles from the bottom up and refusing any two creases at one end whose height intervals interleave; the oldest open problem is about how many there are, and every count above sits inside those totals. The machine is the all-layers simple-fold model of Arkin, Bender, Demaine and colleagues (2004), simulated on rows of stacked cells.

Two halves and one definition, checked against each other #

The listing of piles and the simulation of the machine share no code, and they are required to agree with the layer solver pile for pile at small sizes before any larger count is believed; the machine must never finish a pile the listing calls impossible. On top of that, every pile must have its hooks counted from its creases alone — an end inside the far end’s fold with the fold on its free side — and the figures require that no pile of an even strip has one and that some pile of every odd strip does. Every smallest miss drawn above is required to be missed with both its shrunk piles reached, and the table requires that no even strip’s smallest miss is hooked, that most of every odd strip’s are, and that removing the hooked piles shrinks the largest step between neighbouring lengths at least tenfold.

Still open: what a hook costs the machine #

The machine’s reach on hooked piles is the place an explanation would start. At eleven stamps it makes 514 of the 1,828 piles hooked at both ends, and those 514 are a small, structured set: if they share a feature the missed ones lack — the depth at which the engaged ends sit, or whether the accordion between them runs one way or alternates — that feature would be the obstruction the hook only signals.

The three families can each be counted alone, and each might have a formula where the totals have none. The doubly hooked smallest misses number 8, 92, 668 and 4,392 at seven to thirteen stamps; the clasping ones 2, 12, 82 and 422. Two sequences with simple shapes would be a better description of the machine than one sequence without one.

Sideways from here, a machine that can only crimp folds two adjacent creases at once and cannot fold an odd number of creases at all, which is a parity of another kind; whether its obstructions also split by where the ends go would say whether the hook belongs to this machine or to strips. And two stacks shuffled in glued pairs found that a Miura’s folded states are counted by interleavings of its columns’ stacks — the same kind of description by how pieces nest, applied to a sheet instead of a strip.

The habit worth carrying is about alternating counts. When a count alternates with parity, look for an arrangement only one parity can make, and count without it. Here the arrangement was an end stamp facing the far fold, the reason was a fan’s arithmetic, and what was left after removing it was a list that grows at much the same rate on both sides.