COMPUTING SCIENCE

# Recreational Computing

Puzzles and tricks from Martin Gardner inspire math and science

# One-Cut Magic

Our first example of recreational computer science is inspired by a magic trick performed by Harry Houdini before he was an escape artist. In his 1922 book *Paper Magic*, he describes how to take a standard sheet of paper, make a sequence of folds, cut along a straight line, unfold, and obtain a perfect five-pointed star *(see the top of the first figure, at right).* In 1960, Gardner wrote a *Scientific American* column that described a few such magic tricks, producing “simple geometrical figures” by a sequence of folds and one complete straight cut.

Gardner included the tantalizing statement: “More complicated designs … present formidable problems.” To a theoretical computer scientist such as myself, this screams “Unsolved problem!” Whenever we have several examples of a particular style of magic trick, it is natural to wonder whether it represents a general principle. In this case, we know how to make several simple figures by folding and making one complete straight cut. But what is the complete range of figures that are possible to make in this way, and what sequence of folds will make them? To put it more computationally, can a computer algorithm tell us whether a particular shape can be made, and if so, tell us where to fold and cut to make it?

I started thinking about this problem in 1996 when I was a starting Ph.D. student at the University of Waterloo in Canada. My father, Martin Demaine, then an artist and an avid puzzler and now also a mathematician, had read Martin Gardner’s article back in 1960, remembered the problem and suggested we work on it. So we tackled it, together with my Ph.D. advisor Anna Lubiw, and essentially solved it two years later.

Initially we experimented, folding and cutting lots of pieces of paper. One of our first recognizable creations was a heart shape *(see the bottom of the first figure, above).* This shape, like the five-pointed star, has a line of reflectional symmetry—the center line along which the pieces on either side are mirror images of each other—which is the first fold to make. Why should we fold along symmetry lines? Our effective goal is to fold the paper to *align* the sides of the shape we want to cut out; once the sides lie along a common line, we simply cut along that line. So if the shape has a line of symmetry, we should fold along it, aligning the two halves of the shape, leaving just one half to align.

What if the shape we want doesn’t have a line of symmetry? This is where the problem gets really interesting. Initially we thought that such shapes were impossible: What else could the first fold be? But as we learned more about origami mathematics, which at the time was just making its debut in the scientific literature, we realized that there were many more types of folds than just “fold along a line.” Armed with the idea of such complex flat folds, we quickly made progress on solving the problem, building general techniques for producing more and more shapes.

One early step in this progression was making any triangle *(see the second figure, at right).* To try this out, draw the three sides of a triangle on a piece of paper. Now find the lines that bisect each of the angles of the triangle by starting at one of its corners, folding one edge on top of another, unfolding, and repeating for the two other corners. A classic theorem from high-school geometry is that the three angular bisectors meet at a common point. Now fold along a line through this point so as to bring one of the three triangle sides onto itself, and unfold. The fold will be perpendicular to the triangle side. If you like, you can repeat with the two other sides, though only one perpendicular fold is necessary. The final step, which is the hardest if you’ve never made a “rabbit ear” in origami, is to fold along all the creases at once, with the angular bisectors folding one way (called “mountain” folds) and the perpendicular ones folding the other way (called “valley” folds). Once you do this, all three triangle sides lie along a line, with the inside and outside of the triangle lying on opposite sides of that line. What’s cool is that this works for any triangle—no line of symmetry required.

To our surprise, we also found a way to make any polygon with any number of sides, not just triangles. So you can make the silhouette of your favorite shape, such as the swan in the third figure *(at left),* by folding and then making one complete straight cut. The fold is substantially more complicated, but not too hard with practice. I recommend precreasing—folding and unfolding each crease line—before attempting to fold all the creases simultaneously and collapse the swan down to a line.

And there’s more: You can make several polygons at once with a single cut. This result is especially useful for spelling initials, such as the ones that I prepared for my first Gathering for Gardner (the fifth one, abbreviated G4G5) in 2002. It’s rather difficult to fold anything beyond a few letters, but in principle you could fold a piece of paper, make one complete straight cut, and produce the entire Gettysburg Address.

Although this research was motivated by magic tricks, the theoretical computer science that resulted turns out to have more serious applications as well. A closely related problem is that of compactly folding an airbag flat so that it fits into a small compartment such as your steering wheel. The solution to the fold-and-cut problem leads to a natural way to collapse three-dimensional surfaces such as airbags, and this approach has been applied in some simulations of airbag deployment. So recreational computer science may even save lives.

EMAIL TO A FRIEND :

**Of Possible Interest**

**Feature Article**: Restoring Depth to Leonardo’s Mona Lisa

**Perspective**: Taking the Long View on Sexism in Science

**Computing Science**: Computer Vision and Computer Hallucinations