Origami & Folding
what one sheet can do
Concept

Map folding — where it appears

The problem of counting how many ways a creased rectangle can be folded into a stack. It is unsolved in two dimensions, it is the oldest open problem the subject has, and the counts are known only where a search can exhaust them.

Named by 20 essays across 3 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 6 creases, 7 segments, assignment MVMVMVDoes it fold flat?at most 5,040 orderings, and it may stop earlyyesas far as the first legal oneHow many ways?every one of them, because the last is as likely as the first15,040 orderingsWhat are they?the same search, paying a second time for what it keeps1 stackings, written out5,040 orderings, and the answer as wellCan a machine make it?a different search, over sequences of folds rather than over stackingsno1,275 statesthe four are not four difficulties of one problem — they are four problemsthe cost is work rather than time — a clock reading would differ on every build

Four questions about one sheet

Deciding, counting, listing and optimising are not four difficulties of one problem. They are four problems, and folding is the subject that proves it: a ruled map is trivial to decide and unsolved to count, while a general crease pattern is the other way round.

complexity · Hardness of 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 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 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 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 grid a division makes

Dividing a square into thirds in both directions is a construction: four creases, each exact, each landing on a rational the ladder can name. The object it leaves behind is a three-by-three map of stamps, and how many ways that folds is the oldest open problem in the subject — 1,368 at three, 300,608 at four, and unknown at five.

construction · Exact division 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 of a folded state 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 pile 0 6 1 2 3 4 5 and its turns, which the all-layers machine cannot foldMVMVMMVVMVMMMMVMVMVVVMVMVMMMVMVMVVVMVMVMMM

Fourteen states are one pile

A machine that folds every layer at once reaches every folded state of a strip of six equal stamps and misses fourteen piles at seven. The fourteen are not fourteen things. Taking a pile's bottom stamp and putting it on top maps foldings to foldings, so the 462 piles of seven stamps fall into 33 classes of exactly fourteen, and the missed piles are one whole class: the pile 0 6 1 2 3 4 5 — an accordion of five stamps with the last stamp wrapped round it and slid into the fold that holds the first — seen from each of its seven stamps. At eight stamps the machine misses 64 piles, and they are exactly the piles that leave that one when an end stamp is removed.

complexity · Simple foldability equal stamps to nine: what the all-layers machine misses, and where the misses come frominherited: taking an end stamp off leaves a pile missed one size down; turning moves the bottom stamp to the topstampsfoldingsreachedmissedinheritednewclasses missedturning a pile41616000—keeps the machine's reach55050000—keeps the machine's reach6144144000—keeps the machine's reach7462448140141 whole, 0 in partkeeps the machine's reach813921328646404 whole, 0 in partkeeps the machine's reach94536405248432416024 whole, 8 in part52 reached turn missedto eight stamps every miss is a whole class and every miss past seven is inherited; at nine neither holds

Nine stamps have piles of their own

A machine that folds every layer at once reaches every folding of six equal stamps, misses one class of fourteen piles at seven, and at eight misses exactly the piles that shrink to that class when an end stamp is taken off. The prediction was that nine would do the same. Counted directly, nine equal stamps have 4,536 foldings and the machine reaches 4,052. Of the 484 it misses, 324 are inherited from eight and 160 are new — among them the nine-stamp tucked pile. And the symmetry that made the misses whole classes breaks: at nine stamps, turning a pile's bottom stamp to the top takes 52 piles the machine reaches to piles it cannot.

complexity · Simple foldability the four letterings of a three-by-three map the loop test refusesdash-dot: mountain; dashed: valley; each passes all four vertices and still has no layer orderone in sixty-four of the letterings a three-by-three map allows

A map refuses in small pieces

The one-pass refusal — a circle in the arcs a map's letters force — fires on four of a three-by-three map's 256 letterings and on none below it, and the question was how it grows. It grows by windows. Every lettering it refuses on a four-by-three or five-by-three map contains one of those four refused three-by-three patterns somewhere inside it, so the share refused is almost exactly one minus 63⁄64 to the power of the map's three-by-three windows. Four by four is the first map with a refusal no window explains, 64 of its 2,112. The rise is smooth, not sharp: a quarter at six by six, near half at eight, seven tenths at ten.

complexity · Map folding the circle behind a refusal, on the smallest maps that need each onedash-dot: mountain; dashed: valley; heavy loop: the circle, each step to a panel the letters put above the last3 by 38 creases4 by 412 creases5 by 414 creases5 by 516 creases

The long circles go round the middle

A four-by-four map has 64 letterings the one-pass refusal catches with no three-by-three pinwheel anywhere in them, and they are not larger pinwheels. They are four shapes, sixteen versions of each, none unchanged by any turn or mirror, and every one is a circle of twelve creases running round the middle of the map. Read the same way on larger maps, every refusal is a circle round some rectangle of panels, and it needs the whole of that rectangle: one in 64 three-by-three rectangles closes one, one in 512 four-by-fours, and rectangles three cells across close nothing a pinwheel does not. Two window sizes explain all but 0.07 per cent of a twenty-by-twenty map's letterings.

complexity · Map folding what refuses a lettering of a tube 5 panels longone bar to a circumference; the whole bar is the share refused0%25%50%75%100%2 round49.0%4 round72.9%6 round59.5%8 round52.6%10 round52.7%12 round54.7%a three-by-three windowa four-by-four windowa circle round the tubea longer circle on the sheet1,500 letterings drawn at random for each tube; each is filed under the first test that refuses it

A tube refuses round itself

On a flat map the cheap refusal — a circle in the arcs a lettering forces — is almost entirely local: small windows of the map explain all but a sliver of it. Glue the map's left edge to its right and the windows still refuse at exactly the rate their number predicts, counted across the seam. But a new refusal appears that no window can contain, a circle that goes once round the tube. It refuses half of every lettering of a tube two panels round, over half of one four round, a quarter at six, and it falls by about half with every two panels of circumference while the tube's length hardly matters.

complexity · Map folding the share of a strip's foldings the all-layers machine can makeevery pile counted; a share is the piles the machine finishes over the piles that exist00.2500.5000.75014681012stampsshare of the foldings reachedfoldings: ×3.20 a stamp from nine onreached: ×2.99 a stamp from nine on7 stamps: 448 of 4628 stamps: 1328 of 13929 stamps: 4052 of 453610 stamps: 12040 of 1406011 stamps: 36152 of 4631012 stamps: 106816 of 146376the reach grows by just under three a stamp and the foldings faster; while that holds, the share keeps falling

The machine's misses have no short list

A machine that folds every layer at once misses fourteen piles of seven equal stamps, sixty-four of eight and 484 of nine, and the question left at nine was whether its failures could be described by a short list of forbidden piles. Counted to twelve stamps, and to thirteen by the same method, they cannot. What the machine reaches is closed under taking an end stamp away, for a reason that fits in a sentence, so every miss contains a smallest one, and the smallest ones keep arriving: 14, 0, 160, 12, 1,194, 116 and 7,786 from seven stamps to thirteen, the tucked pile among them at every odd length. Meanwhile the machine's reach grows by just under three a stamp and the foldings by more, so the share it can make falls from all of them at six stamps to under two thirds at thirteen.

complexity · Simple foldability

Named alongside it

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

Stamp foldingEnumerationThe counting problemCombinatorial explosionLayer orderLunnon's countsOpen problemStackingLayer orderingNecessary conditionGluingThe machine model

All concepts