Hyper Folds

The right sequence of origami folds turns a square sheet of paper into the saddlelike form of a hyperbolic paraboloid.  Photo by I. Peterson

Traditional origami allows no cutting or gluing. If the rules are relaxed a little, even more designs and sculptures can emerge from nimble fingers.

In one painstaking effort, Erik D. Demaine, Martin L. Demaine, and Anna Lubiw created polyhedral sculptures based on the hyperbolic paraboloid, an infinite surface discovered in the 17th century. The central portion of a hyperbolic paraboloid resembles a saddle shape.

Demaine and his coworkers started with a traditional method of folding a hyperbolic paraboloid from a square sheet and showed how it is possible to glue these components edge to edge in different ways to form paper sculptures they describe as hyparhedra.

Their algorithm allows you to construct the hyparhedron version of any given polyhedron. It typically takes several hours to complete a model.

Gluing together partial hyperbolic paraboloids, or hypars, along their edges produces a cubic form—one of a number of closed, curved surfaces called hyparhedra that can be constructed from paper hypar units.

"The richness of these forms excites us visually and presents us with interesting mathematical problems," the team reported in their paper "Polyhedral Sculptures with Hyperbolic Paraboloids.".

Euler Bridges

The East Prussian city of Königsberg (now part of Russia and known as Kaliningrad) straddles both banks of the River Pregel and an island, called Kneiphof, located right where the river divides into two branches. In the 18th century, seven bridges spanned various segments of the river, connecting different parts of the city.

These bridges were the subject of a well-known puzzle at the time: Could a person follow a path through the city that crosses each of the bridges only once, then returns to the starting point?

The seven bridges of 18th-century Königsberg.

In 1735, Leonhard Euler (1707–1783), then living in Saint Petersburg, provided the first mathematical proof that such a journey is impossible. He presented it to members of the St. Petersburg Academy on August 26 of that year. His solution was eventually published in 1741 in the academy's proceedings, under the title "Solutio problematis ad geometriam situs pertinentis (The solution of a problem relating to the geometry of position)."

"Backlogs were apparently a problem even in the 18th century, but perhaps they were more of a problem for Euler than most since he was so prolific," commented Gerald K. Alexanderson in the October 2006 Bulletin of the American Mathematical Society. Indeed, within the mathematics section of the 1741 volume, 11 of the 13 articles are by Euler, all written in 1735 or 1736.

Euler's paper arguably marks the beginning of topology and graph theory. Even the paper's title shows that Euler himself was aware that he was dealing with a new type of geometry in which distance and measurement are not relevant. What matters is position and connection.

In his paper, Euler not only explained why it's impossible to make the desired journey across the Königsberg bridges but also established criteria for determining whether such a journey is possible for any network of bridges anywhere.

He proposed the following method for solving a given arrangement of water and bridges.

1. Denote by the letters A, B, C, and so on, the various areas that are separated from one another by water.

2. Take the total number of bridges, add one, and note this sum.

3. Write the letters A, B, C, and so on, in a column, and write next to each the number of bridges leading to it.

4. Indicate with an asterisk those letters that have an even number next to them.

5. Next to each even one, write half the number, and next to each odd one, write half the number increased by one.

6. Add together these last numbers. If this sum is less than, or equal to, the noted sum (the number of bridges plus 1), conclude that the desired journey is possible.

Euler added that, if the sum is one less than the noted number, the journey must begin from one of the areas marked with an asterisk, and it must begin from an unmarked one if the sum is equal.

