MatheMUSEments

Articles for kids about math in everyday life, written by Ivars Peterson for Muse magazine.

June 30, 2007

Count and Capture

You're probably familiar with board games such as Monopoly, Candy Land, or Clue. These games are old enough that your parents likely enjoyed them when they were young, too. There are other games, which people have enjoyed across generations, that have been around even longer—some for thousands of years. One such game is awari, which originated in Africa. If you haven't tried it, you might be surprised at how tricky and involving this seemingly simple game can be.

Awari is an example of a "count-and-capture" strategy game. It belongs to a family of board games called mancala games. In its traditional form, the awari game "board" consists of two rows of six hollows, with four seeds in each hollow, or cup.

Two players sit across from each other, with six cups belonging to one player and six to the other. Each player aims to capture the most seeds.

On each turn, the first player takes all the seeds from one of the six cups on her side and, moving counterclockwise, adds one seed to each succeeding cup, until all the seeds are used up. The second player then takes the seeds from any one of the six cups on his side and does the same.

On any given turn, when a player drops her last seed in a cup on her opponent's side and that cup contains only one or two seeds (making a total of two or three seeds), she removes all the seeds from this cup, taking them out of the game. She also takes any seeds in cups immediately before the emptied cup if those cups now also total two or three. Players can take seeds only from their opponent's side. The game ends when one player has no seeds left on his side, and so he cannot move any seeds. The winner is the player who has captured the most seeds.

The awari board after player #1 takes her first turn (above).

The awari board after player #2 takes his first turn (above).

But how does this all come about? How do you win such a game?

A few years ago, computer scientists in the Netherlands turned to computers to find the answer. They calculated the best move and eventual outcome for all 889,063,398,406 positions that can possibly occur in the game—from having four seeds in every cup to having all 48 seeds in one cup. They found that, if you play perfectly, the game always ends in a tie.

Now, there's no mystery left. But, the good news is: Unless you're playing against a computer that can store and retrieve every possible move, you can still have a lot of fun playing the game and developing your own strategies for winning.

You can play awari against a computer at awari.cs.vu.nl, a Web site created by the computer scientists who solved the game.

Muse, July/August 2006, p. 28-29.

June 29, 2007

From Counting to Writing?

We learn to count at such an early age that we tend to take the notion of numbers for granted. We know that two can stand for two apples, two oranges, or two argyle socks. But abstract numbers are the product of a long cultural evolution. They may even have played a role in the invention of writing, or so archaeologist Denise Schmandt-Besserat argues.

Schmandt-Besserat has studied mysterious clay objects found in large quantities at sites all over the Middle East, particularly in Mesopotamia. These objects, or tokens, first appeared around 8000 B.C., when people who had been hunters and gatherers began settling in villages and growing grain. Schmandt-Besserat suggests that farmers needed a reliable way to keep track of their goods, especially the amount of grain stored in village silos. They kept a stock of tokens—one token for each item they owned, with different shapes for different types of items. For example, a marble-sized clay ball stood for a bushel of grain, a certain cylinder for an animal, an egg-shaped token for a jar of oil. All in all, it was a kind of data-storage system.

As life grew more complex, the tokens became more elaborate. A cone with markings, for example, represented not an amount of grain but a loaf of bread.

Excavations of temples have revealed that the people of Mesopotamia sometimes kept sets of tokens encased in clay globes. Because the tokens were no longer visible, they marked the globes by pressing the tokens into the soft clay before sealing and baking the globes. From the imprints, you could tell what was inside.

It didn't take long for people to realize that once the clay globes were marked, it wasn't necessary to enclose the tokens. The marks by themselves, impressed on a clay tablet, were enough.

The final step came around 3100 B.C., when someone realized that instead of representing, say, 33 jars of oil by repeating the symbol for one jar 33 times, it would be simpler to precede the symbol for a jar of oil by special signs expressing numbers. And the same signs could be used to represent the same quantity of any item.

This much is certain. But Schmandt-Besserat makes an additional intriguing suggestion: that the token system led to pictographic writing, which in turn developed into the writing system called cuneiform. Other scholars agree that Sumerian tokens were devices for keeping track of goods, but argue that writing developed independently. They say there is little evidence that cuneiform arose directly out of a token-based accounting system.

However this scholarly argument comes out, the clay globes with their strange contents bear silent witness to a world without numbers or an alphabet, a world so remote from our own that it is hard to imagine what it must have been like.

Muse, May/June 2006, p. 40.

June 28, 2007

By the Numb3rs

"We all use math every day." That's a line you might hear in math class or see at a science museum. You don't expect to find a TV crime series that celebrates it. Yet millions of people hear this line every week at the beginning of the popular CBS show Numb3rs, which features a young math professor as a crime fighter.

Charlie Eppes, played by David Krumholtz, uses math to help his older brother, Don, who's an FBI agent, solve crimes. For example, he uses a mathematical equation to identify a killer's location by working backward from the crime scene locations. Or he solves an undecipherable numerical code left at the sites of train wrecks to discover who's causing them.

Math comes up in other ways, too. In one show a man's daughter is kidnapped because he is about to solve Riemann's hypothesis, sometimes called the most difficult unsolved problem in mathematics, thereby winning a \$1 million prize.

For many people, part of the fun of watching the series is to see if they can spot mathematical stuff—games, puzzles, books, calculators, posters—in Charlie's cluttered office. They also listen for references to mathematical concepts and famous mathematicians that often have nothing to do with the plot but still say something about a mathematician's life and interests. The see-through blackboards are pretty cool, too.

The show's producers and writers go to a lot of trouble to find stories that involve math and to check with experts to make sure that they use math correctly. It takes about 2 months to go from an idea to a final script.

Just before episodes are filmed, the actors sometimes get written explanations of the math concepts that will come up—but they don't always read them. Krumholtz used to have a hand double who wrote his equations for him, but more recently the actor has begun to write them for himself.

