## Of Paper Folding

The easiest way to refold a road map is differently.

One of the most unusual and frustrating unsolved problems in modern combinatorial theory, proposed many years ago by Stanislaw M. Ulam, is the problem of determining the number of different ways to fold a rectangular "map." The map is pre-creased along vertical and horizontal lines to form a matrix of identical rectangles. The folds are confined to the creases, and the final result must be a packet with any rectangle on top and all the others under it. Since there are various ways to define what is meant by a "different" fold, we make the definition precise by assuming that the cells of the unfolded map are numbered consecutively, left to right and top to bottom. We wish to know how many permutations of these n cells, reading from the top of the packet down, can be achieved by folding. Cells are numbered the same on both sides, so that it does not matter which side of a cell is "up" in the final packet. Either end of the packet can be its "top," and as a result every fold will produce two permutations, one the reverse of the other. The shape of each rectangle is irrelevant because no fold can rotate a cell 90 degrees. We can therefore assume without altering the problem that all the cells are identical squares.

The simplest case is the 1-by-n rectangle, or a single strip of n squares. It is often referred to as the problem of folding a strip of stamps along their perforated edges until all the stamps are under one stamp. Even this special case is still un solved in the sense that no nonrecursive formula has been found for the number of possible permutations of n stamps. Recursive procedures (procedures that allow calculating the number of folds for n stamps provided that the number for n—1 stamps is known) are nonetheless known. The total number of permutations of n objects is n! [that is, factorial n, or n x (n — l)x(n-2) . . . x 1], All n! permutations can be folded with a strip of two or three stamps, but for four stamps only 16 of the 4! = 24 permutations are obtainable [see Figure 27]. For five stamps the number of folds jumps to 50 and for six stamps it is 144. John E. Koehler wrote a computer program, reported in a 1968 paper, with which he went as high as n=16, for which 16,861,984 folds are possible. W. F. Lunnon, in another 1968 paper, carried his results to n = 24, and in a later paper, to n = 28. Koehler showed in his article that the number of possible stamp folds is the same as the number of ways of joining n dots on a circle by chords of two alternating colors in such a way that no chords of the same color intersect.

The simplest rectangle that is not a strip is the trivial 2-by-2 square. It is easy to find that only eight of the 4! = 24 permutations can be folded, half of which (as explained above) are

Figure 27

iHk aR M

1234 2341 3412 4123

1243 2431 3 12 4 4312

1342 2134 3421 4213

1432 2143 3214 4321

The 16 ways to fold a four-stamp strip reversals of the other half. The 2-by-3 rectangle is no longer trivial, because now it becomes possible to tuck one or more cells into open pockets. This greatly confuses matters. As far as I know, nothing has been published on the nonstrip rectangles. I was able to fold 60 of the 6! = 720 permutations (10 folds for each cell on top), but it is possible I missed a few.