Euler applied his method to the Königsberg bridges (figure 1, below), then to a second configuration with two islands, six land masses, and 16 bridges (map shown below as Euler's figure 3).

Courtesy of Gerald L. Alexanderson

Here's the table that results:

Euler concluded that the desired journey can be made if it starts from area D or E.

He then went on in his paper to develop simplified rules for determining whether a bridge-crossing problem has a solution.  Janet Heine Barnett has provided a complete, step-by-step account of Euler's arguments.

The Königsberg bridge problem can be simplified by representing each of the four land masses as a point and each bridge as a line (or arc). Anyone standing on any given land mass would have to have a way to get on and off. So, each land mass would require an even number of bridges. However, in Königsberg, each land mass has an odd number of bridges. As a result, all seven bridges can't be crossed without crossing one of them more than once.

Representation (above) of the Königsberg bridge problem as a graph of points and lines (vertices and edges). Solving the problem would require drawing this diagram without retracing any line or picking up your pencil.

The problem can be solved, however, if you add or remove one bridge. Does it matter which bridge you remove or where you add a bridge?

Nowadays, two of the Königsberg bridges no longer exist, and a single bridge has replaced a pair of the bridges that cross from one side of the river to the other via the island. A set of stairs in the middle of this bridge allows you to visit or leave the island  If you start on the island, it's now possible to find a route that covers all the bridges, as desired in the original problem.

Interestingly, as Alexanderson pointed out, Euler was initially skeptical that mathematics was required for solving the original problem.

In an earlier letter to Carl Leonhard Ehler, mayor of Danzig, Euler had complained that the Königsberg problem "bears little relationship to mathematics … for the solution is based on reason alone, and its discovery does not depend on any mathematical principle."

But, further thought led Euler to a mathematical solution and a pioneering paper in topology.

Originally posted September 25, 2006

Palace of Winds

Hawa Mahal, Jaipur, India, 2010.

Photos by I.Peterson

Mathematical Knitting Network

More than 5,000 mathematicians come annually to the Joint Mathematics Meetings (JMM), held in January. In recent years, amidst the usual lectures, poster sessions, job interviews, and much else, these gatherings have also featured an evening event for those particularly interested in mathematical crafting.

Devoted to knitting, crocheting, beading, needlework, paper folding, and more, this informal session is organized by sarah-marie belcastro and Carolyn A. Yackel.

belcastro and Yackel edited and contributed to the book Making Mathematics with Needlework: Ten Papers and Ten Projects (A K Peters, 2007), which contains not only instructions for creating mathematical objects but also insights into the underlying mathematics.

The JMM knitting network event brings together a wide variety of people, both experts and beginners. Participants and projects can vary widely from year to year.

In the realm of counted cross stitch, Mary Day Shepherd creates painstakingly woven symmetry patterns. For the type of cloth and technique that she uses, the fabric is a grid of squares, and one cross stitch covers one square of the fabric. The only possible subdivision of this square is with a stitch that "covers" half a square on the diagonal, Shepherd said.

These features constrain the number of symmetry patterns that you can weave. Of the 17 possible wallpaper patterns, for example, only 12 can be done in counted cross stitch.

The 12 wallpaper patterns that can be done in counted cross stitch needlework. Courtesy of Mary D. Shepherd.

Shepherd has also worked on frieze and rosette symmetry patterns. Rosette patterns, for example, give a nice visualization of the symmetries of a square (technically, the group D₄ and all its subgroups), she says. See Shepherd's chapter "Symmetry Patterns in Cross Stitch" in the book Making Mathematics with Needlework.

Rosette patterns for visualizing the symmetries of a square (the dihedral group of the square). Courtesy of Mary D. Shepherd.

David Jacob "Jake" Wildstrom has a passion for crocheting in relief.

One of the few fractals that's amenable to crochet is the Sierpinski triangle. Wildstrom has turned this remarkable geometric figure into blankets, wispy shawls, and even a hat. His instructions for crocheting such figures can be found in the chapter "The Sierpinski Variations: Self-Similar Crochet" in Making Mathematics with Needlework. More information is available at Wildstrom's "crochetgeek" website.

Jake Wildstrom's relief crocheting has turned a fractal known as the Sierpinksi triangle into a shawl. Photo by I. Peterson

Tom Hull specializes in mathematical origami design.

One of Tom Hull's modular origami creations. Photo by I. Peterson.

Laura M. Shea strings tiny crystal beads to form polyhedra or geometric tilings.

This beadwork bracelet, created by Laura Shea, is based on a triangular tiling. Photo by I. Peterson.

Creating polyhedra with beads is an interesting way to learn the properties of regular and semi-regular solids, Shea says. In a bead polyhedron, each face becomes open space, each edge becomes one bead, and each vertex becomes a thread void. The resulting structure is light and open.

The "Plato Bead," created by Laura Shea, is a dodecahedron. A bead stands in for each of this polyhedron's 30 edges. Each of the 20 vertices becomes a void surrounded by three beads and thread. The 12 faces of the form become open spaces. Courtesy of Laura Shea.

No mathematical crafts session of the knitting network at JMM would be complete without a Möbius strip—that mind-bending, one-sided, one-edged mathematical object.

Josh Holden displays a Möbius band that he crocheted. Photo by I. Peterson.

Carolyn Yackel works on her knitting during a JMM knitting network session. Photo by I. Peterson.

Originally posted Jan. 27, 2007

References:
belcastro, s.-m., and C. Yackel. 2006. About knitting . . . . Math Horizons 14(November):24-27.

Klarreich, E. 2006. Crafty geometry. Science News 170(Dec. 23&30):411-413.

The Complexity of TipOver and Other Puzzles

Imagine a warehouse with several vertical stacks of crates. Standing on top of one of the stacks, James Bond has to reach a particular crate. He can't touch the electrified warehouse floor, so he must topple some of the stacks to reach others to eventually get to the target crate. His problem, then, is to figure out the right stacks to tip over in the right directions in the right order. A stack falls as a unit, crates can tip over only into empty spaces, and Bond can't leap across empty space or move diagonally to reach other crates.

This scenario is the basis for an entertaining and challenging puzzle called TipOver, produced by ThinkFun. In 2006, Games magazine named it "puzzle of the year."

TipOver started out as an online game invented by James W. Stephens of Atlanta. It's featured on his PuzzleBeast website as the "Kung Fu Packing Crate Maze." Puzzle inventor M. Oskar van Deventer created the three-dimensional version sold by ThinkFun.

Robert A. Hearn has had a longstanding interest in the connection between combinatorial games and computation. He has proved a variety of results related to computational complexity for sliding-block puzzles, sliding-coin puzzles, plank puzzles, hinged polygon dissections, Amazons, Konane, and others. He has also strengthened existing results or provided new, simpler proofs of complexity for games and puzzles such as Minesweeper, the Warehouseman's Problem, Sokoban, and Rush Hour.

Many of these results were included in Hearn's 2006 doctoral thesis on "Games, Puzzles, and Computation," which became the basis of a book with the same title (CRC Press, 2009) and coauthor Erik D. Demaine (Hearn's thesis adviser).

In the case of TipOver, Hearn proved that this puzzle belongs to a class of computational problems described as NP-complete. He described those results in the article "TipOver is NP-complete," published in the Mathematical Intelligencer (Vol. 28, No. 3, pp. 10-14).

In its starting configuration, a TipOver puzzle has several vertical crates of various heights (1 x 1 x h) arranged on a square grid. A tipper—representing a person navigating the layout—stands on top of a particular starting crate. There is a special 1 x 1 x 1 red crate—the target—elsewhere on the grid.

The tipper can topple any vertical crate that it is standing on, in any of the four compass directions, provided there's enough space for the crate to fall unobstructed and lie flat. The tipper can walk (or climb) along the tops of any crates that are adjacent, even when they have different heights.

