Origami & Folding
what one sheet can do
Concept

The counting problem — where it appears

The question of how many objects satisfy a condition, rather than whether any does. Counting flat foldings is harder than deciding flat-foldability, and the gap between the two is a real one rather than an artefact.

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

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 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 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 how much choice there is in the cuttingevery subset of the joins, tested for connectivitygridcranesjoin pointssubsetsconnectedfewest joins2 × 250% of them work41211 of 1one way only3 × 36.3% of them work941614 of 4one way only4 × 44.1% of them work169512215 of 9one way only5 × 51.2% of them work251665,53678510 of 1650 wayseach interior lattice point holds four cranes at once · every subset of them tried, and the piece has to come out in one piece

Which cranes can stay joined

The 1797 book slits a square into a grid and leaves the cranes attached at the interior lattice points, each of which holds four of them at once. Of the sixteen ways to choose which of a three-by-three's four points to leave joined, exactly one leaves the piece in a single object — and it is the one that uses all four. The cutting is very nearly forced rather than chosen.

history · Folklore of folding two ways to come aparta crane left hanging, or every crane held and the piece still in islandsgridsubsetsnothing hangingholds togetherfailures localheld, of those passing3 × 34 joins1611100.0%100.0%4 × 49 joins512322197.8%65.6%5 × 516 joins65,5361,21578599.3%64.6%6 × 625 joins33,554,432260,625141,62199.6%54.3%a crane hangs from nothing when none of the joins at its four corners is kept — one crane, four points, no search

Nearly every cutting fails at one crane

Six by six connected cranes have twenty-five joins and thirty-three million ways to keep some of them, and an exhaustion over all of them takes a fifth of a second. Of the 33,412,811 that fail, 99.64 per cent fail at a single crane — one left holding none of the joins at its corners — which a maker can check by looking at each crane in turn. The arrangements that pass that check hold together less often as the grid grows: all of them at three by three, 54 per cent at six by six.

history · Folklore of folding the bar is the share of sound cuttings that hold the cranes in one piecesound means every crane keeps at least one join at its corners3 × 3100.0%2⁴ subsets of 4 joins · 1 states carried4 × 465.6%2⁹ subsets of 9 joins · 7 states carried5 × 564.6%2¹⁶ subsets of 16 joins · 23 states carried6 × 654.3%2²⁵ subsets of 25 joins · 52 states carried7 × 751.1%2³⁶ subsets of 36 joins · 123 states carried8 × 846.7%2⁴⁹ subsets of 49 joins · 294 states carried9 × 943.6%2⁶⁴ subsets of 64 joins · 714 states carried10 × 1040.5%2⁸¹ subsets of 81 joins · 1,758 states carried11 × 1137.7%2¹⁰⁰ subsets of 100 joins · 4,380 states carried12 × 1235.1%2¹²¹ subsets of 121 joins · 11,024 states carriedcounted one join at a time, carrying only which cranes on the frontier are already joined

The border is where the cranes come apart

Counted one join at a time rather than one subset at a time, the slit grid of connected cranes runs to twelve by twelve, where there are 2¹²¹ ways to keep some of the joins. Among the cuttings that hold every crane by something, the share that also hold together keeps falling — 54.3 per cent at six by six, 35.1 at twelve — and from eight by eight on it falls by the same factor at every size. A constant factor is the signature of the border: at six by six, 99.5 per cent of the sound cuttings that come apart do so through a stray piece touching the outermost ring of joins.

history · Folklore of folding the bar is the fewest joins that hold every crane in one pieceslack is how many merges those joins could make and do not: three a join, against n² − 13 × 34 joinsfloor 3 · 1 above · slack 4 · 1 way4 × 45 joinsfloor 5 · at the floor · slack 0 · 1 way5 × 510 joinsfloor 8 · 2 above · slack 6 · 50 ways6 × 612 joinsfloor 12 · at the floor · slack 1 · 1 way7 × 718 joinsfloor 16 · 2 above · slack 6 · 1,018 ways8 × 821 joinsfloor 21 · at the floor · slack 0 · 1 way9 × 928 joinsfloor 27 · 1 above · slack 4 · 308 ways10 × 1034 joinsfloor 33 · 1 above · slack 3 · 7,076 ways11 × 1142 joinsfloor 40 · 2 above · slack 6 · 2,068,604 ways12 × 1248 joinsfloor 48 · at the floor · slack 1 · 689 waysa slack of nought is a perfect tree of fours, every join merging four pieces that were separate until then

The prediction held at eight and broke at ten

A join in a slit grid of cranes merges at most four pieces, so n² cranes need at least ⌈(n² − 1)⁄3⌉ joins, and exhaustion found four and six by six meeting that floor in exactly one way. The guess was that eight by eight would too, with twenty-one joins. Counted a join at a time, it does — twenty-one, one way. Ten by ten does not: it needs thirty-four against a floor of thirty-three, and has 7,076 ways to spend them. The grids that meet the floor with no merge to spare are four and eight by eight among every size to fourteen, and sixteen by sixteen by construction, because a perfect tree of joins on a grid twice as wide is four perfect trees and one join in the middle. The even grids were never the pattern; the doublings are.

history · Folklore of folding the lattice points of two grids, coloured like a checkerboardringed: the point each corner crane touches, which must be a join5 by 5: 16 lattice pointsthe four ringed points are two coloursso no perfect tree can hold all four4 by 4: 9 lattice pointsthe four ringed points are one colourso a perfect tree may use that colour

No odd grid holds a perfect tree

A perfect tree of joins holds a slit grid of cranes with every join merging four pieces that were separate. Two joins side by side share two cranes and close a loop, so a perfect tree never has two — and so all its joins lie on one colour of the checkerboard the lattice points make. The four corner cranes each touch one lattice point, which must be a join; on a grid with an odd side those four points are two colours. So no odd grid holds a perfect tree, and seventeen by seventeen, the size the count was pointing at, is settled without counting. On one colour the search is small enough to finish: sixteen by sixteen has exactly one perfect tree, the doubled one, and twenty by twenty has none.

history · Folklore of folding the perfect trees on eight, sixteen and thirty-two, drawn by the joins they leave outdots: joins kept; crosses: points of the tree's colour cut, the middle row and column marked in the second colour8 by 8: 4 cuts for 12 loopsfour cuts round the middleevery other join kept16 by 16: 28 cuts for 84 loops12 on the middle row and column16 in the four quarters32 by 32: 140 cuts for 420 loops28 on the middle row and column112 in the four quarters

A perfect tree is the joins it leaves out

On the colour a perfect tree lives on, the lattice points and the cranes they share form a graph full of loops, and a perfect tree is that graph with some points cut out. Euler's count fixes how many: every cut removes three loops' worth, and the loops always number exactly three times the cuts a perfect tree needs — so a set of that many cuts, no two sharing a crane, leaves a perfect tree exactly when what remains is one piece. Searched that way, ten by ten fails in seven cases that fit on one page, fourteen in 761, and sixteen's one tree is four copies of eight's diamond of cuts with a cross of cuts along the middle.

history · Folklore of folding 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

Named alongside it

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

Map foldingEnumerationSenbazuruConnectivityHiden senbazuru orikataStamp foldingLattice identityLayer orderNecessary conditionParityCombinatorial explosionLocality

All concepts