An amusing pastime is to find six-letter words that can be put on the 2-by-3 map (lettering from left to right and from the top down) so that the map can be folded into a packet that spells, from the top down, an anagram of the original word. Each cell should be labeled the same on both sides to make it easier to identify in the packet. For example, it is not hard to fold ill-fed to spell filled and squire to spell risque. On the other hand, osberg (an anagram for the last name of the Argentine writer Jorge Luis Borges that appears on page 361 of Vladimir Nabokov's novel Ada) cannot be folded to Borges, nor can Borges be folded to osberg. Can the reader give a simple proof of both impossibilities?

The 2-by-4 rectangle is the basis of two map-fold puzzles by Henry Ernest Dudeney (see page 130 of his 536 Puzzles Curious Problems. Scribner's, 1967). Dudeney asserts there are 40 ways to fold this rectangle into a packet with cell No. 1 on top, and although he speaks tantalizingly of a "little law" he discovered for identifying certain possible folds, he offers no hint as to its nature. I have no notion how many of the 8! =40,320 permutations can be folded.

When one considers the 3-by-3, the smallest nontrivial square, the problem becomes fantastically complex. As far as I know, the number of possible folds (of the 9! = 362,880 permutations) has not been calculated, although many paperfold puzzles have exploited this square. One was an advertising premium, printed in 1942 by a company in Mt. Vernon, N.Y., that is diagrammed in Figure 28. On one side of the paper there are the faces of Mussolini and Hitler. On the back of the remaining cell of the same row is the face of Tojo, the wartime prime minister of Japan. Above this cell is a prison window with open spaces die-cut between two bars; below the Tojo cell a similar window appears on the back of the cell, as indicated by the dotted lines. The problem is to fold the square into a packet so that at each end two of the faces appear behind the bars; that is, so that on each side of the packet the top cell bears a picture of a window and directly under it a face shows through the open slots between the bars. The fold is not difficult, but it does require a final tuck.

 l 1-Ti -H ____J „X _ S. i „ „ - . % Zu j j i i

A map-fold problem from World War II

### A map-fold problem from World War II

A much tougher puzzle using a square of the same size is the creation of Robert Edward Neale, a Protestant minister, professor of psychiatry and religion at the Union Theological Seminary and the author of the influential book In Praise of Play (Harper & Row, 1969). Neale is a man of many avocations. One of them is origami, the Oriental art of paper folding, a field in which he is recognized as one of the country's most creative experts. Magic is another of Neale's side interests; his famous trick of the bunny in the top hat, done with a folded dollar bill, is a favorite among magicians. The hat is held upside down. When its sides are squeezed, a rabbit's head pops up. (The interested reader can obtain Bunny Bill, a manuscript describing the fold, from Magic, Inc., 5082 North Lincoln Avenue, Chicago, 111. 60625. The fold is far from simple, by the way.)

Figure 29 shows Neale's hitherto unpublished Beelzebub puzzle. Start by cutting a square from a sheet of paper or thin cardboard, crease it to make nine cells, then letter the cells (the same letter on opposite sides of each cell) as indicated. First try to fold the square into a packet that spells (from the top down) these eight pseudonyms of the fallen angel who, in Milton's Paradise Lost, is second in rank to Satan himself: Bel Zeebub, Bub Blezee, Ube Blezbe, Bub Zelbee, Bub Beelze, Zee Bubble, Buz Lebeeb, Zel Beebub. If you can master these names, you are ready to tackle the really fiendish one: Beelzebub, the true

 L Z E B B E B U E

Robert Edward Neale's Beelzebub puzzle

Robert Edward Neale's Beelzebub puzzle name of "the prince of the devils" (Matthew 12:24). Its extremely difficult fold will be explained in the Answer Section. No one who succeeds in folding all nine names will wonder why the general map-folding problem is still unsolved.

Neale has invented a variety of remarkable paper-fold puzzles, but there is space for only two more. One is in effect a nonrectangular "map" with a crosscut at the center [see Figure 30]. The numbers may represent six colors: all the 1-cells are one color, the 2-cells a second color and so on. Here opposite sides of each cell are different. After numbering or coloring as shown at the top in the illustration, turn the sheet over (turn it sideways, exchanging left and right sides) and then number or color the back as shown at the bottom. The sheet must now be folded to form a curious species of tetraflexagon. (Tetraflexa-gons were the topic of an earlier column that is reprinted in The 2nd Scientific American Book of Mathematical Puzzles & Diversions.

To fold the tetraflexagon, position the sheet as shown at the top in the illustration. (It helps if you first press the creases so that the solid lines are what origamians call "mountain folds" and the dotted lines are "valley folds.") Reach underneath and seize from below the two free corners of the 1-cells, holding the corner of the upper cell between the tip of your left thumb and index finger and the corner of the lower cell between the tip of your right thumb and finger. A beautiful maneuver can now be executed, one that is easy to do when you get the knack even though it is difficult to describe. Pull the corners simultaneously down and away from each other, turning each 1-cell

 Z 6 3 1J 6 P P 6 I 3 6 Z 4 3 1 2 1 S 9 S 9 [, 1 3 4

Front (top) and back (bottom) of the unfolded tetraflexagon

Front (top) and back (bottom) of the unfolded tetraflexagon over so that it becomes a 5-cell as you look down at the sheet. The remaining cells will come together to form two opentop boxes with a 6-cell at the bottom of each box [see Figure 31].

Shift your grip to the two inside corners of the 5-cells—corners diagonally opposite the corners you were holding. Push down on these corners, at the same time pulling them apart. The boxes will collapse so that the sheet becomes a flat 2-by-2

First step in folding the tetraflexagon

tetraflexagon with four 1-cells on top and four 2-cells on the underside [see Figure 32]. If the collapsing is not properly done, you will find a 4-cell in place of a 1-cell, and/or a 3-cell in place of a 2-cell. In either case simply tuck the wrong square out of sight, replacing it with the correct one.

The tetraflexagon is flexed by folding it in half (the two sides going back), then opening it at the center crease to discover a new "face," all of whose cells have the same number (or color). It is easy to flex and find faces 1, 2, 3 and 4. It is not so easy to find faces 5 and 6.

One of Neale's most elegant puzzles is his "Sheep and Goats," which begins with a strip of four squares and a tab for later gluing [see Figure 33.] Precrease the sheet (folding it both ways) along all dotted lines. Then color half of each square [dark grey in illustration] black—on both sides, as if the ink had soaked right through the paper.

The strip is folded as shown in steps a, b, c and d. The first

Figure 32

Final step in folding the tetraflexagon

Figure 33

0 0