In the sample puzzle and solution shown below, the numbers indicate the vertical height of each untoppled crate. The tipper starts on the purple crate. In the first move (top, second from left), the tipper has moved to one of the green crates (3 units tall) and toppled it southward so that it ends up adjacent to a yellow crate that is 2 units tall.

"Surprisingly, it does not take many crates to make an interesting puzzle," Hearn wrote. "The number of tips required can never be more than the number of crates—once a crate has been tipped over, it stays fallen—yet finding the correct sequence can be quite a challenge."

To prove that TipOver is NP-complete, Hearn showed that TipOver puzzles are related to a well-known problem in computer science called the Boolean formula satisfiability (SAT) problem.

Consider, for example, two variables, x and y, and the logical statement (x OR y) AND ((NOT x) OR (NOT y)). The OR means that the clause (x OR y) is true if either x or y is true, and the AND means that the clause (x AND y) is true only if both x and y are true. Solving the given problem means assigning a value of true or false to each of the two variables so that the entire statement is satisfied. Here, x must be true and y false, or vice versa, for the statement to be true.

"For any given instance of SAT, there is a corresponding TipOver puzzle that can be solved just when the SAT problem can be solved," Hearn said.

SAT is the prototypical NP-complete problem. Roughly speaking, an NP problem is one for which it is relatively easy to check whether a given answer is correct, but may require an impossibly long time to solve by any direct procedure. In general, as the number of elements, n, increases, a computer's solution time grows exponentially in the worst case. In effect, systematically solving such a worst-case problem involving many elements can take an enormous amount of time, even on the fastest available computers.

Hearn's results show that TipOver must be at least as hard as SAT. "It's easy to show that TipOver is also no harder than SAT," Hearn said, "so TipOver must be NP-complete as well."

Interestingly, Minesweeper, Tetris, and n x n sudoku also belong to the NP-complete category.

How hard is TipOver? "Is there, perhaps, a clever algorithm for coming up with a solution to a given puzzle instance?" Hearn asked. Probably not, he ed

Hearn has also applied his analytic techniques to plank puzzles, invented by Andrea Gilbert and available as River Crossing from ThinkFun.

In this case, you have to cross a crocodile-infested swamp using only wooden planks supported by tree stumps. You can pick up planks and put them down between other stumps, as long as the stumps are exactly the right distance apart. You can't let planks cross each other or intervening stumps, and you can carry only one plank at a time.

Here's a sample puzzle.

To solve the puzzle, you start by walking across the first plank (length 1) to get to a stump. You pick the plank up, lay it down to the south, walk across it, pick it up again, lay it down to the east, walk across it again, pick it up again, walk across the length-2 plank, lay the length-1 plank down to the east, and so on.

It turns out that plank puzzles belong to the class of computational problems known as PSPACE-complete. Such problems are thought to be computationally harder than their NP-complete counterparts.

"We should not be surprised that [plank puzzles] can be very challenging," Hearn said. "It can be very difficult to determine whether there is a solution, and there are puzzles that take exponentially many moves to escape."

At the same time, no one has yet proved that there is no efficient algorithm for solving all NP-complete (or PSPACE-complete) problems. Indeed, finding an efficient method to solve TipOver could yield the most important computer science result of all time—an achievement worth a $1 million prize.

Originally posted Feb. 19, 2007

Perforated Hexagons

Agra Fort, Agra, India, 2010.

Photos by I.Peterson

Tricky Crossings

Have you heard the one about an itinerant entertainer traveling with a wolf, a goat, and a basket of cabbages?

The showman comes to a river and finds a small boat that holds only himself and one passenger. For obvious reasons, he can’t leave the wolf alone with the goat, or the goat with the cabbages. How does he get his cargo safely to the other side?

The showman would need seven trips to ferry the cabbages, goat, and wolf across the river. The showman crosses the river with the goat and leaves the goat on the far shore, then returns alone to the near shore. He brings the wolf to the far shore and brings the goat back to the near shore. He then brings the cabbages to the far shore and returns alone to the near shore. Finally, the showman brings the goat to the far shore.

The showman would need seven trips to ferry the cabbages, goat,and wolf across the river. Another solution interchanges the wolf and the cabbages.

Brainteasers that involve ferrying people and their belongings across a river under trying circumstances have been around for centuries. This particular version dates back to the eighth century and the writings of Alcuin of York (735–804), a poet, educator, cleric, and friend of Charlemagne.

Alcuin of York (right). MAA Portrait Gallery

A variant of this puzzle with a different logical structure also features a predator, its prey, and some food. In this case, however, the human can transport two items at one time.

Suppose, for instance, that a herdsman in North Africa must cross a river with a jackal (a predator), a goat (potential prey), and fig leaves (a potential snack for the goat). One solution is to take the jackal and the goat, leave the jackal while returning with the goat, then ferry across the goat and the fig leaves.

An alternative solution would be to carry over the jackal and the fig leaves, then return for the goat. Although it involves the same number of trips, the second solution might be considered more efficient than the first because the herdsman carries the lightest load on each trip.

In the 16th century, a more elaborate edition of the river-crossing problem, proposed by Venetian mathematician Niccolò Fontana Tartaglia (1499–1557), featured three beautiful brides and their young, handsome, and intensely jealous husbands, who come to a river. The small boat that is to take them across holds no more than two people. To avoid any compromising situations, the crossings must be arranged so that no woman is left with a man unless her husband is also present. How many trips does it take to ferry them all across the river—without igniting an angry outburst?

Niccolo Fontana Tartaglia. MAA Portrait Gallery

It turns out that 11 trips are required. Five passages are needed for just two couples. With four or more couples, however, it’s impossible to accomplish the crossings under the required conditions.

