Map folding
Encyclopedia
In combinatorial mathematics
the map folding problem is the question of how many ways there are to fold a rectangular map along its 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
.
Combinatorics
Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures. Aspects of combinatorics include counting the structures of a given kind and size , deciding when certain criteria can be met, and constructing and analyzing objects meeting the criteria ,...
the map folding problem is the question of how many ways there are to fold a rectangular map along its 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
NP-complete
In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...
.
See also
- Martin Gardner, "The Combinatorics of Paper Folding," Wheels, Life and Other Mathematical Amusements, New York: W. H. Freeman, 1983 pp. 60–61.
- "Folding a Strip of Labeled Stamps" from The Wolfram Demonstrations Project: http://demonstrations.wolfram.com/FoldingAStripOfLabeledStamps/