Origami & Folding
what one sheet can do
Concept

Stamp folding — where it appears

The one-dimensional version of map folding: a strip of stamps folded into a pile. Its counts are known and published, so they are the ground truth an implementation can be checked against.

Named by 15 essays across 2 fields — each of them below, with the objects they name alongside it.

MVMV123455 segments, 4 creases12345the stack, solvedassignmentsMVMVvalid stacks1decided byexhaustive searchover the orderingsthe folded positions come from the crease spacing; the assignment only decides which way each turn wraps

A strip is decidable

Take the same problem down one dimension and it stops being hard. The reason is not that strips are small — it is that overlaps on a line form a chain, and chains cannot contain the cycles that make the two-dimensional question intractable.

flat-folding · Flat-foldability 1 × 4161 × 5501 × 61442 × 282 × 3602 × 43203 × 31,3684 × 4300,608filled — counted here, by exhaustive search over stacking ordersopen — Lunnon's published count, quoted rather than computed

The oldest open problem

In how many ways can a map be folded? The question needs no notation to state, the answer is a small integer for small maps, and after sixty years there is still no formula — only a list of numbers, each one found by searching every possibility.

complexity · Map folding mapflat foldingsand what it took2 × 284 cells, computed here2 × 3606 cells, computed here2 × 43208 cells, computed here3 × 31,3689 cells, computed here2 × 51,9800.6 s3 × 415,55254 s4 × 4300,608not reached herethe 1 × n case is the strip, and it is the only row of this table with a fast methodnobody has a formula for any entry, and nobody has proved there is none

The answer is bigger than the question

A twelve-square strip of stamps is twelve numbers of input and 146,376 objects of output. No algorithm writes that faster than it can be written, so 'efficient' has to be measured against the answer rather than against the question — and in folding that is the normal case.

complexity · Hardness of folding 2468101222.22.42.62.833.23.4stampsratio to the term beforeodd terms, from aboveeven terms, from belowfilled: computed here, to 9 stamps · hollow: 10 and 11 and 12, computed once and quoted4,536 foldings at 9 stamps

Where the exponent comes from

The number of ways a strip of stamps folds grows exponentially, and the base of the exponential is a number nobody has proved exists. The ratio of one term to the last climbs past three and is still climbing where the computation stops — which is the only structural handle anybody has on the sequence.

complexity · Map folding creases at 0.25, 0.50, 0.75, marked MMM3 legal stackings of 4 segments, read from the bottom of the pile up12341: 2 · 1 · 4 · 3assignment12342: 4 · 2 · 1 · 3taco-taco12343: 2 · 4 · 3 · 1taco-tacothe paper lands in the same place every time — only the order through the pile differs

More than one way to lie flat

A crease pattern with its mountains and valleys marked is spoken of as though it named a folded object. It does not. The legal stackings can be counted exactly in one dimension, the count is routinely more than one, and its size is a property of the pattern that nobody quotes.

flat-folding · Layer multiplicity 1 × 4161 × 5501 × 61442 × 282 × 3602 × 43203 × 31,3684 × 4300,608filled — counted here, by exhaustive search over stacking ordersopen — Lunnon's published count, quoted rather than computed

Two directions that will not separate

A map has rows and columns, and a strip of stamps is a map with one row. The obvious hope is that the two-dimensional count is built from the one-dimensional one — fold the rows, then fold the columns. It is not: a two-by-three map folds 60 ways against a product of 12, and the discrepancy grows from a factor of two to a factor of thirty-eight over the counts anybody has.

complexity · Map folding how many ways each map foldsa strip of five50of 120a plus120= 5! — every stackinga tee120= 5! — every stackinga two-by-three60of 720a two-by-three, one gone40of 120one corner gone848of 40320the middle gone8016of 40320the full square1368of 362880

The map that is not a rectangle

Take one square out of a three-by-three map and the number of ways it folds does not go down by an eighth. It goes up — to 848 if the square came from a corner, and to 8,016 if it came from the middle. Two maps of eight squares in the same box, differing by nearly a factor of ten, and no function of the box tells them apart.

complexity · Map folding the bar is every legal stacking; the dark part is the ones with no move out of thema swap is legal when the result is still a stacking — the two layers need not be joined by a crease3 segments2 of 6 isolated · 4 legal moves4 segments16 of 16 isolated · 0 legal moves5 segments34 of 50 isolated · 16 legal moves6 segments144 of 144 isolated · 0 legal moves7 segments366 of 462 isolated · 96 legal moves

Nothing slides past anything

A marked strip has several legal stackings and this site has counted them at length. Nobody asked whether a folder holding one can reach another by lifting a flap over its neighbour: five hundred and sixty of six hundred and seventy-two stackings have no such move at all, and whether any exists depends on the parity of the segment count.

flat-folding · Layer multiplicity the pale bar is the published count, the dark one the objectsneither operation ever fixes a folding; doing both sometimes does, and that is why it is not a quarter2 stamps2 labelled · 1 objects · 2 fixed by doing both3 stamps6 labelled · 2 objects · 2 fixed by doing both4 stamps16 labelled · 5 objects · 4 fixed by doing both5 stamps50 labelled · 14 objects · 6 fixed by doing both6 stamps144 labelled · 38 objects · 8 fixed by doing both7 stamps462 labelled · 120 objects · 18 fixed by doing both8 stamps1392 labelled · 353 objects · 20 fixed by doing both

The count counts labels