A similar problem involves n couples and a boat that can carry n – 1 people. Under these circumstances, the number of passages from one bank to the other is 11 for n = 3 (as above), nine for n = 4, and seven for n > 4.

A 19th-century version has three missionaries and three cannibals together on one side of a river, with a boat that holds only two people. In this case, the cannibals must never be allowed to outnumber missionaries on either bank. It takes nine trips to get everyone across: a missionary and a cannibal cross; the missionary returns; two cannibals cross; one cannibal returns; two missionaries cross; one missionary and one cannibal return; two missionaries cross; one cannibal returns; and the remaining two cannibals cross.

Here’s a variation from a Russian source: Three soldiers have to cross a river without a bridge. Two boys with a boat agree to help the soldiers, but the boat is so small it can support only one soldier or two boys. A soldier and a boy can’t be in the boat at the same time for fear of sinking it. Given that none of the soldiers can swim, it would seem that in these circumstances just one soldier could cross the river. Yet all three soldiers eventually end up on the other bank and return the boat to the boys. How do they do it?

It takes 12 crossings: Both boys go to the opposite bank; one of them brings the boat back to the soldiers; a soldier crosses the river; the boat returns with the other boy; both boys cross the river; one boy returns with the boat; the second soldier crosses the river; the second boy returns with the boat; both boys cross the river; one boy returns with the boat; the third soldier crosses the river; and the second boy returns with the boat. The boys continue on their journey and the three soldiers are on the opposite bank.

Now, what happens if, in each of these problems, there’s an island in the middle of the river, which can be used as a temporary landing place? In some cases, the island affects neither the total number of trips nor the feasibility of a successful transfer. In other cases, it actually reduces the number of crossings that are necessary.

These puzzles and their many variants represent ways of dressing up relatively straightforward mathematical problems. They invite attempts at solution that range from trial and error to extensive mathematical analysis. You can even try to model a given problem with slips of paper that represent passengers and a boat.

"Story puzzles are expressions of their cultures and so variations will be seen in the characters, the settings, and the way in which the logical problem is framed," Marcia Ascher noted in a 1990 article in Mathematics Magazine.

Novel variants of the river-crossing problem continue to surface in a variety of forums. In one recent guise, the puzzles involve crossing a rickety bridge at night within a certain time period with just one lantern to light the way. Such puzzles now even play a role in job interviews at places such as Microsoft.

Mathematician David Singmaster has compiled an extensive bibliography of material devoted to recreational mathematics. “Recreational problems act as historical markers, showing the transmission of mathematics (and culture in general) in time and space,” he noted. “In particular, they illustrate the fact that most of the more algebraic and arithmetic parts of mathematics have their origins in the Orient, beginning with Babylonia and China and being transmitted through India and the Arabs.

“One must be a little careful with some of these problems, as past cultures were often blatantly sexist or racist,” Singmaster warns. “But such problems also show what the culture was like…. The river crossing problem of the jealous husbands is quite sexist and transforms into masters and servants, which is classist, then into missionaries and cannibals, which is racist. With such problems, you can offend everybody!”

From the days of ancient Egypt to modern times, it’s all done for the sake of turning what appear to be routine mathematical exercises in logic into problems that tickle—even challenge—the mind.

Fort Symmetry

Agra Fort, Agra, India, 2010.

Photo by I. Peterson

Puzzling Names in Boxes

Mathematician Peter Winkler collects mathematical puzzles. Every once in a while, he encounters a particularly fiendish puzzle that gets him to scratch his head and wonder whether he heard it correctly. Or the puzzle sounds so trivial that he has to ask himself whether he missed something.

Winkler described the following puzzle, titled "Names in Boxes," in his paper "Seven Puzzles You Think You Must Not Have Heard Correctly."

The names of 100 prisoners are placed in 100 wooden boxes, one name to a box, and the boxes are lined up on a table in a room. One by one, the prisoners are led into the room. They may look into up to 50 of the boxes to try to find their own name, but must leave the room exactly as it was.

The prisoners are permitted no further communication after leaving the room. They do have a chance to plot a strategy in advance. Good thing. Unless they all find their own names, they will all be executed.

If each prisoner examines 50 boxes at random, the probability of the group's survival is a minuscule 1/2¹⁰⁰. Even worse, if they all happen to look into the same 50 boxes, their chances drop to zero.

However, there is a strategy that the prisoners can use to increase the probability of success to more than 30 percent. Incredible but true! The trick is to find this strategy.

This puzzle, in a different form, was originally devised by computer scientist Peter Bro Miltersen. It appeared in a 2003 paper on substring searches presented at a conference on automata, languages, and programming and later published in a journal.

Here's the strategy.

Beforehand, the prisoners randomly assign "ownership" of one box to each prisoner. As a result, each of the 100 boxes now has a "label" on the outside.

Each prisoner goes to the box with his name on it. He finds another prisoner's name in the box. He then looks into the box labeled with that prisoner's name. He continues in this fashion until he finds his own name or ends up looking into 50 boxes.

Why does this procedure greatly increase the prisoners' chances of survival?

The random assignment of a box with a name in it to each prisoner is just a permutation of the 100 names, chosen uniformly at random from the set of all such permutations, Winkler explained.

So, in inspecting boxes, each prisoner follows a cycle of that permutation, beginning with his box. If they don't exceed the 50-box limit, they succeed in finding their own name. If the particular permutation chosen by the prisoners happens to have no cycle of length greater than 50, the process works, every prisoner finds his name, and no one gets executed.

Indeed, the probability that a random permutation of 2n objects has no cycle of length greater than n is at least 1 minus the natural logarithm of 2.

In this case, the probability of the prisoners surviving is a bit larger than 1 – ln 2. It comes to 31.18 percent.