A team of teachers also gets a preview of each script before it's filmed. Inspired by a program's math content, they prepare classroom activity sheets, which are made available at www.weallusematheveryday.com/tools/waumed/home.htm on the Monday before each new show is broadcast. You can also check out Numb3rs blogs. The math department at Northeastern University in Boston, for example, provides background information on topics the shows touch on, such as digital image processing or blackjack strategies, at www.atsweb.neu.edu/math/cp/blog/.

Of course, no real mathematician could possibly know as much as Charlie does about so many different areas of mathematics. But you expect TV stars to be larger than life—and those CSI guys sure can figure out a lot from one "epithelial"!

Muse, April 2006, p. 43.

June 27, 2007

Problems to Sharpen the Young

One of the oldest collections of mathematical problems we know of is Problems to Sharpen the Young. No one knows who wrote the book, but some scholars say that the author might have been someone named Alcuin, who lived from about 732 to the year 804 (three-digit years!). Alcuin was born near the city of York in England and was a student, then a teacher, and then head of the Cathedral School at York.

Here's a problem from the book you might find interesting:

A staircase has 100 steps. On the first step stands a pigeon; on the second, two pigeons; on the third, three; on the fourth, four; on the fifth, five; and so on, on every step up to the hundredth. How many pigeons are there altogether?

Can you find a quick way to solve the problem that doesn't require you to add all the numbers from 1 to 100? You'll find the answer at the end of this article.

Problem 5 in the collection is one of six variations in the book on what was known as the "hundred fowls" problem, so-called after a 5th-century version that features 100 birds (cocks, hens, and chicks):

A merchant wanted to buy 100 pigs for 100 pence. For a boar, he would pay 10 pence, for a sow, 5 pence; while he would pay 1 penny for a couple of piglets. How many boars, sows, and piglets must there have been for him to have paid exactly 100 pence for 100 animals?

Problem 52 in the collection has survived in various forms to this day:

A certain head of household ordered that 90 modia of grain be taken from one of his houses to another 30 leagues away. Given that this load of grain can be carried by a camel in three trips (not necessarily all the way) and that the camel eats one modium per league but only eats when he is carrying a load, how many modia were left over at the end of the journey?

Forget about the modia. The units are irrelevant. Modern versions are sometimes called jeep problems because they describe a jeep in the desert with n cans of fuel and a distant destination.

Here's a really sneaky one:

A man has 300 pigs and orders that they are to be killed in three days, an odd number each day. What odd number of pigs must be killed each day?

There's no answer. According to the book, this problem was composed to show up smart-alecky or misbehaving schoolchildren. Wonder how long it took students to figure out that this was a trick question and that three odd numbers can never add up to an even number.

It seems that some things about school haven't changed much—even over hundreds of years.

ANSWER: Alcuin's clever solution to the staircase problem is to count the pigeons in pairs, starting with the one on the first step and the 99 on the 99th step. That makes 100. The two on the second step and the 98 on the 98th step also make 100. Remember the 50th step and the 100th step have no pairs. The grand total? 5050 pigeons, which is a lot of feathers.

If you want to try other problems in the collection, go to logica.ugent.be/albrecht/alcuin.pdf.

Muse, March 2006, p. 42.

June 26, 2007

Hard Cash

What could you do for fun with some coins and a sheet of paper? That's all Bob Hearn, a graduate student at the Massachusetts Institute of Technology, needed to invent a new kind of puzzle. Here's an example.

Place four coins on the bottom row of circles (covering G, D, E, and R). This leaves the letters MARTIN exposed. Your challenge is to slide the coins along the paths joining the circles until the four coins cover the top row of circles (M, T, I, and blank), exposing the letters GARDNER. (By the way, Martin Gardner is the name of a famous math writer and puzzle expert.)

Sounds simple? The catch is that the coins can never be directly connected by a path. For example, you can't move the G coin initially because the only allowed move would put it next to the D coin. The D coin can move to the T circle but not to the A circle or the I circle. You also have to slide the coins one at a time, all the way from one circle to another. And, where paths cross, you can't switch from one path to the other.

Hearn has discovered that such puzzles can be surprisingly tricky. For example, it takes 25 moves to solve the MARTIN GARDNER puzzle, and Hearn has come up with puzzles that take more than 100 moves to solve. In fact, he's written a computer program that searches for the hardest puzzles of a given size.

Here's another one that you might like to try (below). In this case, you put coins on the black circles. Then you have to slide the coins along the paths until there is a coin in every starred circle. Again, you're not allowed to move a coin to a circle directly joined to another coin. You should be able to solve the puzzle in 28 moves.

Are these too tough for you—or not challenging enough? Try changing the rules or inventing your own sliding-coin puzzle. There are lots of possibilities. You can add or subtract paths or change the number of circles or coins. The tricky part is coming up with something that's fun and challenging but not impossible to solve!

Hearn's new brainteasers have inspired designer James Stephens to create a set of puzzles that he calls the "Meandering Monk Maze." You can try them online at www.puzzlebeast.com/monkmaze/index.html.

Muse, February 2006, p. 33.

June 25, 2007

The Beauty of the Bag

The humble brown-paper bag that you use to carry groceries is actually a technological masterpiece that solves many practical problems. Unlike a plastic bag, it can stand upright by itself; you don't need an extra hand to hold it open while you fill it. Yet it folds flat for easy storage.

A standard brown-paper bag can stand upright, as shown above.

It took inventors years to come up with a design that would behave this way. Early paper bags had "envelope bottoms" and wouldn't stand up at all. Then in 1867 Margaret Knight invented a machine that could make the standard bag's rectangular "satchel bottom" in a series of three folds. Another inventor added the accordion folds on the sides of the bag.

The folded form of a standard brown-paper bag lies flat (above).

A company near Savannah, Georgia, now makes 35 million paper bags per day, or about 9 billion per year. That's more than 100 bags for every family in the United States.

