Jump to content

Map folding

Edit links
From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by David Eppstein (talk | contribs) at 18:54, 3 December 2016 (→Maps: how it differs from stamp folding). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

In the mathematics of paper folding, map folding and stamp folding are two problems of counting the number of ways that a piece of paper can be folded. In the stamp folding problem, the paper is a strip of stamps with creases between them, and the folds must lie on the creases. In the map folding problem, the paper is a map, divided by creases into rectangles, and the folds must again lie only along these creases.

Lucas (1891) credits the invention of the stamp folding problem to Émile Lemoine.[1] Touchard (1950) provides several other early references.[2]

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.[3] 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 i = 1 and j = 3. All remaining permutations, without this pattern, can be folded.[3] 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, ... (sequence A000136 in the OEIS).

These numbers are always divisible by n (because a cyclic permutation of a foldable stamp sequence is always itself foldable),[3][4] and the quotients of this division are

1, 1, 2, 4, 10, 24, 66, 174, 504, 1406, 4210, 12198, 37378, 111278, 346846, 1053874, ... (sequence A000682 in the OEIS),

the number of topologically distinct ways that a half-infinite curve can make n crossings with a line, called "semimeanders".

Unsolved problem in mathematics:
Is there a formula or polynomial-time algorithm for counting solutions to the stamp-folding problem?
(more unsolved problems in mathematics)

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.[5][6][7] Despite additional research, the known methods for calculating these numbers take exponential time as a function of n.[8][9] 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.[10]

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).[11]

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.[3] 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, ... (sequence A001011 in the OEIS)

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.[12]

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:[5]

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 ≤ 5. They are:

1, 8, 1368, 300608, 186086600 (sequence A001418 in the OEIS).

Complexity

Unsolved problem in mathematics:
Given a mountain-valley assignment for the creases of a map, is it possible to test efficiently whether it can be folded flat?
(more unsolved problems in mathematics)

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.[13]

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.[14] 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.[13]

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.[15]

See also

References

  1. ^ Lucas, Édouard (1891), Théorie des nombres (in French), vol. I, Paris: Gauthier-Villars, p. 120.
  2. ^ Touchard, Jacques (1950), "Contribution à l'étude du problème des timbres poste", Canadian Journal of Mathematics (in French), 2: 385–398, doi:10.4153/CJM-1950-035-6, MR 0037815.
  3. ^ a b c d Legendre, Stéphane (2014), "Foldings and meanders", The Australasian Journal of Combinatorics, 58: 275–291, arXiv:1302.2025, MR 3211783
  4. ^ Sainte-Laguë, André (1937), Avec des nombres et des lignes (in French), Paris: Vuibert, pp. 147–162. As cited by Legendre (2014)
  5. ^ a b Gardner, Martin (1983), "The combinatorics of paper folding", Wheels, Life and Other Mathematical Amusements, New York: W. H. Freeman, pp. 60–73. See in particular pp. 60–62.
  6. ^ Koehler, John E. (1968), "Folding a strip of stamps", Journal of Combinatorial Theory, 5: 135–152, doi:10.1016/S0021-9800(68)80048-1, MR 0228364
  7. ^ Lunnon, W. F. (1968), "A map-folding problem", Mathematics of Computation, 22: 193–199, doi:10.2307/2004779, MR 0221957
  8. ^ Jensen, Iwan (2000), "A transfer matrix approach to the enumeration of plane meanders", Journal of Physics A: Mathematical and General, 33 (34): 5953
  9. ^ Sawada, Joe; Li, Roy (2012), "Stamp foldings, semi-meanders, and open meanders: fast generation algorithms", Electronic Journal of Combinatorics, 19 (2): Paper 43, 16pp, MR 2946101
  10. ^ Di Francesco, P. (2000), "Exact asymptotics of meander numbers", Formal power series and algebraic combinatorics (Moscow, 2000), Springer, Berlin, pp. 3–14, doi:10.1007/978-3-662-04166-6_1, MR 1798197
  11. ^ Connelly, Robert; Demaine, Erik D.; Rote, Günter (2003), "Straightening polygonal arcs and convexifying polygonal cycles" (PDF), Discrete and Computational Geometry, 30 (2): 205–239, doi:10.1007/s00454-003-0006-7, MR 1931840
  12. ^ Lunnon, W. F. (1971), "Multi-dimensional map-folding", The Computer Journal, 14: 75–80, doi:10.1093/comjnl/14.1.75, MR 0285409
  13. ^ a b Arkin, Esther M.; Bender, Michael A.; Demaine, Erik D.; Demaine, Martin L.; Mitchell, Joseph S. B.; Sethia, Saurabh; Skiena, Steven S. (September 2004), "When can you fold a map?" (PDF), Computational Geometry: Theory and Applications, 29 (1): 23–46, doi:10.1016/j.comgeo.2004.03.012.
  14. ^ Morgan, Thomas D. (May 21, 2012), Map folding, Master's thesis, Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science
  15. ^ Umesato, Takuya; Saitoh, Toshiki; Uehara, Ryuhei; Ito, Hiro; Okamoto, Yoshio (2013), "The complexity of the stamp folding problem", Theoretical Computer Science, 497: 13–19, doi:10.1016/j.tcs.2012.08.006, MR 3084129
Retrieved from "https://en.wikipedia.org/w/index.php?title=Map_folding&oldid=752849598"