The strategy works because the prisoners, in effect, impose a structure on their search and take advantage of a basic property of random permutations.

Garden Pieces

Gardens, Agra Fort, Agra, India, 2010.

Photos by I. Peterson

Touring the Poles

A classic brainteaser concerns a hunter out to bag a bear. The hunter walks 1 mile south. He then turns left and walks 1 mile east, then turns left again and walks 1 mile north. He ends up back where he started and spots a bear. What color is the bear?

The standard answer is "white." If you're at the North Pole and you go south along any meridian, turn left and go 1 mile east along a circle of latitude, then 1 mile north, you end up where you started. And you're more likely to find a polar bear there than any other kind.

But, if you ignore the requirement of seeing a bear, there are infinitely many possible solutions—if you look for additional starting points near the South Pole. The South Pole itself isn't a solution because the only direction in which you can go to start with is north.

In fact, there is "an infinity of infinitely many solutions," Eli Maor pointed out in the article "A Cantorian Tour Around the South Pole" in the September 2006 issue of Math Horizons. "And this is in addition to the one obvious solution, the North Pole."

Suppose that you draw a circle centered at the South Pole with a circumference (not radius) of 1 mile. Start at any point along this circle and go 1 mile north. You reach a point that satisfies the requirements of the problem. Proceeding south from this point puts you on the circle, turning left and walking 1 mile along the circle takes you all the way around it, so walking 1 mile north then puts you back in the original spot.

There are infinitely many such points, all lying on a circle centered at the South Pole and having a radius of (1 + ½π) miles.

But there are even more solutions. Suppose you draw a circle with a circumference of 0.5 mile. Any point 1 mile north of this circle is also a solution point. This time, you would end up going around the circle twice to end up at your starting point. Again, there are infinitely many solution points.

And you can do this for circles of infinitely many different circumferences.

So, altogether, you have an infinity of infinitely many solutions, plus one. In Georg Cantor's arithmetic of infinity, that's simply uncountably infinite.

Problem at the Art Gallery

The Crystal Art Gallery was being readied for its grand opening, and, in my role as a security consultant, I had to work out how many guards were needed to make sure that every wall of paintings was under scrutiny. I was also required to keep costs as low as possible.

The trouble was that the art gallery had a distinctive shape. Its walls didn't meet at the usual right angles. Instead, its perimeter consisted of 11 walls forming a highly irregular, sharply cornered, deeply indented polygon. It looked stunning, both inside and out. But the geometry also complicated my task of determining the minimum number of guards that I would need to post.

I started by assuming that a guard stationed at a corner would be able to see down the two walls that meet at that corner. Then, as I was idly sketching the gallery's layout on a paper napkin, I noticed that this configuration was really just a graph, which is what mathematicians call a set of points (known as vertices) and a set of lines (known as edges) joining pairs of these points. I realized I could draw the polygonal art gallery as a graph consisting of 11 vertices (for the corners) and 11 edges (for the walls).

Polygonal art gallery represented as a graph with 11 vertices and 11 edges (left), and one possible triangulation of that polygon (right).

Graph theory often involves coloring problems. In effect, you try to color a graph by assigning colors to each vertex so that no two adjacent vertices are the same color.

There's a famous, closely related problem in which you have to decide whether four colors are sufficient to fill in every conceivable map that can be drawn on a flat piece of paper so that no territories sharing a common boundary are the same color. Once the conjecture was proposed, mathematicians took more than 100 years to prove that four colors are always enough.

It seemed to me that one way to find a solution to my art gallery problem was to subdivide the 11-sided polygon into triangles. I had to do it carefully, making sure that none of the lines I added crossed one another or passed outside the polygon's boundary. There are actually lots of different ways to do this, and any one way is as good as another.

I could now apply a theorem stating that the vertices of any triangulated polygon can be three-colored. Using just red, green, and blue, I could color all 11 vertices of my polygon so that no two adjacent vertices are the same color. Thus, each triangle ends up with one corner of each color.

I could then pick one of the colors and put a guard at each corner having that color. For 11 vertices, two colors are used four times and one color is used three times. So I realized that the smallest number of posted guards that I could get away with would be three.

The great thing about math is that you can often figure out a general answer that works for a host of different cases. For an art gallery with n walls and n corners, the answer is n/3 or the next smallest whole number if 3 doesn't divide evenly into n.

So, I'm now all set for another assignment. Maybe I'll get to work on the Taj Mahal Gallery, which is currently being built as a 21-walled enclosure.

But what if the guards were mobile? Is that anything like routing a robot through an obstacle-filled room?

Photos by I. Peterson

Paul Erdos and an Infinity of Problems

Paul Erdős (1913-1996) was arguably the supreme mathematical problem poser and solver of modern times. His interests were mainly in number theory and combinatorics, though they ranged into topology and other areas of mathematics. He was fascinated by relationships among numbers, and numbers served as the raw materials for many of his conjectures, questions, and proofs.

Born in Hungary in 1913, Erdős demonstrated a quick and nimble mind for mathematics at an early age. In a 1979 interview, he recalled: "It was fairly obvious that I could calculate very well when I was four. At that age, I told my mother that if you take away 250 from 100, you have 150 below 0." Entirely on his own, he had discovered negative numbers.

Erdős made his initial mark as a mathematician at the age of 18, when he discovered an elegant proof of the theorem that, for each integer greater than 1, there is always a prime number between it, n, and double the number, 2n. For example, the prime number 3 lies between 2 and 4. The interval between 10 and 2 x 10, or 20, has the prime numbers 13, 17, and 19.

Though Erdős wasn't the first to prove this theorem, his accomplishment was striking because it considerably improved upon a famous result. A little later, he proved his own theorem that there is always a prime of the form 4k + 1 and 4k + 3 between n and 2n. For example, the interval between 100 and 200 contains the prime-number pair 101 and 103 (k = 25).