A paper bag can be easily folded and unfolded because it is creased. But these creases are more peculiar than you'd think. Suppose you made a bag from a very stiff material, such as steel, and that each crease was some sort of hinge. If the steel bag started out flat, you wouldn't be able to open it, and if it started out open, you couldn't fold it flat. The bag could open or close only if the material could bend, and steel doesn't bend.

The red lines in the diagram (above) show where a paper bag is creased.

Robotics expert Devin Balkcom of Dartmouth College got interested in grocery bags when he was designing a robot that could do "rigid origami," origami folding where the paper stays flat. You can watch his robot fold a paper airplane at www.cs.dartmouth.edu/~robotics/origami.html. The film clip will make you laugh—such a big machine concentrating so hard on such a simple task.

Balkcomm and computer scientists Erik and Martin Demaine of the Massachusetts Institute of Technology independently observed that rigid grocery bags wouldn't fold and worked together on finding some mathematical solutions to this problem. One is to make the bag very short, so it looks more like a collapsible department-store gift box. That gets rid of the place on the grocery bag where several creases meet, blocking collapse. The researchers also figured out how to fold a tall bag without bending the material, but their method requires a whole bunch of new creases and doesn't look much like a grocery bag.

A 'short' bag gets rid of the place on the grocery bag where several creases meet, blocking collapse.

So the next time you use a paper bag, take a closer look at this wonderful invention. There's a lot to ponder in its simple folds.

Muse, January 2006, p. 19.

June 24, 2007

A Good Plot

These days, a lot of people recognize the name Harry Potter, the hero of J.K. Rowling's immensely popular books. But Harry isn't a very popular baby name. In the United States in 2004, it ranked only 531st among names for boys. It was much more popular about 100 years ago, when it ranked in the top 15.

The popularity of the name Harry (above) has fallen since its peak more than 100 years ago. © babywizard.com

This information comes from a fun Web site that's designed to help parents pick names for their offspring. One of its features is a special program that lets you zoom in on particular names and track their popularity over the years (see www.babynamewizard.com/namevoyager/).

The opening screen shows nearly 5,000 names, each represented by a colored stripe (blue for boys' names, pink for girls' names). A stripe's width shows how popular the name was. Moving the cursor to any point in the display highlights a name and reveals its rank during a given decade. For example, you can quickly find out that Mary was the most popular girl's name in every decade from 1880 to 1960. In 2004, the top girl's name was Emily. In the 1960s, Emily was ranked 251.

The spooky thing about first names is that they often tell you a person's age. Chances are that a Susan (above) is 50, but a Madison (below) is probably much younger. © babywizard.com

This display was designed by Laura Wattenberg, who has written a book about picking baby names. She had help from her husband, Martin Wattenberg, who works for IBM developing ways of displaying data that go way beyond graphs and pie charts.

In one recent project, Wattenberg and his coworkers analyzed how people have put together an encyclopedia known as Wikipedia (www.wikipedia.org). This online encyclopedia is being written by people from all over the world. Using colors to represent authors, the researchers produced large displays that showed when text was added to Wikipedia articles.

The history logs for articles from the online encyclopedia Wikipedia can be very revealing. Each color in a log corresponds to a writer. The vertical lines mark different versions of the article. Black gaps in the log indicate text was deleted or vandalized. There are quite a few gaps in the log for the article on evolution (above). © IBM Research

Sometimes authors politely add to what is already there. Other times, they irritably delete what others said and substitute their own version. The article on the Microsoft company is full of gray or white anonymous contributions, but the one on IBM is mostly by authors willing to be identified. And many pages have been vandalized at some point in their history by visitors who came in and deleted text or wrote something rude, damage that shows up as a black gap in the record.

The history log for the article on the Microsoft company (above) is mostly gray and white, colors that indicate the writers wanted to remain anonymous. © IBM Research

Whether you're interested in the popularity of names or how an encyclopedia is put together, the right sort of display can make your search for information that much more revealing—and fun.

Muse, November/December 2005, p. 22.

June 19, 2007

Sudoku Mania

Millions of people around the world can't get started every day without their sudoku fix. Have you joined them?

A sudoku puzzle usually consists of a nine-by-nine grid. Some of the spaces contain numbers; the rest are blank. Your goal is to fill in the blanks with numbers from 1 to 9 so that each row, each column, and each of the nine three-by-three blocks making up the grid contains just one of each of the nine numbers. (Sudoku means "single number" in Japanese.)

Sudoku puzzles are basically logic puzzles. You don't need math to solve them. The numbers could just as easily be nine different shapes, colors, or letters of the alphabet. A smaller grid also works. For example, kids can try to solve simple puzzles that have four-by-four grids with two-by-two boxes.

An easy sudoku. Just fill in the blanks with the numbers 1 through 4.

Mathematicians have calculated that there are 6,670,903,752,021,072,936,960 nine-by-nine number patterns that can be turned into sudoku puzzles. If you were to do one every second of every day, it would take many, many times the age of the universe to complete them all. As it is, even expert solvers can take as long as 30 minutes to solve a challenging sudoku. So, there are plenty of puzzles to keep everyone busy for a long, long time.

If you're eager to join the hordes devouring these puzzles, here are a few hints on how to get started. If you're working on paper, pencil in numbers that might go in a blank until there is only one choice. Look especially for rows, columns, or blocks that have numbers in five or more spaces. That allows you to narrow down the possibilities more quickly.

Another easy sudoku. Just fill in the blanks with the numbers 1 through 6.

Whatever strategy you use, doing sudoku puzzles gives you a chance to sharpen your concentration and reasoning powers. But beware of the nasty frustration factor when you realize that, having just about completed a puzzle, you've got the same number in two spaces in the same row and you have to start all over again. Keep an eraser handy!

You can find some sample sudoku puzzles for kids at www.activityvillage.co.uk/sudoku_for_kids.htm.

Standard sudoku puzzles that you can do online are available at www.websudoku.com.

Additional information about sudoku puzzles, along with tips for solving them, can be found at www.sudoku.com.

Muse, October 2005, p. 25.

June 17, 2007

Icing the Kicker

