Old-fashioned navigation aid.
Back in the days before smart phones with GPS functions became ubiquitous, we had maps. They were big, flat paper objects that worked pretty well, except when you were done navigating and needed to fold them back up. It was never obvious how to re-fold them. Even though they came pre-folded and the creases were on a simple grid pattern. To get the map back to a rectangular shape that fit neatly in your pocket, you needed to carefully fold it section by section along straight lines. It seemed so simple an idiot could do it, but invariably you would get some critical fold backwards or forwards when it was supposed to be the opposite and the map would skew and you would curse and try again and again and again until you threw the thing down in disgust and lost it somewhere under one of the car seats.
Mathematicians feel your pain. No one has ever been able to figure out a general formula to calculate how many different ways a grid of arbitrary size can be folded. It's bedeviled researchers for generations. People are still writing papers about it.
But a recent insight by a maths student suggests there might be another way to approach the problem, one that makes an unlikely connection between combinatorics, colouring problems, and origami.
Tom Hull, a mathematician at Western New England University in Springfield, Massachusetts, has been exploring the Miura map fold, which is a variant of the classic map. Instead of a grid of perpendicular folds, the Miura fold is a grid where the lines intersect at 84/96 degree angles. It looks like this:
The Miura fold was invented by Japanese astrophysicist Koryo Miura, who was just as frustrated with the typical map fold as everyone else. In addition to making pocket maps more convenient, the Miura fold allows space satellites to safely stow and unfold their solar panels.
Let me count the ways...
The genius of the Miura map is that it is easy to open and close the same way every time, just by pushing two diagonally opposite corners together or pulling them apart. But that's not the only possible way to fold it — just the easiest. There are many other possibilities. Almost, but not quite, as many as a standard 90 degree angle map fold, which allows the paper to fold in eight different arrangements around each intersection point, or vertex. A Miura map can fold in only six arrangements around a vertex. Hull thought the Miura's more constraining geometry would make calculating all the possible ways to fold it a more tractable problem.
He gave the challenge to an undergraduate student, Jessica Ginepro. Initially Ginepro and Hull hoped to find a generalised formula for a Miura map grid squares across and squares tall. But it quickly became obvious that wasn’t going to happen. The number of ways of folding the map is given by the formula
For the map it is
And for the case the formula spans pages.
"It was nasty. Really, really nasty," Hull says. Ginepro is still working on finding a formula for the grid. But she’s found there might be a different way. Playing around one day, Ginepro began plugging the solutions of the formula into the Online Encyclopedia of Integer Sequences. Much to her surprise, the encyclopedia spat out a match. The numbers were exactly the same as those generated by an apparently unrelated colouring problem.It was wonderfully unexpected. Colouring problems represent constraint satisfaction challenges. A classic example would be colouring countries on a map so that no two countries of the same colour share a border (see here for more on this). Sudoku, in which the value of each box in the puzzle is constrained by the surrounding boxes' values, is another example. Commercial entities such freight shippers and airlines deal with constraint problems all the time, and would like a better way to frame and solve them. But no one had ever thought colouring problems could have a connection with folding.
Hull and Ginepro have not yet found a simple way to convert the Miura map folding problem to a colouring problem, much less a method to generalise it for any fold. But to get a concrete idea of how colouring and folding are related, consider an origami figure that can fold flat in a plane, like this crane:
If you wanted to colour every region on the crane such that no two regions that share a crease are the same colour, you would only need two colours to do it. And when you fold the crane back up, all the regions of one colour will face one direction, and the regions of the other color will face the other direction.
Most colouring problems are more abstract, but the colouring connection provides a promising approach.
And that is not all. Folding problems can also be related to statistical mechanics, a branch of physics that deals with the behaviour of various materials from a probabilistic point of view. There are physicists collaborating with Hull and Ginepro on the statistical mechanics of folding. They don't care so much about finding every single possible way a map or collapsed cone or other origami object might fold itself into existence; they want to know how to make it fold the one, right way. Or rather, make the right fold the most probable fold. "The math doesn't care. But the physicists do," says Hull.
If the mountains and valleys don't fold properly, this collapsed cone is nothing but crumpled paper.
The physicists care because they are trying to create self-assembling objects from sheets of polymer. When the polymers swell — from getting wet, or changing pH — they buckle and fold. The researchers can control the outline of the buckles and folds, but not whether they fold into mountains or valleys. That's the key. Whether the fold becomes a mountain or a valley depends on the stresses within the material as it is forming. Those stresses can be described by statistical mechanics, but it's a nonlinear problem. In the twentieth century when nonlinear problems were unpopular, most researchers dismissed folding and buckling as junk. But more recent work has shown that our intestines, brains and other tissues self-assemble into predictable folded shapes that are controlled by the material properties of the tissue. The leaves of plants and torn plastic bags seem to follow similar rules. Evolution has managed to master origami engineering, so why shouldn't we?
It's hard folding a map.
There are three ways in which formalising the mathematical connection between colouring, folding, and statistical mechanics problems might be useful. One, it might allow us to understand why structures get stuck in undesirable shapes. Two, it might allow us to identify the important folds. Perhaps there are a subset of folds in a figure that, if folded the right way, force the whole object to self-assemble properly. And third, knowing that might allow us to engineer origami shapes that have two forms and can switch back and forth, depending on whether certain folds become mountains or valleys, says Christian Santangelo, a physicist at University of Massachusetts at Amherst who is collaborating on the project.
It's an unwieldy leap from folding maps, to colouring problems, to a statistical mechanics tour-de-force of soft-materials engineering. But the greatest research breakthroughs are often found in the most unlikely of places. "The real hope is that if map coloring turns out to be related to origami, Tom [Hull] can use that to say something truly cool about origami," Santangelo says.
About the author
Kim Krieger is a freelance writer based in Norwalk, Connecticut. She has covered science policy in Washington, D.C., commodities prices from the floor of the New York Mercantile Exchange, and maths innovation everywhere.