Paper-folding is a recurring theme in mathematics. The art of origami is much-loved by many who also enjoy recreational maths. One particular folding problem is remarkably easy to state, but the solution remains elusive:
Given a map with M × N panels, how many different ways can it be folded?
Each panel is considered to be distinct, so two foldings are equivalent only when they have the same vertical sequence of the L = M × N layers.
Folding Stamps
We have all experienced the frustration of trying to re-fold an open map in a moving car. There are so many possibilities that it can be very difficult to reverse the unfolding process. Let’s start with the simplest non-trivial example: a map with just two panels, separated by a single fold which we take to be vertical. A simple example of this is a greeting card, which can be folded correctly or inside-out.
Suppose the figure here shows the inside of the card. If we fold the card in the normal way, we get a trough: we denote this action as V1T. Alternatively, we may fold it inside-out, forming a ridge, denoted V1R. These are the only ways to fold this simplest of maps.
Now consider a 3 × 1 map: many pamphlets and brochures are of this form, with two vertical creases. There would appear to be eight ways to fold this map:
V1R-V2R V1R-V2T V1T-V2R V1T-V2T
V2R-V1R V2R-V1T V2T-V1R V2T-V1T
However, examining the results we find that V1R-V2T = V2T-V1R and V1T-V2R = V2R-V1T. Thus, there are just six independent way to fold the 3 × 1 map.
One might argue that, with three panels, there are 3 × 2 × 1 = 6 ways to order them, so the answer must be 6. But what if there are 4 panels (three creases)? We would then argue that there should be 4 × 3 × 2 × 1 = 24 folding patterns. But there are only 16. The problem is not quite as innocent as it appears.
Folding maps of dimension N × 1 is often called the stamp-folding problem as it applies to linear strips of postage stamps. 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, …
This is Sequence A000136 in the Online Encyclopedia of Integer Sequences (OEIS). The pattern is far from obvious. While heuristic methods can be used to estimate terms of this sequence, there is no formula known that could extend this sequence to very large values of N.
From Stamps to Maps
Moving up one dimension, we may now have both vertical and horizontal creases. There are eight ways to fold a 2 × 2 map along its creases, counting each different vertical sequence of folded panels as a distinct way of folding the map.
For the L = M × N layers of a folded map there are L! possible orderings. However, many of these are physically impossible, due to the manner in which the panels are attached to each other. So, normally, L! provides only a very crude upper bound. For a 2 × 2 map we have L = 4 and L! = 24 but, as we have seen, there are only 8 foldings.
Simple and Complex Folds
The 3 × 2 case is shown in the figure below. For an M × N map, there are M – 1 vertical creases and N – 1 horizontal creases. If we restrict ourselves to simple folds, where each fold acts along a full crease, the total number of actions to fold the map is n = M + N – 2. For the 3 × 2 map, this means n = 3 folds. Since there are 3! = 6 ways to order the folds and each fold must be a ridge or a trough, we potentially have 3! × 23 = 48 possibilities.
More generally, for n simple folds, the upper limit of fold patterns is n! × 2n. So, for a 5 × 5 map, we have n = 8 creases and the upper limit is 8! × 28 = 10,321,920.
But there are numerous complex folding patterns. We can easily calculate the total number of “creaselets”; these are segments of a crease between two adjacent vertices or between a vertex and the edge of the map. For an M × N map, there are (M – 1) N vertical creaselets and M (N – 1) horizontal creaselets, and the total number is K = 2MN – (M + N). Each creaselet must be a ridge or a trough. Thus, the total number of possibilities is 2K. So, for a 2 × 2 map, we have K = 4 creaselets and the upper limit is T = 24 = 16. In fact, there are 8 patterns. The remaining 8 are ruled out by a theorem:
Every vertex of a folded map must have one ridge and three troughs or else one trough and three ridges.
This result is known as Maekawa’s Theorem. In the more general cases occurring in origami, it means that at every vertex, the numbers of ridges and troughs always differ by plus or minus two.
Maekawa’s Theorem substantially reduces the number of possible solutions. For example, for a 5 × 5 map, we have K = 40 creaselets and the number of creaselet patterns is T = 240 or about 1012. But most of these do not lead to a legitimate fold. The number of folding patterns is less than 2 × 109.
Unsolved Problem
The general problem of counting the number of ways to fold a map remains unsolved. The number of ways of folding an N × N map are known only for N ≤ 5. They are:
1 8 1,368 300,608 186,086,600 …
(see OEIS: https://oeis.org/A001418 ). The Wikipedia page on “Map Folding” states that the number of solutions is unknown for N > 5. However, the OEIS sequence gives seven terms of the sequence, so I am not sure what is the current state of knowledge.
Map folding, which appears at first glance to be a simple problem, turns out be deep, subtle and intricate.
Source
Wikipedia: Folding Maps: https://en.wikipedia.org/wiki/Map_folding
ThatsMaths 