There are just a few seconds left in the football game. Your team is all set to kick a field goal to win. The opposing team, however, calls a timeout. Its players hope that the extra time will make your kicker think about his upcoming kick—and then miss the field goal. The strategy is called "icing the kicker."

But does this time-honored trick really work? Does making a kicker wait an extra minute or two increase his chances of missing a crucial field goal?

That's not something you can find out directly. You can't let a kicker try a field goal right away and then let him try the same field goal after a delay (or vice versa) and see what happens. Instead, statisticians have to look at data from a lot of games to see if they can detect a difference.

A variety of factors might affect whether a field-goal try is successful. It could depend, for example, on how skilled the kicker is, the length of the kick, the score when the kick is made, and the amount of time left in the game. With that in mind, statisticians Scott Berry and Craig Wood recorded data on all field-goal attempts during the 2002 and 2003 National Football League seasons (including playoff games). They even noted whether the turf (grass or artificial) turf and, for outdoor games, the weather conditions (sun, clouds, rain, average wind speed, temperature).

Taking all these factors into account, Berry and Wood found that icing works. During the last 3 minutes of a football game, a kicker has a somewhat smaller chance of making a field goal if he has to wait and has time to get nervous.

So, at least one piece of sports lore holds up to scrutiny. I'm not so sure about the one about double numbers on a player's jersey bringing good luck, however.

Muse, September 2005, p. 27.

June 16, 2007

Seeing Things

You've probably split sunlight into a rainbow of colors with a prism. Maybe you've also split sunlight with a spray of water from a garden hose or even with a CD. But have you ever tried splitting light with your fingernail?

That's right. Your fingernail. On a bright, sunny day, if you look at sunlight reflecting off your fingernail at just the right angle, you might see a dancing pattern of colorful speckles.

A sunlight speckle pattern photographed by Stewart McKechnie.

A prism, garden hose, and CD all separate the colors into rainbows. Usually, you get speckles only with a laser. A laser, such as a pointer that creates a red spot on a wall or some other surface, produces light of a single color (or wavelength). These waves are also locked in step so that they overlap exactly. Scientists describe them as coherent. When this light reflects from a surface that isn't completely smooth, the waves no longer line up perfectly. In some places, the reflected waves cancel each other to create a dark spot. In other places, they reinforce each other to create a bright red spot. The result is a rapidly shifting pattern of tiny red and black dots.

Sunlight, unlike laser light, is made up of many different wavelengths and these waves are not coherent. Nonetheless, it's possible to see a sunlight speckle pattern under the right conditions, says scientist Stewart McKechnie of ITT Industries in Albuquerque, New Mexico. To see sunlight speckle, he says, you might have to experiment a bit. You have to look at your fingernail from the direction in which it would reflect sunlight if it were a mirror (now there's a concept). And you have to look at it as closely as you can without losing focus. Also, if you have astigmatism this won't work for you (sorry).

So what's happening? It turns out that to scatter sunlight into the speckle pattern, a surface must be rough but not too rough. A fingernail has just the right amount of roughness for you to see the speckles.

Besides, now you have a nice excuse for going outdoors on a bright, sunny day.

Let us know what happens when you try this experiment—even if you fail.

It would be much easier to see sunlight speckle if you lived on Pluto and the sun was just a tiny spot in the sky.

Muse, July/August 2005, p. 19.

June 15, 2007

Math Music

In the right hands, mathematics can be a musical instrument, a spooky player piano that turns numbers, number sequences, or mathematical functions into mysterious and haunting melodies.

Composers create music out of math by inventing special recipes, or formulas, that match numbers or mathematical patterns with musical notes. One example is Daniel Cummerow's recipe for a pi tune. (Pi is the number you get when you divide a circle's circumference by its diameter.)

Cummerow assigned each digit from 1 to 8 to a note of a particular, eight-note musical scale (O.K., for you music nuts, it was A harmonic minor). The digit 0 signaled a pause, and 9 meant a pause or a repeat of the previous note. Identical tones in a row were tied together into a longer note.

Suppose that 1 = do, 2 = re, 3 = mi, 4 = fa, 5 = sol, 6 = la, 7 = ti, 8 = do* (one octave higher). The number pi would become the following tune:

mi, do, fa, do, sol, sol, re, la, sol, mi, sol, do*, do*, ti, ti, mi, re, mi, do*, fa, la, re, la, fa, mi, mi, do*, mi, re, ti, ti, sol, rest, re do*, do*, fa, do, do, ti, do, la, la.

Try singing or playing it. What do you think? Maybe it would sound better with rhythm or dynamics.

Of course, you can change the recipe and make an entirely different kind of music from the same digits. Cummerow, for example, assigned each letter of the alphabet from A to Z to a note with its own pitch, octave, and duration, so he had 26 different notes. He then went through the first 255 digits of pi in pairs, assigning one of these 26 notes to each pair.

And pi is just one of many possible sources of musical inspiration. All sorts of special numbers and mathematical objects can be converted into music. You can use the numbers of an arrangement known as Pascal's triangle or even a geometric pattern, such as the Sierpinski triangle or Lorenz's butterfly, to create music.

A Sierpinski triangle is a large upright triangle, which consists of three smaller upright triangles, each of which consists of three smaller upright triangles, and so on . . . .

Maybe it's not all that surprising that math makes hypnotic music. After all, both music and math are about interesting patterns. Still, hearing pi in A harmonic minor sends shivers up your spine.

If you want to try making your own pi tune, go to Felix Jung's site, www.avoision.com/experiments/pi10k/pi10k.html. You might also want to check out some of the other experimental art pieces at the bottom of the page.

Advanced Math Music: If you have Web browser software that can play MIDI files, you can sample Cummerow's compositions for various mathematical constructs at www.geocities.com/Vienna/9349.

Muse, May/June 2005, p. 16-17.

June 14, 2007

Never Lift the Pencil

Have you ever tried drawing something without lifting your pencil from the paper? You usually end up with a squiggly mess that sometimes looks a bit like the object you were trying to draw.