One, two, six, sixteen, fifty, a hundred and forty-four: the oldest sequence in the subject counts foldings of a strip of numbered stamps. A folded strip of blank paper has no first stamp and no top side, and neither of those operations ever leaves a folding alone — so the count of objects is 1, 2, 5, 14, 38, 120, and it is not the count over four.

complexity · Map folding the pale bar is every folded state; the dark one is the states the machine reachescounted over every marking of the strip that folds at all3 equal stamps12 of 12 reached4 equal stamps32 of 32 reached5 equal stamps100 of 100 reached6 equal stamps288 of 288 reachedcreases at .13 .31 .62 .780 of 24 reached — 24 missedcreases at .08 .24 .28 .35 .720 of 48 reached — 48 missed

Where the machine catches up

The weakest machine in the subject folds every layer at once and is stopped by a strip with two creases in it. On a strip of equal stamps it is stopped by almost nothing: every one of the 288 folded states a six-stamp strip has is reachable by a sequence of all-layers folds, and on every unevenly creased strip tried it reaches none of them. At seven stamps the completeness ends, and finding out where it ended is what checking it past six was for.

complexity · Simple foldability the bar is the number of foldings, on a logarithmic scaleboth routes give the number printed; a disagreement anywhere would be a defect in one of them2 × 122 letterings · 1 creases3 × 164 letterings · 2 creases4 × 1168 letterings · 3 creases5 × 15016 letterings · 4 creases6 × 114432 letterings · 5 creases2 × 288 letterings · 4 creases3 × 26032 letterings · 7 creases4 × 2320128 letterings · 10 creases3 × 31,368256 letterings · 12 creasesa strip of stamps is the one-row case, and the classical sequence 2, 6, 16, 50, 144 is the top of the table

The map counted from the layers

The classical map-folding counts are computed from a rule that never places a panel: work out which edge of the folded square each fold wraps around, and refuse the orderings that interleave two folds at one edge. Place the panels instead and order them by the general non-crossing rules, and the same numbers come out — 2, 6, 16, 50, 144, 8, 60, 320, 1368 — on nine sizes, by machinery that shares no line of code with the first.

complexity · Map folding the bar is how many letterings pass every condition at every vertexand the note is how many of those close a loop in the arcs2 by 122 panels · 2 letterings pass every vertex · 0 close a loop3 by 143 panels · 4 letterings pass every vertex · 0 close a loop4 by 184 panels · 8 letterings pass every vertex · 0 close a loop5 by 1165 panels · 16 letterings pass every vertex · 0 close a loop2 by 284 panels · 8 letterings pass every vertex · 0 close a loop3 by 2326 panels · 32 letterings pass every vertex · 0 close a loop4 by 21288 panels · 128 letterings pass every vertex · 0 close a loop3 by 32569 panels · 256 letterings pass every vertex · 4 close a loopa map's difficulty is not here — it is in the rules about which panels may lie between which

The test that never fires on a map

The cheapest refusal this collection has reads a crease list once and reports that no arrangement of the layers exists. Enumerate every labelling of every map from two panels to nine and it fires on four of the four hundred and fifty-four — all four on the largest map, none at all below it. On the oldest open problem in the subject, the cheap test has essentially nothing to say.

complexity · Map folding the period cell of the gridone period, with its neighbours round it1 interior vertices in the cell4 crease pieces drawnperiod 1.000 × 1.000one square, because a grid repeats at every linethe cell is a rectangle of ordinary paper until somebody says its edges are one edge

A map with no edges

Counting the ways a rectangular map folds is the oldest open problem in the subject, and every version of it assumes the map has an edge. Join the map's opposite edges and the question changes shape: half the sizes have no folded state at all, and the ones that do have no bottom layer to count from.

complexity · Map folding the pieces that are one panelleft and right edges identified — 9 pieces, 6 panels9 pieces on the drawing6 panels on the sheet10 creases, 4 verticeskeeps the sidetwo pieces of one shade are one piece of paper, a cell apart

The tube a map makes

Join one pair of a map's edges and the result is a tube — a real object, foldable in the hand, and neither the strip's problem nor the torus's. It has one loop that cannot be shrunk instead of two, it keeps its bottom layer because it keeps half its rim, and half its sizes are refused by a parity the flat map does not have.

complexity · Map folding the pale bar is every folded state the strip has; the dark one is what the machine reachesthree machines on the same strips, and none of them is the flat-folding theorem3 equal stamps · takes every layerall 123 equal stamps · takes one layer4 of 123 equal stamps · takes any block reaching an edgeall 124 equal stamps · takes every layerall 324 equal stamps · takes one layer4 of 324 equal stamps · takes any block reaching an edgeall 325 equal stamps · takes every layerall 1005 equal stamps · takes one layer4 of 1005 equal stamps · takes any block reaching an edgeall 1006 equal stamps · takes every layerall 2886 equal stamps · takes one layer4 of 2886 equal stamps · takes any block reaching an edgeall 288counted over every marking of the strip that folds flat at all

Deciding is not making

Four earlier essays here ask which machines can flatten a strip at all, and the answer sorts them into a lattice with one column full and three with holes in it. Asked instead what each machine can produce, the three sort completely differently: the machine that may choose its block reaches every folded state of every strip tried, the machine that takes one layer reaches exactly four whatever the strip is and however long, and the machine that takes the whole pile is the only one whose answer depends on the spacing at all.

complexity · Simple foldability

Named alongside it

The objects these essays reach for when they reach for this one.

Map foldingEnumerationLayer orderingCombinatorial explosionThe counting problemLunnon's countsLayer orderOne-dimensional foldingOpen problemStackingThe all-layers simple foldFolded state

All concepts