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! *×* 2^{3} = 48 possibilities.

More generally, for *n* simple folds, the upper limit of fold patterns is *n*! *×* 2^{n}. So, for a 5 *×* 5 map, we have *n* = 8 creases and the upper limit is 8! *×* 2^{8} ^{ }= 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 2^{K}. So, for a 2 *×* 2 map, we have K = 4 creaselets and the upper limit is T = 2^{4 }= 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 = 2^{40 }or about 10^{12}. But most of these do not lead to a legitimate fold. The number of folding patterns is less than 2 *×* 10^{9}.

**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

You must be logged in to post a comment.