Now computer scientists have written a program that does first-rate "continuous-line" drawings. Why are they wasting their time on such frivolous things? The answer is that the drawings are actually a version of an important mathematical problem that turns up in many everyday situations.

A continuous-line version of Leonardo da Vinci's Mona Lisa portrait.

Suppose you're at a humongous mall with dozens of stores. You need to visit nine of them to find that Naruto manga you put down somewhere, before your mom arrives to pick you up. What's the shortest route between all nine stores and the mall entrance?

One way to solve the problem is to get out a map of the mall, locate the entrance and the nine stores you need to visit, and measure all the different distances. You can then list the possible routes, calculate the length of each route, and pick the shortest one.

Whew! That sounds like a lot of work, and it is. In fact, you would have to check 362,880 (9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1) possibilities. As the number of stores increases, the number of possibilities skyrockets. Imagine how many there would be if you were to visit all 99 stores in the mall.

Mathematicians and engineers often have to make such calculations, whether to design networks carrying phone calls across the country, to plan routes for shipping goods from a warehouse, or to create schedules. Over the years, they've developed efficient ways to solve problems of this type.

The current world record for such a calculation is a route that visits all 24,978 cities, towns, and villages in Sweden. Despite the efficient method, finding that route took a lot of computer time!

You can see the Swedish tour at http://www.tsp.gatech.edu/sweden/index.html (Georgia Tech).

Robert Bosch and Adrianne Herman of Oberlin College in Ohio use a similar method to make continuous-line drawings of celebrities, works of art or architecture, or friends. Their computer program starts with a black-and-white digital image. The picture is divided into squares, and an average darkness is computed for each square.

Then a blank digital "canvas" is divided into matching squares, and a computer randomly places points (the "cities") within each square. The number of points in a square is related to the square's darkness. Next, distances between the points are computed.

Finally, the program then solves the problem of visiting all those points, one by one, to produce a route. Voila! It produces a continuous-line drawing, which from a distance actually looks a bit like the original image.

For more on continuous-line drawings, go to http://www.oberlin.edu/alummag/spring2004/ats.html (Oberlin College).

Robert Bosch's domino artworks are featured in the MatheMUSEments article Seeing Spots.

Muse, April 2005, p. 17.

June 12, 2007

Random Knots

Have you ever left a necklace or a piece of string lying around on a table in a jumbled heap? There's a good chance that it will have formed a knot when you pick it up again, especially if it has been jostled a little. The same thing can happen to a garden hose left in an untidy pile on the ground.

Sailors and rock climbers know about this problem, so they take great care to store their ropes in ways that prevent accidental knotting. Because we're used to making some effort to tie a knot, the unintended formation of knots in ropes, hoses, strings, and necklaces can be frustrating and puzzling.

Topologists—mathematicians who study shapes—have investigated how knots can form accidentally. Imagine a three-dimensional grid made up of lines that define a set of evenly spaced rows, columns, and stacks. Suppose a "walker" were to start at one point, or vertex, of this grid. The walker steps randomly from one vertex to the next vertex in any one of the six directions available from a given point.

A self-avoiding walk in three dimensions can create a knotted path.

Because the path is chosen randomly, perhaps by rolling a die to determine the direction of each step, topologists call the walker's path a random walk. When the walker is not allowed to revisit the same vertex a second time, the path is called a self-avoiding random walk. Mathematicians have proved that the longer the random walk, the greater its chance of forming a knot.

So, it shouldn't really come as a surprise that a rope, necklace, or garden hose—if it's long enough—is quite likely to settle into a knot. There's no getting away from knotty situations!

Muse, March 2005, p. 29.

June 10, 2007

Chomping to Victory

It's often tough to figure out how to win even a really simple game.

Consider the two-player game called Chomp. A move consists of picking one checker anywhere in a rectangular array of checkers, then removing that checker along with all the checkers above and to the right of it. It's like taking a big, neat bite out of a chocolate bar divided into easy-to-break-off sections.

You and your opponent take turns "chomping" on the checkers. The loser is the player forced to take the last "poisoned" checker in the lower left corner.

Chomp on a 5-by-6 field (above). The first player selects a counter (green, top left) and removes a block of six counters (top right). The second player selects one of the remaining counters (yellow, top right) and removes a block of two counters (bottom left). The first player responds, leaving the L-shaped array shown at bottom right. Who will be forced to take the last, poisoned counter (red)?

When you start with a square of checkers, the first player can automatically win. Can you see how?

Here's the strategy. If you go first, pick the checker that's diagonally up and to the right of the poisoned checker. Such a bite leaves one row and one column, with the poisoned piece at the corner. From that point on, simply take from one line whatever your opponent takes from the other line. Eventually, your opponent is forced to take the poisoned piece.

If the checkers are in a narrow rectangle that's two checkers wide and any number of checkers long, the first player also wins automatically. If you go first, take one checker from the end of one line so that one column or row is one checker longer than the other. Depending on what your opponent does in his or her turn, pick a checker that again makes one column or row one checker longer than the other. Again, your opponent gets stuck with the poisoned piece.

Here's the frustrating thing. Mathematicians have proved that the first player always wins—whether the checkers are in a square or in any sort of rectangle. The trouble is that no one has been able to figure out a foolproof winning strategy that works every time if the initial rectangle of checkers has more columns than it has rows (except when there are only two rows).

Maybe you can help. Can you figure out a strategy for chomping to victory when you have checkers in a pattern that is three rows long and any number of columns wide? Start with a small pattern, such as 12 checkers arranged in four columns and three rows, then go from there.

Happy chomping!

You can play Chomp online at lpcs.math.msu.su/~pentus/abacus.htm or www.duke.edu/~ljw6/ooga/chompgame.html.

Muse, February 2005, p. 35.

June 9, 2007

