Map folding

Labeled stamps

In the stamp folding problem, the paper to be folded is a strip of square or rectangular stamps, separated by creases, and the stamps can only be folded along those creases. In one commonly considered version of the problem, each stamp is considered to be distinguishable from each other stamp, so two foldings of a strip of stamps are considered equivalent only when they have the same vertical sequence of stamps. For example, there are six ways to fold a strip of three different stamps:

These include all six permutations of the stamps, but for more than three stamps not all permutations are possible. If, for a permutation p, there are two numbers i and j with the same parity such that the four numbers i, j, i + 1, and j + 1 appear in p in that cyclic order, then p cannot be folded. The parity condition implies that the creases between stamps i and i + 1, and between stamps j and j + 1, appear on the same side of the stack of folded stamps, but the cyclic ordering condition implies that these two creases cross each other, a physical impossibility. For instance, the four-element permutation 1324 cannot be folded, because it has this forbidden pattern with and . All remaining permutations, without this pattern, can be folded. The number of different ways to fold a strip of n stamps is given by the sequence :1, 2, 6, 16, 50, 144, 462, 1392, 4536, 14060, 46310, 146376, 485914, 1557892, 5202690, ... . These numbers are always divisible by n (because a cyclic permutation of a foldable stamp sequence is always itself foldable),{{citation :1, 1, 2, 4, 10, 24, 66, 174, 504, 1406, 4210, 12198, 37378, 111278, 346846, 1053874, ... , the number of topologically distinct ways that a half-infinite curve can make n crossings with a line, called "semimeanders". These are closely related to meanders, ways for a closed curve to make the same number of crossings with a line. Meanders correspond to solutions of the stamp-folding problem in which the first and last stamp can be connected to each other to form a continuous loop of stamps.

In the 1960s, John E. Koehler and W. F. Lunnon implemented algorithms that, at that time, could calculate these numbers for up to 28 stamps.{{citation | doi-access = free Despite additional research, the known methods for calculating these numbers take exponential time as a function of n.{{citation | doi-access = free Thus, there is no formula or efficient algorithm known that could extend this sequence to very large values of n. Nevertheless, heuristic methods from physics can be used to predict the rate of exponential growth of this sequence.{{citation

The stamp folding problem usually considers only the number of possible folded states of the strip of stamps, without considering whether it is possible to physically construct the fold by a sequence of moves starting from an unfolded strip of stamps. However, according to the solution of the carpenter's rule problem, every folded state can be constructed (or equivalently, can be unfolded).{{citation

Unlabeled stamps

In another variation of the stamp folding problem, the strip of stamps is considered to be blank, so that it is not possible to tell one of its ends from the other, and two foldings are considered distinct only when they have different shapes. Turning a folded strip upside-down or back-to-front is not considered to change its shape, so three stamps have only two foldings, an S-curve and a spiral. More generally, the numbers of foldings with this definition are :1, 1, 2, 5, 14, 38, 120, 353, 1148, 3527, 11622, 36627, 121622, 389560, 1301140, 4215748, ...

Maps

Map folding is the question of how many ways there are to fold a rectangular map along its creases, allowing each crease to form either a mountain or a valley fold. It differs from stamp folding in that it includes both vertical and horizontal creases, rather than only creases in a single direction.{{citation

There are eight ways to fold a 2 × 2 map along its creases, counting each different vertical sequence of folded squares as a distinct way of folding the map:{{citation

However, the general problem of counting the number of ways to fold a map remains unsolved. The numbers of ways of folding an n × n map are known only for n ≤ 7. They are: :1, 8, 1368, 300608, 186086600, 123912532224, 129950723279272 .

Complexity

The map folding and stamp folding problems are related to a problem in the mathematics of origami of whether a square with a crease pattern can be folded to a flat figure. If a folding direction (either a mountain fold or a valley fold) is assigned to each crease of a strip of stamps, it is possible to test whether the result can be folded flat in polynomial time.

For the same problem on a map (divided into rectangles by creases with assigned directions) it is unknown whether a polynomial time folding algorithm exists in general, although a polynomial algorithm is known for 2 × n maps. In a restricted case where the map is to be folded by a sequence of "simple" folds, which fold the paper along a single line, the problem is polynomial. Some extensions of the problem, for instance to non-rectangular sheets of paper, are NP-complete.{{citation

Even for a one-dimensional strip of stamps, with its creases already labeled as mountain or valley folds, it is NP-hard to find a way to fold it that minimizes the maximum number of stamps that lie between the two stamps of any crease.{{citation

References

References

1. Morgan, Thomas D.. (May 21, 2012). "Map folding". Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science.