Map folding

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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]


  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[edit]