You've probably heard the one about Archimedes, the Greek mathematician who jumped out of the tub and ran naked through the streets shouting, "Eureka! Eureka!" Legend has it he suddenly realized how to tell a wreath made of pure gold from one made of a mixture of gold and silver. First, put a weight of pure gold equal to the wreath's weight into a bowl and fill the bowl with water. Then, take out the weight and put the wreath into the bowl; if the wreath contained the lighter and bulkier element silver, the bowl would overflow.

That story probably isn't true. Archimedes made many far more important discoveries during his lifetime—discoveries that would have excited him a good deal more than water spilled out of a tub. But it does have an element of truth: Archimedes was interested in things that float, so much so that he wrote two books about them.

He was especially fascinated by paraboloids (see below), objects that look like rocket nosecones. How do you think a paraboloid would float? With its nose down and flat side up? On its side? At some angle? With its flat side down?

Archimedes found that a paraboloid could float in different ways. Which way if floated depended on two things: its density (its weight compared to the weight of an equivalent volume of the liquid it was floating in) and the paraboloid's taper.

Archimedes looked only at cases where the paraboloid's flat base is completely above or below the liquid's surface, because that is all the math of his day could handle. Recently, mathematician Chris Rorres of the University of Pennsylvania completed the analysis by working out what happens when the base is partially submerged.

A paraboloid almost as dense as the liquid would float point down, with its flat base sticking up out of the liquid a little. But if its surface eroded and it became narrower, it might suddenly tilt and tumble onto its side.

The same thing can happen to icebergs, many of which float with broad bases up and points under water. As the iceberg melts, its underwater part is whittled down, until suddenly the entire mass topples over, throwing off any penguins or polar bears who happen to be hitching a ride.

A paraboloid much less dense than the liquid will float upright, with its base barely immersed. But if the liquid somehow became less dense, this paraboloid might fall over, too.

This also happens in real life. During an earthquake, a tall building built on water-saturated soil is like a floating paraboloid. As the soil "liquefies" and becomes less dense, the building can tilt, exposing its base, and then fall over.
Archimedes would have loved it.

You can see animations of floating paraboloids at www.math.nyu.edu/~crorres/Archimedes/Floating/floating.html.

Muse, January 2005, p. 23.

Images courtesy of Chris Rorres.

June 7, 2007

Earth Hole

Forget about the heat and the pressure and the iron core. Imagine there's a hole that goes all the way through Earth, passing through its center. If you dropped a stone into this hole, what do you think would happen?

Normally when you drop a stone, it falls to the ground, pulled by Earth's gravity. For a stone falling through Earth, the situation is a little different. At the surface, it's attracted by all of Earth. As it travels down the hole, the stone is attracted by parts of Earth that are both above and below it. So, the force pulling the stone downward gets smaller as the stone travels toward Earth's center.

At the center of Earth, the stone is weightless. It's attracted equally in all directions, so it experiences no net force. Everything cancels out.

What does this changing force do to the stone's motion? Because it experiences a downward force all the way to Earth's center, the stone goes faster and faster even as this force gets smaller and smaller. It reaches its highest speed at Earth's center.

Because there's no force a acting on it there, the stone overshoots. As it travels away from the center, the force pulling the stone back toward the center gets stronger and stronger. The stone slows down more and more. When it finally reaches the surface on the other side of Earth, it comes to a stop for an instant. Then, unless someone snatches it out of the air, it begins to fall again, repeating its trip through Earth.

Galileo Galilei argued in 1632 that a cannonball dropped down such a hole would oscillate forever between the drop site on one side of Earth and the exit hole on the other side. Each round trip would take 84.6 minutes. It wouldn't matter whether you dropped a cannonball or a pebble: The trips would take the same amount of time.

If you take air resistance into account, however, a dropped stone wouldn't actually make it all the way to the other side of Earth. Instead, with each trip through the center, it would travel less and less far, eventually getting trapped in the middle. The weightless stone would then simply float at Earth's center.

But Earth also spins. So, as the stone falls, Earth moves around it. For this reason, Isaac Newton argued in 1679 that, unless it was dropped along Earth's spin axis (a line joining the north and south poles), a stone would follow a curved path. The closer to the equator the stone was dropped, the wider the curve would be. A stone dropped at a point on the equator would curve wide enough that it would hit the hole's wall—unless the hole was more than 300 kilometers wide.

What a way to go!

Muse, November/December 2004, p. 17.

June 6, 2007

Poe, E.: Near a Raven

Quick! What are the first nine digits of π, the number known as pi?

You probably know pi as the number you get when you divide a circle's circumference by its diameter. You might even have a calculator that gives you the value of pi to eight or more decimal places: 3.14159265. . . . Remarkably, mathematicians have proved that the digits of pi go on forever, although only about 1 trillion have been calculated so far.

This hasn't stopped people from trying to memorize as many digits of pi as they can. Contests to see who can rattle off the largest number of digits are one feature of National Pi Day, which is celebrated in math classrooms and schools on, naturally, March 14. The current record is about 42,000 digits!

One way to remember at least some of the digits is to turn them into a sentence, where the number of letters in the words corresponds to the digits of pi. For example, the sentence "Can I have a small container of coffee?" gives the first eight digits of pi. Or, if you want just six digits: "Wow, I made a great discovery." Can you come up with a sentence of your own that gives, say, 20 digits of pi?

Mike Keith, a pi fanatic, has composed a poem, "Poe, E.: Near a Raven," that encodes 740 digits of pi (see below). He has also written a short story in which the number of letters in the words gives the first 3835 digits. He says these pi compositions are harder to wrote than compositions that leave out a vowel. His proof? There are two novels that do not use the letter e, but his short story is the longest pi composition in existence.

You could also come up with phrases or sentences to remember the first few digits of other numbers that go on forever. The phrase "I wish I knew" gives you the first four digits of the the square root of two, for example. Who knows? These memory aids may come in handy some day when your calculator dies at a critical moment.

Poe, E.
Near a Raven