In 1978, mathematician Ross Honsberger noted: "Paul Erdős has the theory that God has a book containing all the theorems of mathematics with their absolutely most beautiful proofs, and when [Erdős] wants to express particular appreciation of a proof, he exclaims, 'This is one from the book!'"

Erdős loved problems that people could understand without learning a mass of definitions. His hallmark was the deceptively simple, precisely stated problem and the succinct and ingenious argument to settle the issue. Though simply stated, however, his problems were often notoriously difficult to solve.

Here's a sample Erdős problem that concerns sequences of +1's and −1's. Suppose there are equal numbers of +1's and −1's lined up in a row. If there are two +1's and two −1's, for example, a row could consist of +1 +1 −1 −1. Because these terms can be listed in any order, there are in fact six different ways to write such a row.

Of course, the sum of all the numbers in a row is zero. However, it's interesting to look at the partial sums in each row. In the example above, the partial sums are +1 (after one term), +2 (after two terms), +1 (after three terms), and 0 (after four terms). The problem is to determine how many rows out of all the possibilities yield no partial sum that is negative.

Of the six different rows for n = 2, only two escape a negative partial sum. Of the 20 rows for n = 3, just five have exclusively nonnegative partial sums; for n = 4, 14 out of 70 rows have this particular characteristic; and so on. The answer turns out to be a sequence called the Catalan numbers: 1/(n + 1) times the number of different rows for n +1's and n −1's.

One can liken these rows to patrons lined up at a theater box office. The price of admission is 50 cents, and half the people have the exact change while the other half have one-dollar bills.Thus, each person provides one unit of change for the cashier's later use or uses up one unit of change. In how many ways can the patrons be lined up so that a cashier, who begins with no money of her own, is never stuck for change?

Erdős enjoyed offering monetary rewards for solving particular problems, ranging from $10,000 for what he called "a hopeless problem" in number theory to $25 for something that he considered not particularly difficult but still tricky, proposed in the middle of a lecture.

One problem worth a $3,000 reward concerns an infinite sequence of integers, the sum of whose reciprocals diverges. The conjecture is that such a sequence contains arbitrarily long arithmetic progressions.

"This would imply that the primes contain arbitrarily long arithmetic progressions," Erdős remarked. "This would be really nice. And I don't expect to have to pay this money, but I should leave some money for it in case I leave."

He continued parenthetically, "There I mean leave on the trip for which one doesn't need a passport."

Erdős had once remarked that mathematics is eternal because it has an infinity of problems. In the same spirit, his own contributions have enriched mathematics. Erdős problems—solved and unsolved—abound in the mathematical literature, lying in wait to provoke thought and elicit surprise.

Mirror Bounces

In a game of mathematical billiards, one ball moves across the table at a constant speed forever. There's no friction to slow the ball down. It simply travels in a straight line until it hits a cushion and rebounds according to the rule that the angle of reflection equals the angle of incidence.

What makes the game interesting is the table's geometry. Depending on the ball's initial position and direction, its path can vary considerably within the confines of tables having different shapes. For example, on a circular table, a ball can follow paths that never penetrate an inner circular region of a certain diameter in the middle of the table. A stadium-shaped billiard table leads to unpredictable paths reminiscent of chaos (see "Billiards in the Round").

Even billiard motion inside a rectangular table—indeed, any table bounded by straight lines—can exhibit intriguing regularities and apparent irregularities. Suppose, for example, that a rectangular billiard table is m units long and n units wide, and it has pockets at the corners, labeled A, B, C, and D. It turns out that a ball struck at 45 degrees to the table's sides from a position at A will eventually arrive in either pocket B, C, or D, depending on whether the ratio of m and n to the highest common factor, d, of m and n is even or odd.

Rectangular billiard table of dimensions m x n, with corner pockets at A, B, C. and D.

Consider a table 2 units long and 1 unit wide. In this case, the ball will bounce once—right into pocket B. Here, m = 2, n = 1, and d = 1. So, m/d = 2/1 = 2 (even) and n/d = 1/1 = 1 (odd). Indeed, you can use such a billiard shot to prove that the square root of 2 is an irrational number!

In general, a ball will eventually drop into pocket B if m/d is even and n/d is odd, pocket C if m/d is odd and n/d is odd, and pocket D if m/d is odd and n/d is even. The number of bounces is given by the value of the expression [(m + n) divided by the highest common factor of m and n] − 2. Thus, for a table 5 units long and 3 units wide, the ball bounces six times before it lands in pocket C.

The trick to solving such puzzles is to use the technique of mirror reflection. Every time the ball hits a side, it continues in its original direction across a virtual table created by reflecting the rectangle along that side. In effect, the broken course of the billiard ball is replaced by a straight line.

Example of mirror reflection applied to a rectangular table 5 units long and 3 units wide. The ball ends up in pocket C and takes 6 bounces to get there.

The same technique can be applied to solving a wide variety of ball-bouncing problems, including finding paths in which a ball hits each side just once as it cycles forever inside a polygon or even inside a polyhedron.

Billiards in the Round

Cones of smoky light soak into the green baize of a billiard table. The player squints at the gleaming balls scattered across the surface, adjusts his stance, and lowers his billiard cue, aiming the tip directly at one ball. A smooth stroke ending in a sharp tap shoots the ball across the surface. The ball bounces off one cushion, then another before smacking squarely into a second ball.

On a level, rectangular billiard table, a skillful player can return the balls to their original positions, repeat the shot, and obtain the identical result. The geometry of the table, however, can greatly influence the types of motion possible in a game. Going from a rectangle to a circle or an ellipse or to some sort of oval or polygon introduces new elements into the game—even chaos and unpredictability—and offers a variety of intriguing mathematical puzzles.

