In combinatorial mathematics the map folding problem is the question of how many ways there are to fold a rectangular map along its creases, disregarding any directionality in the creases. A related problem called the stamp folding problem is how many ways there are to fold a strip of stamps.
For example, there are six ways to fold a strip of three different stamps:
And there are eight ways to fold a 2×2 map along its creases:
The problem is related to a problem in the mathematics of origami of whether a square with a crease pattern can be folded to a flat figure. Some simple extensions to the problem of folding a map are NP-complete.
- Gardner, Martin (1983), "The combinatorics of paper folding", Wheels, Life and Other Mathematical Amusements, New York: W. H. Freeman, pp. 61–61
- 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.
- Weisstein, Eric W., "Map Folding", MathWorld.
- "Folding a Strip of Labeled Stamps" from The Wolfram Demonstrations Project: http://demonstrations.wolfram.com/FoldingAStripOfLabeledStamps/
|This combinatorics-related article is a stub. You can help Wikipedia by expanding it.|