Midnights so dreary, tired and weary.
Silently pondering volumes extolling all by-now obsolete lore.
During my rather long nap—the weirdest tap!
An ominous vibrating sound disturbing my chamber's antedoor.
"This," I whispered quietly, "I ignore."

Perfectly, the intellect remembers: the ghostly fires, a glittering ember.
Inflamed by lightning's outbursts, windows cast penumbras upon this floor.
Sorrowful, as one mistreated, unhappy thoughts I heeded:
That inimitable lesson in elegance—Lenore—
Is delighting, exciting . . . nevermore.

You can find the complete Poe poem at http://cadaeic.net/naraven.htm (Mike Keith).

The full text of Edgar Alan Poe's "The Raven" can be found at www.eapoe.org/works/poems/ravena.htm (Edgar Alan Poe Society of Baltimore).

Muse, October 2004, p. 17.

June 5, 2007

Tricky Crossings

Have you ever heard the one about a farmer traveling with a fox, a goose, and a bag of grain?

The farmer comes to a river and finds a small boat that will hold only two passengers. For obvious reasons, he can't leave the fox alone with the goose, or the goose with the grain. How does he get his cargo safely to the other side?

Brainteasers that involve ferrying people and their belongings across a river under trying conditions have been around for centuries. This particular version dates back more than 1100 years. Such puzzles are simply ways of dressing up fairly standard math problems. To solve them, you can use math and logic, or you can try trial and error. There are often lots of different ways to solve a given problem.

So, what does the farmer do? Here's one answer. The farmer crosses the river with the goose and leaves the goose on the far shore, then returns alone to the near shore. He brings the fox to the far shore and brings the goose back to the near shore. He then brings the grain to the far shore and returns alone to the near shore. Finally, the farmer brings the goose to the far shore. It takes seven trips.

Another type of river-crossing puzzle also features a predator, its prey, and some food. In this case, however, the human can transport two items at one time, which changes the logical structure of the problem. For instance, a herdsman in North Africa might have to cross a river with a jackal (a predator), a goat (potential prey), and fig leaves (potential snack for goat).

But there are countless other variations on the river-crossing problem as well. Often the players and the situation reflect the culture of a particular place and time. What is a fox in Europe becomes a jackal in North Africa.

Here's a Russian version. Two boys with a boat agree to help three soldiers cross a river without a bridge. 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. How many trips does it take to ferry all the soldiers across?

This cultural coloring also means old problems can be sexist or racist by today's standards. In the 16th century, one version featured three beautiful brides and their young, handsome, and intensely jealous husbands. The small boat that is to take them across the river holds no more than two people. To avoid 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 all six across the river without an angry outburst?

A 19th-century version features three missionaries, three cannibals, and a boat that holds only two people. In this case, the cannibals must never be allowed to outnumber missionaries on either bank. How many trips does it take?

New versions of the river-crossing problem continue to be invented. One puzzle found on the Internet involves crossing a rickety bridge at night within a certain time period with just one lantern to light the way.

Even job seekers might find they have to solve one of these puzzles. They're sometimes part of the interview at places such as Microsoft. Talk about a pop quiz!

From the days of ancient Egypt to modern times, river-crossing problems have turned routine math exercises into puzzles that tickle your mind.

The Jackal, the Goat, and the Fig Leaves. 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. Three trips.

The Russian Soldiers and the Boys. 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. Twelve trips.

The Three Beautiful Brides and Their Jealous Husbands. Say the couples are named John and Joan, Edward and Elinor, Richard and Rose. Elinor and Rose cross; Rose returns; Joan and Rose cross; Rose returns; John and Edward cross; John and Joan return; Richard and John cross; Elinor returns; Elinor and Joan cross; Elinor returns; Rose and Elinor cross. Eleven trips.

The Cannibals and the Missionaries. 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; two cannibals cross; one cannibal returns; and the remaining two cannibals cross. Eleven trips.

Muse, September 2004, p. 34-35.

June 4, 2007

Champion Paper-Folder

You've probably heard that it's impossible to fold a sheet of paper in half more than seven or eight times. Usually you're also told that it doesn't matter how big or thin the sheet is.

Try folding a sheet of notebook paper. You'll probably find that it is pretty tough to get beyond eight folds. However, just because people—even experts—say something's impossible doesn't mean it is. That's what high-school student Britney Gallivan discovered when she succeeded in folding a sheet in half an unheard-of 12 times. She had to solve the problem to get extra credit in one of her math classes.

Britney Gallivan and her folded paper sheet after the eleventh fold. Photo by James Gallivan.

Why is it hard to get past eight folds? Suppose you're just folding in one direction instead of turning the paper 90 degrees between folds. Each time you fold, the thickness of the folded wad doubles and its width is halved. If you start with a standard sheet of paper, after seven folds, the wad is thicker that it is wide, and it takes too much strength to fold it again.

Analyzing the problem this way, however, you might begin to wonder whether you could beat the limit by folding something very, very thin or something very, very wide.

At first, Britney tried thin. She spent hours trying to fold paper sheets, newspapers, and any other flat material that she could get her hands on. Paper didn't appear to work, so she decided to use gold foil—only 11 millionths of an inch thick. Working with soft artists' brushes, rulers, and tweezers, she managed to fold a 4-inch-by-4-inch square of gold foil in half 12 times without tearing the extremely delicate sheet.

But that wasn't good enough. Britney's teacher said the problem was to fold a sheet of paper—not gold foil—12 times.

Determined to solve the problem, Britney tried again. This time she decided to go for width. If she used paper that was the same thickness as regular paper, she calculated, she would need a roll that was nearly 4000 feet long (about three-quarters of a mile) to be able to fold it 12 times. She found special toilet paper that met these requirements and bought a roll for \$85.

Equipped with her jumbo roll, Britney went to a shopping mall in her hometown of Pomona, California. She unrolled the paper and marked the halfway point. It took three people (Britney and her parents) 7 hours, mostly on hands and knees, to complete the folding.

"The problem was a lot of work, a lot of frustration, a lot of fun, and I learned a lot from it," Britney later wrote in a booklet describing her accomplishment. "The world was a great place when I made the twelfth fold."