One mathematician who thought of playing billiards on a circular table was Charles L. Dodgson, better known as Lewis Carroll. In 1890, he published a set of rules for a two-player game of circular billiards, and he apparently had a suitable table built for the game.

Charles Dodgson (left) and his circular billiard table.

Dodgson's rules specified that a circular table must have a cushion all around, no pockets, and a surface marked with three spots arranged in an equilateral triangle, where three differently colored balls are initially placed.

Hitting a cushion and then a ball scored one point for the player; hitting two balls scored two points; a ball, cushion, then ball, three points; cushion, ball, ball, four points; and cushion, ball, cushion, ball, five points. A player scoring more than one point would get another shot right away.

Dodgson noted, "The circular table will be found to yield an interesting variety of Billiard-playing, as the rebounds from the cushion are totally different from those of the ordinary game."

In mathematical billiards, such motions are idealized to make it easier to look for and detect patterns. There's only one ball, which travels at a constant speed forever. The ball moves in a straight line until it hits the cushion, then bounces back, obeying the rule that the angle of reflection equals the angle of incidence. There are no pockets for the ball to roll into.

Here are examples of what a multiple-bounce trajectory looks like on a circular table. Depending on the ball's starting position and initial direction, it can follow paths that never penetrate an inner circular region of a certain diameter in the middle of the table.

Trajectory after five bounces on a circular table.

Trajectory after 100 bounces on a circular table.

On an elliptical table, billiard-ball trajectories show additional, surprising features. Placed at one focus and shot in any direction, the ball hits the cushion, bounces, and passes over the other focus. If there is no friction to slow the ball down, it continues to pass over a focus with each subsequent bounce. After a few bounces, its course ends up closely following the major axis of the ellipse.

Path of a ball that started at one focus of an ellipse (100 rebounds).

Two different possibilities occur when the ball starts at a position away from either focus. If it is driven so that it doesn't pass between the two foci, it continues along a path that outlines a smaller ellipse—an excluded region—with the same foci as the ellipse of the table.

Trajectory of a ball driven so it doesn't pass between the two foci of an ellipse (100 bounces).

A ball driven between the two foci of an ellipse travels along a path that passes again between them after rebounding from the cushion. The motion repeats endlessly, and the trajectory never gets closer to either focus than a hyperbola with the same focus as the elliptical table.

Path of a ball that passes between the two foci of an ellipse (100 bounces).

Setting up a computer simulation of idealized billiard-ball trajectories on circular and elliptical tables allows you to explore the effects of changing the starting conditions. In one little exercise, I varied the ball position step by tiny step as a way of locating a focus, just by observing from the resulting trajectories on which side of the focus I happened to start. Fascinating patterns emerged in that experiment and in some of my other efforts.

A stadium-shaped billiard table—one in which a rectangle's two flat ends are replaced by half circles—presents its own surprises. In stadium billiards, a slight difference in starting point can radically alter a ball's trajectory. The more often the ball rebounds from the curved walls, the less predictable its path becomes.

On a stadium-shaped billiard table, balls that start off in slightly different directions follow paths that diverge rapidly with each bounce.

If there were no friction at all, the ball's continuing motion as it rattled around the table would appear quite random.

While billiard trajectories on a circular table appear quite regular (left), those on a stadium-shaped table look random after successive bounces (left).

Researchers have also explored idealized billiard trajectories on a family of tables with shapes reminiscent of not only ovals but also peanuts, violins, moons, flippers, and droplets. The sensitive dependence on initial conditions characteristic of chaos lurks in a significant proportion of these geometries.

Unlike rolling dice or tossing coins, billiards is generally considered a game of skill rather than a game of chance. Yet under certain conditions, the game can appear extremely chancy. Depending on the billiard table's configuration, a ball's motion can be either predictable or chaotic.

The same physical laws determine the outcome in either case, but in the chaotic situation the result is so sensitively dependent on initial conditions that the ball's path quickly becomes unpredictable. There are times when billiards can be much more of a game of chance than skill, no matter how expert the player! 

Originally posted March 3,1997

Numbers on the Dartboard

You may have noticed that the numbers on a standard board for the game of darts have the following order, going clockwise starting at the top: 20, 1, 18, 4, 13, 6, 10, 15, 2, 17, 3, 19, 7, 16, 8, 11, 14, 9, 12, and 5.

Why this particular order?

A possible criterion for designing a dartboard is to penalize poor shots as much as possible. That can be done, for example, by maximizing the sum of the absolute value of the difference between adjacent numbers. The larger this sum, the more a poor shot is penalized.

To achieve this maximum, the numbers 11 to 20 should interlace 1 to 10. In this case, the differences between adjacent numbers total 200.

A standard board with 20 sectors has a total of 19! (or 19 ✕ 18 ✕ 17 … ✕ 1 = 121,645,100,408,832,000) possible arrangements. Of those, 10! ✕ 9! (or 1,316,818,944,000) give the maximum possible penalty sum of 200.

Surprisingly, even though there are so many possible arrangements that give the maximum penalty score of 200, the standard dartboard in everyday use has a difficulty of only 198. The "flaw" lies in the placement of 11 next to 14 and 6 next to 10. You could correct this imperfection simply by inserting 14 between 6 and 10 to achieve the maximum difficulty.

Of course, the sum of the differences between adjacent numbers represents just one possible way of defining the difficulty of a dartboard. You might consider, for example, the squares of the differences of adjacent sectors or not only immediate neighbors but also near neighbors.

