Origami & Folding
what one sheet can do
Concept

Combinatorial explosion — where it appears

The growth of a search space that makes exhaustive methods stop working. It is what limits every enumeration on this site, and it usually arrives at a size small enough to be surprising.

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

degree-4 vertex4 of 1625.0% · 4 creasespreliminary base112 of 25643.8% · 8 creasesmiura 2×28 of 1650.0% · 4 creasesmiura 3×232 of 12825.0% · 7 creasesmiura 3×3256 of 4,0966.3% · 12 creasesevery count enumerated, none estimatedthe share falls as the pattern grows, and the count still rises

How many assignments fold

The local conditions throw away most of the ways a pattern could be creased. They throw away a smaller and smaller fraction as the pattern grows, and what survives grows faster than what is discarded — which is why a strong filter is not a decision procedure.

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 24681012-202halvingsmetres of paper (powers of ten)297 mm — 6 folds, 64 layers1 m — 7 folds, 128 layers10 m — 8 folds, 256 layers100 m — 10 folds, 1024 layers1200 m — 12 folds, 4096 layerspaper 0.1 mm thick · L = (πt/6)(2ⁿ + 4)(2ⁿ − 1)the loss is the paper that goes round the closed end, and it doubles twice per fold

How many times can it be halved

The folklore says seven, and the folklore is a statement about one sheet of paper. What actually binds is arithmetic: every halving doubles the layers and the paper spent at the closed end grows as the square of the layer count, so the length needed for twelve folds is nearly a kilometre.

material · Idealisation 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 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 of the 33 patterns each refusal is the first to catchtwo creases cross5one sweep over pairs of creasesa vertex condition fails0one pass over the verticesthe panels do not place0one walk over the panelsthe letters force a loop0one pass over the crease listno ordering exists6every ordering of the panels22 of the 33 are refused by none of these and are folded, undecided, or waiting on a search too large to run

The order the refusals come in

This collection can say no to a crease pattern in five ways, and they cost wildly different amounts: a sweep over pairs of creases, a pass over the vertices, a walk over the panels, a pass over the crease list, and an enumeration of every ordering of the panels. Run all five over the thirty-three patterns in the four test populations and the cheapest refuses five, the most expensive refuses six, and the three in between refuse nothing at all.

complexity · Hardness of folding the bar is the largest gap between anywhere on the sheet and a referencea third fold specifies more folds than can be listed, so a sample of them is taken insteadnone of them0.089565 references, from two folds50 of them0.0763,498 references · 0.02% of the round100 of them0.0508,056 references · 0.04% of the round200 of them0.04723,480 references · 0.07% of the round400 of them0.02274,694 references · 0.15% of the round800 of them0.014270,882 references · 0.29% of the roundevery row is a lower bound on what the whole round would buy, because leaving folds out can only make the gap larger

The third fold cannot be listed

Two folds from a bare square reach five hundred and sixty-five reference points. The third round specifies three hundred and seventy-eight thousand folds, of which two hundred and seventy-four thousand are distinct — and the crossings of those with each other run to the tens of billions. The closure stops being computable at exactly the depth a folder starts working at, and what can be said instead is a bound rather than a list.

construction · Reference points each cell is one patch, searched to a verdictgreen: a lettering exists · magenta: none exists, by exhaustion0.150.250.350.50.70.91.11.3turn angle, in radianssquare2626262626262626elongated1515323231313232hexagonal1515394545464545triangular1515393939373737the number in a cell is the nodes the search visited; 6 of 32 patches have no lettering at all

The order that proves nothing exists

Twelve crease patterns with no consistent lettering at all. Proving it takes fifteen steps under one rule and half a million under another — and on three of the twelve the two rules swap places, so neither is the good one. The cost of a negative is two to the power of how many free choices sit above the contradiction.

complexity · Search order what each sheet costs, per panel — a square twistcut out ×10.5565 nodes on 9 panels · 12 lettersglued across ×10.6674 nodes on 6 panels · 10 lettersglued along ×10.6674 nodes on 6 panels · 10 lettersglued both ways ×10.7503 nodes on 4 panels · 8 letterscut out ×20.52013 nodes on 25 panels · 40 lettersglued across ×20.55011 nodes on 20 panels · 36 lettersglued along ×20.55011 nodes on 20 panels · 36 lettersglued both ways ×20.5639 nodes on 16 panels · 32 letterscut out ×30.61230 nodes on 49 panels · 84 lettersglued across ×32.02485 nodes on 42 panels · 78 lettersglued along ×30.57124 nodes on 42 panels · 78 lettersglued both ways ×317.361625 nodes on 36 panels · 72 lettersthe letters go down as the rim goes and the cost per panel goes up

Half the slack

Gluing one pair of a cell's edges removes half the free letters and costs almost nothing. Gluing the second pair removes the other half and costs three orders of magnitude. The letters go linearly and the search does not, and the reason is that the last free letter is worth more than all the others.

complexity · Search order

Named alongside it

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

Map foldingEnumerationStamp foldingLayer orderingLunnon's countsOpen problemAssignmentBacktrackingThe counting problemThe decision problemNecessary conditionSearch cost

All concepts