You can order a copy of Britney's booklet at pomonahistorical.org/12times.htm (Historical Society of Pomona Valley).

Muse, July/August 2004, p. 33.

June 3, 2007

Sink or Be Sunk

It's sink or be sunk in the game of Battleship, the cat-and-mouse game where players try to figure out where their opponent's fleet is deployed. You probably know the paper-and-pencil, pegboard, or electronic versions. And if you don't, you can play a version of the game online at javascript.internet.com/games/battleship.html.

But Mogens Esrom Larsen of the University of Copenhagen has invented a much trickier version of Battleship, where the ships aren't straight and the goal is to hit the open water rather then them.

In Larsen's game the game pieces are special shapes called pentominoes. Dominoes consist of two squares stuck together; a pentomino is made up of five squares. Each player has 11 pieces: the 12 possible pentominoes, named for the letter of the alphabet they most resemble.

The game board is a standard checkerboard with 64 squares. The 12 pentominoes take up a total of 60 squares. Each player fits together the 12 pentominoes to cover the board, leaving just four empty squares. This can be done in many different ways. Here's one example:

The goal of the game is to find the four empty squares on your opponent's grid. Each player, in turn, fires a volley of four shots. Your opponent then tells you how many shots hit which pentomino.

One good offensive strategy is to hit the corners. In the example below, a player has hit a1, b1, a8, and h8. His opponent must tell him that he hit the N pentomino twice, the Z pentomino once, and the P pentomino once. The player then knows the Z, P, and N pentominoes are in the corners. But he doesn't know how any of these pieces are oriented. The P, for example, could be upside down or flopped.

What about a defensive strategy? You want to come up with a starting arrangement of pentominoes that makes the four empty squares hard to find. One way to make the problem manageable is to build your board around the F pentomino, which is one of the few that are not symmetric. If you put the F on a three-by-three square by itself, you end up with four empty squares. And there are eight different ways to place the F on this grid.

If you placed the F grid away from the corners of the larger board, your opponent wouldn't be able to locate it by hitting the corners. And even if he did hit the F, he wouldn't know which of the eight possible orientations it had. It would probably take him several more turns to find out, enough time for you to find his open squares.

The new game combines the challenge of fitting together jigsaw pieces with the fun of sinking the fleet.

Muse, May/June 2004, p. 28-29.

June 2, 2007

Knight's Tour

"I'm going to be a knight," said Ron. With that remark, Ron Weasley took charge of a deadly, larger-than-life game of wizard chess, played near the climax of Harry Potter and the Sorcerer's Stone.

Deciding to be a knight was an interesting choice. Chess has six different kinds of pieces: king, queen, bishop, knight, rook, and pawn. Each piece moves in its own special way. The knight stands out because, unlike the other pieces, it doesn't move in a straight line. It makes L-shaped moves, jumping over anything in its way to reach an empty square on a chessboard.

For example, a knight can move two squares forward, then one square sideways, or it can move one square forward, then two squares sideways.

The special way in which a knight moves not only adds drama to chess games but also suggests various puzzles mathematicians and others have spent untold hours trying to solve.

One of the oldest of these puzzles is called the knight's tour: Given the ways in which a knight is allowed to move, is it possible for a knight to start at one square on an empty chessboard, then land on each of the other squares, visiting each square exactly once?

Try it. Get out a chessboard and a knight. Pick a starting point. Make legal knight moves, keeping track of each square the knight visits.

In fact, it turns out there's a huge number of ways a knight can make such a tour. In some cases, the knight ends up at its starting point, after visiting all the other squares once.

Here's another, tougher puzzle. What is the smallest number of knights that you would need to place on a chessboard so that every vacant square could be reached by a knight in one move? For a standard chessboard, the answer is 12. Any idea where you would put them? The answer can be found at www.contestcen.com/kn3.htm.

As you can see, board games such as chess can keep you busy in all sorts of ways.

Muse, April 2004, p. 35.

June 1, 2007

Solve It or Die

It's a tense moment in Die Hard with a Vengeance. A time bomb is about to go off. The frazzled heroes, detective John McClane and his sidekick Zeus, a dry cleaner from Harlem, have just seconds to defuse it. To their horror, they discover they must solve a mathematical puzzle to do so.

Sitting on the lip of a fountain in a park are a 5-gallon jug and a 3-gallon jug. The timer will stop if they place a jug containing 4 gallons of water on a scale attached to the bomb.

Bumbling about, our heroes realize that it won't do to use the smaller jug to pour 3 gallons into the larger one, then refill the smaller jug one-third of the way up to get the extra gallon. The villain, being a villain, had insisted that the total amount be exactly 4 gallons.

The puzzle that John and Zeus have to solve has actually been around for a long time—at least since the 1200s, to be exact. You often find it in collections of brainteasers. Can you solve it—in less than 30 seconds? One solution is given below. Can you think of another?

After a lot of yelling and confusion, John and Zeus solve the puzzle, stop the timer, and save the day. But if you watched this particular scene closely (doubtful, since the movie is rated R), you'd have seen that it wasn't filmed very carefully. Water levels in the jugs rise and fall throughout the sequence without human intervention. Some Hollywood magic, perhaps?

There are lots of puzzles that involve measuring out given amounts using various jugs. Here's another one for you to try: Given an 11-gallon jug and a 4-gallon jug, measure out exactly 1 gallon. Maybe this puzzle, or another one like it, will show up in the fourth Die Hard movie.

How to Measure Out 4 Gallons
• Fill the 5-gallon jug.
• Empty the 5-gallon jug into the 3-gallon jug, leaving 2 gallons.
• Empty the 3-gallon jug.
• Pour the 2 gallons from the 5-gallon jug into the 3-gallon jug.
• Fill the 5-gallon jug and use it to fill the 3-gallon jug. That leaves 4 gallons in the 5-gallon jug.

Muse, March 2004, p. 45.