Moreover, the dartboard also includes areas representing doubles, trebles, and the inner and outer bull. These features, which play an important role in many games, considerably complicate any analysis of the board.

Expert players often concentrate on the treble 20 when aiming for a high score. Players who throw with a much lower accuracy may be wise to aim at sector 14, which has 9 and 11 as adjacent sections. That's the area of the standard dartboard that happens to deviate from the requirements for maximum difficulty, at least according to one criterion.

It would be interesting to delve into the history of dartboards to see how the standard numbering scheme came about.

Originally posted May 19,1997

References:

Cohen,G.L., and E. Tonkes. 2001. Dartboard arrangements. Electronic Journal of Combinatorics.

Everson, P.J., and A.P. Bassom. 1994/5. Optimal arrangements for a dartboard. Mathematical Spectrum 27(No. 2):32-34.

Selkirk, K. 1976. Redesigning the dartboard. Mathematical Gazette 60:171-178.

Old and New Arithmetic

"Three merchants have invested their money in a partnership, whom to make the problem clearer I will mention by name. The first was called Piero, the second Polo, and the third Zuanne. Piero put in 112 ducats, Polo 200 ducats, and Zuanne 142 ducats. At the end of a certain period they found that they had gained 563 ducats. Required is to know how much falls to each man so that no one shall be cheated."

This problem appears in a mathematics text known as the Treviso Arithmetic. The original book, written in a Venetian dialect, had no formal title, and its author is unknown. Treviso is the northern Italian town where the book originated in 1478.

Intended for self study and aimed at a broad audience not necessarily versed in Latin, this volume had a very practical bent. Venice, along with its country outpost Treviso, was a major trade center during the 15th century, and the book's language, examples, and problems reflected a wide range of commercial concerns.

The book also introduced a "new math," promoting the use of the Hindu-Arabic numeral system and the pen-and-ink computational algorithms that accompany it. Together, they were well-suited to the bookkeeping essential for burgeoning worldwide enterprises and clearly superior to Roman numerals and the abacus for handling daily business dealings.

"As the activities of the merchant profession moved from the limited scope of the itinerant peddler to the entrepreneurship of the international commercial house, preparation for entry into the business world became more prolonged and rigorous," mathematics historian Frank J. Swetz wrote in Capitalism and Arithmetic: The New Math of the 15th Century (Open Court, 1987), which includes an English translation of the Treviso Arithmetic.

"A merchant had to be literate, if not in several languages, at least in his own; therefore, boys aspiring to the merchant profession attended the basic grammar schools," Swetz continued. "Then, upon securing a fundamental literacy and numeracy they advanced onward at ages 11 to 12 to a special secondary school to study commercial arithmetic."

The Treviso is the earliest known printed mathematics book in Europe, appearing even before an edition of Euclid's Elements. The fact that a book devoted to commercial arithmetic was printed before Euclid "tells much about the real mathematics climate of this time," Swetz commented.

The Treviso Arithmetic begins on a personal, modest note. "I have often been asked by certain youths in whom I have much interest, and who look forward to mercantile pursuits, to put into writing the fundamental principles of arithmetic," the anonymous author noted. "Therefore, being impelled by my affection for them, and by the value of the subject, I have to the best of my small ability undertaken to satisfy them in some slight degree."

Presumably a teacher, the author then set the stage by echoing words that go back to Aristotle. "All things which have existed since the beginning of time have owed their origin to number." He went on to discuss the five fundamental operations: numeration, addition, subtraction, multiplication, and division.

The rest of the book goes from algorithm to worked example to word problem and solution, step by step cycling to increasingly difficult tasks and combinations of operations.

Pages from the Treviso Arithmetic (1478), the earliest known example of a printed book on arithmetic.

Problems involving currency, for example, could get quite complicated. Merely to subtract the sum of 2820 lire, 4 soldi, 3 grossi, and 27 pizoli from the sum of 8433 lire, 4 soldi, 3 grossi, 27 pizoli, you would need to know that 20 soldi = 1 lira, 12 grossi = 1 soldo, and 32 pizoli = 1 grosso and proceed accordingly. For many other problems, it's useful to know that 24 grossi = 1 ducat.

Investment problems sometimes involved calendar calculations, another type of reckoning replete with quirks. And here's a type of problem that ought to sound familiar: "If 17 men build 2 houses in 9 days, how many days will it take 20 men to build 5 houses?" Some things never seem to change!

The book concludes with a point-by-point summary of the key facts and formulas that a diligent student ought to remember and use.

What about Piero, Polo, and Zuanne? The author provides a model solution to the problem of dividing their profits: "In this and all problems of partnership, you set down all of the shares one after the after and find their sum, which becomes your divisor."

Piero put in 112 ducats

Polo put in 200 ducats

Zuanne put in 142 ducats

The sum 454 (Divisor)

You then apply the relevant algorithm to compute that Piero's share comes to 138 ducats. 21 grossi, 11 pizoli and 190/454; Polo's share to 248 ducats, 0 grossi, 13 pizoli and 242/454; and Zuanne's share to 176 ducats, 2 grossi, 2 pizoli and 22/454. Of course, you then check your answer.

"To prove the case for all three, that no one has been cheated, take the sum of the profits of all three," the author instructs. Since these amount to exactly 563 ducats, which is the total given, no one has been cheated."

Despite the author's best intentions, his textbook apparently was not a popular success. Only one edition was ever published. Perhaps it wasn't commercial enough. Perhaps it failed to do justice to the true complexity of the financial transactions, accounting practices, and mercantile activities typical of that period.

Nonetheless, exploring the byways of practical mathematics through the pages of the Treviso Arithmetic is both illuminating and great fun. It provides a fascinating glimpse of arithmetic as it was taught and used centuries ago.

Originally posted August 5, 1996