Map folding

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

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

References

  1. ↑ Gardner, Martin (1983), "The combinatorics of paper folding", Wheels, Life and Other Mathematical Amusements, New York: W. H. Freeman, pp. 61–61
  2. ↑ 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.

External links


This article is issued from Wikipedia - version of the Friday, January 08, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.