It's easy to learn to play checkers, but it takes a lot of practice to become an expert player, and no one has ever played checkers flawlesslyuntil now. This spring, a computer program became the first perfect checkers player ever. Tic-tac-toe, connect four, and other simple games were "solved" long ago, but checkers is the first of the complex games to fall.
Computer scientist Jonathan Schaeffer of the University of Alberta, who describes himself as an "awful" checkers player, has been studying the game for nearly 20 years. Schaeffer's initial goal was to create a computer program that played checkers so well that it could beat the human world champion. Named Chinook, the program took the title in 1994, becoming the first computer program to win a human world championship in any game.
Schaeffer's next goal was to turn Chinook into a perfect player. This meant figuring out the best move to make given any of the 500 billion possible positions in the game. It took as many as 200 computers, running for years, to work out all the possibilities, but he and his coworkers finally finished the job in 2007. With this information now at its disposal, Chinook plays perfectlyand never losesnot because it is smart but because it can check the possible outcomes for every move it makes.
If you want to learn more about Chinook or even play against the program, go to www.cs.ualberta.ca/~chinook/.
Schaeffer's team also proved that if two players both play perfectly, the game always ends in a draw. Top checkers players had long suspected this, but the researchers proved it. This doesn't mean that checkers is no longer fun. You're highly unlikely to come across anyone who plays perfectlyunless you're playing Chinook. Then, you really don't have a chance.
The Rules of Checkers
Two players take turns moving pieces on an eight-by-eight checkerboard. Each side starts off with 12 checkers. Checkers move diagonally forward one square (staying on the same color square). You can capture (and remove) an opponent's piece by "jumping" your checker over it and landing in an empty space. When a checker reaches the far end of the board, it is "crowned" and becomes a king. Kings also move diagonally, but they are allowed to go backward as well as forward. A player loses when he or she has run out of pieces or has no legal moves left.
Muse, November/December 2007, p. 36.
MatheMUSEments
Articles for kids about math in everyday life, written by Ivars Peterson for Muse magazine.
November 5, 2007
October 10, 2007
Mystic Puzzler
Lots of computer games have you whacking monsters as you struggle to find better weapons and power up. Some games, however, rely on puzzles more than single combat. If your game is one of the puzzling kind, trial and error might get you by, but a bit of logic or mathematical knowledge will often speed you on your way.
Near the beginning of the game Myst, for example, you encounter a contraption that has three levers and three stacked dials, each one reading 3.
Pulling the levers reveals that each of the dials is three sided. Rotating a dial reveals other faces, numbered 1 and 2. If you've been paying attention to other clues in the game, you realize that your task is to use the levers to rotate the blocks until they read 2, 2, 1 instead of 3, 3, 3.
But how do you do this?
Jessica Sklar of Pacific Lutheran University in Tacoma, Washington, is both a mathematician and a gaming geek, and she especially loves games that contain puzzles. Here's how she would tackle the Myst puzzle.
Let's label the levers A, B, and C. Experimenting, you soon discover that pulling lever A leaves the top block unmoved and turns the middle and bottom blocks to show the next face. So, if you start with faces 1, 2, 3 (from top to bottom), the new pattern after pulling lever A would be 1, 3, 1. Pulling lever B leaves the bottom dial unmoved and rotates the top two dials. Lever C resets the blocks to their original 3, 3, 3 pattern.
It turns out there's no way to get from 3, 3, 3 to 2, 2, 1 by pulling the levers. You have to pull lever B twice to get the top block from 3 to 2. In so doing, you also move the second block to 2. To move the third block to 1, however, you have to use lever A once. And that also moves the second blockback to 3. No combination of moves works, and Sklar can prove mathematically that's absolutely true.
So there has to be a trick. Indeed, if you play with the levers a bit, you find out that you can give the middle block an additional turn by holding down lever A or B.
Now, there's a solution. Pull lever A once, lever B twice, then hold lever B down after its second pull just long enough to turn the second block two more times. Pretty sneaky! You hear a grinding noise, and the gear at the bottom of the contraption opens, giving you access to a book that allows you to travel in a different world.
Many computer games contain logic and math puzzles. You'll find them in Myst, Timelapse, and Trinityand even in SpongeBob SquarePants: Battle for Bikini Bottom. You never know when some math may come in handy.
Muse, October 2007, p. 36.
Near the beginning of the game Myst, for example, you encounter a contraption that has three levers and three stacked dials, each one reading 3.
Pulling the levers reveals that each of the dials is three sided. Rotating a dial reveals other faces, numbered 1 and 2. If you've been paying attention to other clues in the game, you realize that your task is to use the levers to rotate the blocks until they read 2, 2, 1 instead of 3, 3, 3.
But how do you do this?
Jessica Sklar of Pacific Lutheran University in Tacoma, Washington, is both a mathematician and a gaming geek, and she especially loves games that contain puzzles. Here's how she would tackle the Myst puzzle.
Let's label the levers A, B, and C. Experimenting, you soon discover that pulling lever A leaves the top block unmoved and turns the middle and bottom blocks to show the next face. So, if you start with faces 1, 2, 3 (from top to bottom), the new pattern after pulling lever A would be 1, 3, 1. Pulling lever B leaves the bottom dial unmoved and rotates the top two dials. Lever C resets the blocks to their original 3, 3, 3 pattern.
It turns out there's no way to get from 3, 3, 3 to 2, 2, 1 by pulling the levers. You have to pull lever B twice to get the top block from 3 to 2. In so doing, you also move the second block to 2. To move the third block to 1, however, you have to use lever A once. And that also moves the second blockback to 3. No combination of moves works, and Sklar can prove mathematically that's absolutely true.
So there has to be a trick. Indeed, if you play with the levers a bit, you find out that you can give the middle block an additional turn by holding down lever A or B.
Now, there's a solution. Pull lever A once, lever B twice, then hold lever B down after its second pull just long enough to turn the second block two more times. Pretty sneaky! You hear a grinding noise, and the gear at the bottom of the contraption opens, giving you access to a book that allows you to travel in a different world.
Many computer games contain logic and math puzzles. You'll find them in Myst, Timelapse, and Trinityand even in SpongeBob SquarePants: Battle for Bikini Bottom. You never know when some math may come in handy.
Muse, October 2007, p. 36.
August 24, 2007
Changing the Soccer Ball
If you've kicked around a soccer ball, you've probably noticed the distinctive pattern on the ball's surface. For a long time, soccer balls have been stitched or glued together from 32 pieces of material. Twelve of these patches are five-sided (pentagons), and twenty of them are six-sided (hexagons). These patches are arranged so that each pentagon is surrounded by hexagons. Traditionally, the pentagons are colored black and the hexagons white.
This type of soccer ball is based on a geometric shape called a truncated icosahedron. An icosahedron has 20 flat faces, each one a triangle, with five triangles meeting at each corner. If you slice off the corner of an icosahedron, you reveal a pentagon. By slicing off all 12 of an icosahedron's corners, you end up with 12 pentagons and 20 hexagons. The new shape has 60 corners. A soccer ball differs from this shape in that its faces are curved rather than flat, which means the ball is just about as rounded as a sphere.
A truncated icosahedron (left) and a standard soccer ball (right). Wikipedia.
Now, there's a new ball design. It was introduced as the official soccer ball at last year's World Cup. Designed by engineers at Adidas, this ball is made from 14 curved panels to give it a smoother look and feel. It has fewer seams so the ball is rounder. Experts say the ball behaves more predictably that the old one did. You're less likely to get a wayward hook or an unexpected swerve when you kick it properly.
The official soccer ball for the 2006 World Cup is made from 14 curved panels. Adidas.
The official ball is also made from materials that make it practically waterproof. This makes a big difference when the ball gets wet. Because the old ball tended to absorb moisture and gain weight in the rain, it would fly slower, bounce lower, and curl less than the new one does.
Your soccer team is still probably using the old type of ball, but watch out for the new one. The way it bounces and bends might take you by surprise.
Muse, September 2007, p. 36.
This type of soccer ball is based on a geometric shape called a truncated icosahedron. An icosahedron has 20 flat faces, each one a triangle, with five triangles meeting at each corner. If you slice off the corner of an icosahedron, you reveal a pentagon. By slicing off all 12 of an icosahedron's corners, you end up with 12 pentagons and 20 hexagons. The new shape has 60 corners. A soccer ball differs from this shape in that its faces are curved rather than flat, which means the ball is just about as rounded as a sphere.
A truncated icosahedron (left) and a standard soccer ball (right). Wikipedia.
Now, there's a new ball design. It was introduced as the official soccer ball at last year's World Cup. Designed by engineers at Adidas, this ball is made from 14 curved panels to give it a smoother look and feel. It has fewer seams so the ball is rounder. Experts say the ball behaves more predictably that the old one did. You're less likely to get a wayward hook or an unexpected swerve when you kick it properly.
The official soccer ball for the 2006 World Cup is made from 14 curved panels. Adidas.
The official ball is also made from materials that make it practically waterproof. This makes a big difference when the ball gets wet. Because the old ball tended to absorb moisture and gain weight in the rain, it would fly slower, bounce lower, and curl less than the new one does.
Your soccer team is still probably using the old type of ball, but watch out for the new one. The way it bounces and bends might take you by surprise.
Muse, September 2007, p. 36.
July 6, 2007
Seven Bridges
Suppose that you live in a town that sprawls across the banks of a branching river, with an island in the middle. Seven bridges link the different parts of town. One sunny summer day, you decide to take a bike ride. Looking at a map, you try to find a route that would take you across all the bridges and back to where you started. You also add the challenge never to cross the same bridge more than once. If you succeed, you decide, an ice cream reward awaits you on your return.
Is it possible to find such a route? Try it.
This illustration shows the seven bridges (green) of 18th-century Königsberg.
It turns out there is no such route. The first person to prove that it can't be done, nearly 300 years ago, was a famous mathematician named Leonhard Euler (pronounced OIL-er). The puzzle originally concerned a city in northern Europe, Königsberg, which really did have a branching river running through it, with an island and seven bridges. (The city is now called Kaliningrad and is part of Russia.)
In essence, the bridges connect four separate pieces of land. Anyone standing on any given land mass would have to have a way to get on and, if they wanted not to cross the same bridge twice, a different way off. That means 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.
Leonhard Euler was an amazing person. Some people describe him as the greatest mathematician of all time. He was born in Basel, Switzerland, on April 15, 1707 (so this year was the 300th anniversary of his birth). As a young boy, he found it very easy to learn languages. He had an extraordinary memory and could do all sorts of mental arithmetic with astonishing speed. He entered the University of Basel at the age of 14 and obtained his degree three years later.
Interestingly, if you were to visit Kaliningrad today, you would find that two of the bridges no longer exist, and a single bridge has replaced a pair of the bridges that crossed from one side of the river to the other via the island. A set of stairs in the middle of the bridge allows you to visit or leave the island.
This satellite image shows Kaliningrad today, with its new arrangement of bridges.
It's now possible, if you start on the island, to follow a route that crosses all the bridges without crossing any one of them twice. With this restructuring, the city planners may have thought they were foiling Euler's toiling. But of course, being a mathematician, Euler didn't just solve a single problemhe solved the problem generally. That is, he worked out rules for figuring out whether such routes exist for any number of land masses and bridges.
Muse, July/August, 2007.
Is it possible to find such a route? Try it.
This illustration shows the seven bridges (green) of 18th-century Königsberg.
It turns out there is no such route. The first person to prove that it can't be done, nearly 300 years ago, was a famous mathematician named Leonhard Euler (pronounced OIL-er). The puzzle originally concerned a city in northern Europe, Königsberg, which really did have a branching river running through it, with an island and seven bridges. (The city is now called Kaliningrad and is part of Russia.)
In essence, the bridges connect four separate pieces of land. Anyone standing on any given land mass would have to have a way to get on and, if they wanted not to cross the same bridge twice, a different way off. That means 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.
Leonhard Euler was an amazing person. Some people describe him as the greatest mathematician of all time. He was born in Basel, Switzerland, on April 15, 1707 (so this year was the 300th anniversary of his birth). As a young boy, he found it very easy to learn languages. He had an extraordinary memory and could do all sorts of mental arithmetic with astonishing speed. He entered the University of Basel at the age of 14 and obtained his degree three years later.
Interestingly, if you were to visit Kaliningrad today, you would find that two of the bridges no longer exist, and a single bridge has replaced a pair of the bridges that crossed from one side of the river to the other via the island. A set of stairs in the middle of the bridge allows you to visit or leave the island.
This satellite image shows Kaliningrad today, with its new arrangement of bridges.
It's now possible, if you start on the island, to follow a route that crosses all the bridges without crossing any one of them twice. With this restructuring, the city planners may have thought they were foiling Euler's toiling. But of course, being a mathematician, Euler didn't just solve a single problemhe solved the problem generally. That is, he worked out rules for figuring out whether such routes exist for any number of land masses and bridges.
Muse, July/August, 2007.
July 5, 2007
Spiraling Triangles
Playing with triangles can lead to amazing patterns and three-dimensional structures. That's what Hungarian designer Dániel Erdély (below) found when he created an intriguing geometric form out of two spirals of triangles that get smaller and smaller.
Daniel Erdély holds a complex polyhedron constructed from spidrons. Photo by Regina Márkus.
He called the resulting S-shaped object a spidron. Each of its two arms looks a bit like a seahorse's tail.
The two spiral arms of a spidron consist of alternating sequences of equilateral and isosceles triangles (above). Erdély.
How to Draw a Spidron's Arm (above): Start with a regular hexagon, which has six corners. Connect every send corner with a straight line to make a six-pointed star. Inside the star is a smaller hexagon. Again connect every second corner. Continue the process until the shape in the center is so small that you can't put in any more lines. The resulting pattern contains six identical copies of a spidron arm. Erdély.
Even though spidrons are irregularly shaped, they can fit together without gaps or overlaps to cover a plane (above). For example, you could tile your bathroom floor with this pattern of spidrons. Erdély, Marc Pelletier, Amina Buhler Allen, Walt van Ballegooijen.
When spidrons are laid down like tiles on a flat surface, then creased in just the right way at the line within each spidron arm, the flat structure can be forced to fold accordion-style into a wavy surface (above). As the folds get steeper, the whole pattern twists and compacts. Erdély, Marc Pelletier, Amina Buhler Allen, Walt van Ballegooijen.
Creased and folded spidrons can be assembled into three-dimensional balls (above). This one is made of 120 spidrons. Erdély, Marc Pelletier, Amina Buhler Allen, Walt van Ballegooijen.
Are spidrons good for anything besides artwork and maybe bathroom floors? Erdély says spidron surfaces could be used for collapsible solar panels or shock absorbers. And spidron-based blocks might make an interesting toy. But mostly, he admits, they're just interesting for their own sake.
You can learn more about spidrons at www.spidron.hu.
Muse, February 2007, p. 26-27.
Daniel Erdély holds a complex polyhedron constructed from spidrons. Photo by Regina Márkus.
He called the resulting S-shaped object a spidron. Each of its two arms looks a bit like a seahorse's tail.
The two spiral arms of a spidron consist of alternating sequences of equilateral and isosceles triangles (above). Erdély.
How to Draw a Spidron's Arm (above): Start with a regular hexagon, which has six corners. Connect every send corner with a straight line to make a six-pointed star. Inside the star is a smaller hexagon. Again connect every second corner. Continue the process until the shape in the center is so small that you can't put in any more lines. The resulting pattern contains six identical copies of a spidron arm. Erdély.
Even though spidrons are irregularly shaped, they can fit together without gaps or overlaps to cover a plane (above). For example, you could tile your bathroom floor with this pattern of spidrons. Erdély, Marc Pelletier, Amina Buhler Allen, Walt van Ballegooijen.
When spidrons are laid down like tiles on a flat surface, then creased in just the right way at the line within each spidron arm, the flat structure can be forced to fold accordion-style into a wavy surface (above). As the folds get steeper, the whole pattern twists and compacts. Erdély, Marc Pelletier, Amina Buhler Allen, Walt van Ballegooijen.
Creased and folded spidrons can be assembled into three-dimensional balls (above). This one is made of 120 spidrons. Erdély, Marc Pelletier, Amina Buhler Allen, Walt van Ballegooijen.
Are spidrons good for anything besides artwork and maybe bathroom floors? Erdély says spidron surfaces could be used for collapsible solar panels or shock absorbers. And spidron-based blocks might make an interesting toy. But mostly, he admits, they're just interesting for their own sake.
You can learn more about spidrons at www.spidron.hu.
Muse, February 2007, p. 26-27.
July 4, 2007
The Power of 10
Nearly everyone has 10 fingers and 10 toes, and it's been like that for a long, long time. So, it's probably natural that we count by tensso natural that the decimal system is, by far, the most common way of expressing numbers in both spoken and written language around the world.
In ancient times, Pythagoras and his followers taught that "everything is number." They considered 10 to be special because it's the sum of the first four numbers, 1, 2, 3, and 4, and sets of 1, 2, 3, and 4 items can be arranged to form a triangle (like the pins in a bowling alley). To the Pythagoreans, this triangle was sacred, and they even swore oaths by it.
Ten objects (billiard balls) arranged to form a triangle (above).
However, 10 isn't quite so convenient when you have to measure out small amounts or take fractions of a whole. In the decimal system, it's easy to deal only with halves and tenths. But if you're slicing a pizza, halves, fourths, eighths, and sixteenths are much handier. That's what European merchants realized hundreds of years ago. Even though they used a number system based on 10 for counting and calculations, their systems of weights and measures often involved quarters, eighths, twelfths, twentieths, twenty-fourths, or sixtiethsanything but tenths. For example, there are 2 pints in a quart, 4 quarts in a gallon, 12 inches in a foot, 16 ounces in a pound, 24 hours in a day, and so on. Many people still use such measures today.
The English language shows traces of this past. Notice that the numbers from 1 to 12 all have distinctive names, though "eleven" is related to "one" and "two" to "twelve." It's only at 13 that the names for numbers begin to follow a standard, ten-based pattern: thirteen = three + ten.
So, just because we happen to have 10 fingers and 10 toes, we celebrate tens. If we had 12 fingers and 12 toes, we might have ended up with a number system based on 12. And for fraction fanatics, that would have been much tidier.
Muse, January 2007, p. 22.
In ancient times, Pythagoras and his followers taught that "everything is number." They considered 10 to be special because it's the sum of the first four numbers, 1, 2, 3, and 4, and sets of 1, 2, 3, and 4 items can be arranged to form a triangle (like the pins in a bowling alley). To the Pythagoreans, this triangle was sacred, and they even swore oaths by it.
Ten objects (billiard balls) arranged to form a triangle (above).
However, 10 isn't quite so convenient when you have to measure out small amounts or take fractions of a whole. In the decimal system, it's easy to deal only with halves and tenths. But if you're slicing a pizza, halves, fourths, eighths, and sixteenths are much handier. That's what European merchants realized hundreds of years ago. Even though they used a number system based on 10 for counting and calculations, their systems of weights and measures often involved quarters, eighths, twelfths, twentieths, twenty-fourths, or sixtiethsanything but tenths. For example, there are 2 pints in a quart, 4 quarts in a gallon, 12 inches in a foot, 16 ounces in a pound, 24 hours in a day, and so on. Many people still use such measures today.
The English language shows traces of this past. Notice that the numbers from 1 to 12 all have distinctive names, though "eleven" is related to "one" and "two" to "twelve." It's only at 13 that the names for numbers begin to follow a standard, ten-based pattern: thirteen = three + ten.
So, just because we happen to have 10 fingers and 10 toes, we celebrate tens. If we had 12 fingers and 12 toes, we might have ended up with a number system based on 12. And for fraction fanatics, that would have been much tidier.
Muse, January 2007, p. 22.
July 3, 2007
The Simpsons and Mathematics
Many people watch The Simpsons for its zany characters, political jokes, and outrageous situations. But other viewers keep a sharp eye out for references to mathematics. Really.
Several of the show's writers studied math or computer science in college. And, from time to time, they just can't resist sneaking in a mathematical bit or two (or three). But, unless you're looking carefully, these inside jokes can be easy to miss.
For example, during the final episode of the 20052006 season, which aired in May, an angry singing star tells her baseball-player husband that she will come back to him only if he can correctly guess the attendance of the day's ball game: 8128, 8191, or 8208? But these numbers aren't just any old numbers. Each one is mathematically special.
The first choice, 8128, is know as a perfect number. The smallest perfect number is 6. Its divisors are 1, 2, and 3. When you add up the divisors of a perfect number, you get the number itself: 1 + 2 + 3 = 6. This doesn't happen for most numbers; perfect numbers are rare. The second smallest perfect number is 28, the third is 496, and the fourth is 8128.
The second choice, 8191, is a prime number. In other words, it's evenly divisible only by itself and 1. In fact, it's a special type of prime known as a Mersenne prime. You get this number by multiplying 2 by itself 13 times, then subtracting 1. All Mersenne primes are prime-number powers of 2 minus 1.
The third choice, 8208, is a special four-digit number. If you multiply each digit by itself four times, then add up the results, you get the number (8 x 8 x 8 x 8) + (2 x 2 x 2 x 2) + (0 x 0 x 0 x 0) + (8 x 8 x 8 x 8) = 8208. It's one of only three four-digit numbers that can be written as the sum of the fourth powers of their digits. The others are 1634 and 9474.
Whew! You probably didn't catch any of that when you saw the show. But mathematicians Sarah J. Greenwald of Appalachian State University and Andrew Nestler of Santa Monica College have been keeping a careful watch, tracking the math in The Simpsons for years. Their Web site, simpsonsmath.com, lists math references episode-by-episode. In April 2006, the show even aired a program devoted entirely to mathwell, OK, and laughs, too. It was called "Girls Just Want to Have Sums."
Now you have yet another reasonone maybe even your teachers will endorseto watch all those Simpsons reruns.
For more about math in The Simpsons, see "Springfield Theory."
Muse, November/December 2006, p. 44.
Several of the show's writers studied math or computer science in college. And, from time to time, they just can't resist sneaking in a mathematical bit or two (or three). But, unless you're looking carefully, these inside jokes can be easy to miss.
For example, during the final episode of the 20052006 season, which aired in May, an angry singing star tells her baseball-player husband that she will come back to him only if he can correctly guess the attendance of the day's ball game: 8128, 8191, or 8208? But these numbers aren't just any old numbers. Each one is mathematically special.
The first choice, 8128, is know as a perfect number. The smallest perfect number is 6. Its divisors are 1, 2, and 3. When you add up the divisors of a perfect number, you get the number itself: 1 + 2 + 3 = 6. This doesn't happen for most numbers; perfect numbers are rare. The second smallest perfect number is 28, the third is 496, and the fourth is 8128.
The second choice, 8191, is a prime number. In other words, it's evenly divisible only by itself and 1. In fact, it's a special type of prime known as a Mersenne prime. You get this number by multiplying 2 by itself 13 times, then subtracting 1. All Mersenne primes are prime-number powers of 2 minus 1.
The third choice, 8208, is a special four-digit number. If you multiply each digit by itself four times, then add up the results, you get the number (8 x 8 x 8 x 8) + (2 x 2 x 2 x 2) + (0 x 0 x 0 x 0) + (8 x 8 x 8 x 8) = 8208. It's one of only three four-digit numbers that can be written as the sum of the fourth powers of their digits. The others are 1634 and 9474.
Whew! You probably didn't catch any of that when you saw the show. But mathematicians Sarah J. Greenwald of Appalachian State University and Andrew Nestler of Santa Monica College have been keeping a careful watch, tracking the math in The Simpsons for years. Their Web site, simpsonsmath.com, lists math references episode-by-episode. In April 2006, the show even aired a program devoted entirely to mathwell, OK, and laughs, too. It was called "Girls Just Want to Have Sums."
Now you have yet another reasonone maybe even your teachers will endorseto watch all those Simpsons reruns.
For more about math in The Simpsons, see "Springfield Theory."
Muse, November/December 2006, p. 44.
July 2, 2007
Upgrading
So it's already been a pretty tough school year? Some of your grades are OK, but others are quite dismal (especially that test you took the day after staying up way too late playing Guild Wars online)? Luckily, your teacher says you can drop a single test. Alright! But wait, which one?
The answer is easy if all of the tests are worth the same number of points. You simply drop the lowest score. But, if the tests are worth different numbers of points, dropping the lowest score isn't always the best strategy. Consider the following example.
On the first quiz, you score 80 out of 100 points, and get an 80 percent. On the second quiz, you score 20 out of 100: 20 percent. On the third quiz, you score 1 point out of 20: a miserable 5 percent. Without the option to drop one quiz, your final grade would be 101/220, or 46 percent. Ouch.
If you drop your lowest score (1 point out of 20), your final grade would be 100/200, or 50 percent. Ouch again. But, if you drop the score on the second quiz instead, your final grade would be 81/120, or 67.5 percent. Still not rocketing your way to the academic honors list, but, OK, you're passing.
In this case, it pays to work out all possibilities before deciding which grade to drop. Dropping your lowest score (or your lowest percentage) wouldn't guarantee that you'll end up with the best possible result.
It gets even trickier if you're allowed to drop two or more scores from your total. And if you're dealing with a lot of scores, it could take you a long time to calculate all the possibilities to find the result that helps you the most, and who wants that?
Math professor Jonathan Kane of the University of Wisconsin at Whitewater and his son Daniel, a student at the Massachusetts Institute of Technology and twice a member of the U.S. Mathematical Olympiad team, to the rescue. After the problem came up in conversation during a 10K run, they worked out a fancy formula that pinpoints the scores you should drop to get the best possible result, and created a computer program that allows your teacher to do these calculations quickly and easily.
AND, if you just mention casually that you're aware of their work, that will probably get you five bonus points.
Muse, October 2006, p. 33.
The answer is easy if all of the tests are worth the same number of points. You simply drop the lowest score. But, if the tests are worth different numbers of points, dropping the lowest score isn't always the best strategy. Consider the following example.
On the first quiz, you score 80 out of 100 points, and get an 80 percent. On the second quiz, you score 20 out of 100: 20 percent. On the third quiz, you score 1 point out of 20: a miserable 5 percent. Without the option to drop one quiz, your final grade would be 101/220, or 46 percent. Ouch.
If you drop your lowest score (1 point out of 20), your final grade would be 100/200, or 50 percent. Ouch again. But, if you drop the score on the second quiz instead, your final grade would be 81/120, or 67.5 percent. Still not rocketing your way to the academic honors list, but, OK, you're passing.
In this case, it pays to work out all possibilities before deciding which grade to drop. Dropping your lowest score (or your lowest percentage) wouldn't guarantee that you'll end up with the best possible result.
It gets even trickier if you're allowed to drop two or more scores from your total. And if you're dealing with a lot of scores, it could take you a long time to calculate all the possibilities to find the result that helps you the most, and who wants that?
Math professor Jonathan Kane of the University of Wisconsin at Whitewater and his son Daniel, a student at the Massachusetts Institute of Technology and twice a member of the U.S. Mathematical Olympiad team, to the rescue. After the problem came up in conversation during a 10K run, they worked out a fancy formula that pinpoints the scores you should drop to get the best possible result, and created a computer program that allows your teacher to do these calculations quickly and easily.
AND, if you just mention casually that you're aware of their work, that will probably get you five bonus points.
Muse, October 2006, p. 33.
July 1, 2007
Climbing a Watery Slope
Some insects can walk on water. They take advantage of water's high surface tension to skate across a pond or puddle. But at the edge of the pond, where wet meets dry, surface tension makes the water curve upward in a meniscus. For tiny, water-walking insects, scaling this slope isn't easy. If they try to stride up the slope, they simply slide back down.
So how do these insects get out of the pond? It turns out water-walking insects rely on special tricks to propel themselves upward. Surprisingly, these don't require them to move their legs back and forth in a walking motion at all, say mathematicians David Hu and John Bush of the Massachusetts Institute of Technology. The MIT mathematicians used high-speed video to capture the meniscus-climbing antics of several tiny insects.
As this water treader (above) approaches a meniscus, its front and rear legs deform the water's surface to help it move up the slope. Courtesy of Hu and Bush.
Some water treaders, for example, have retractable claws on their front and hind legs that allow them to pull up on the water to create tiny peaks. Each peak is itself a meniscus. And, because one meniscus is attracted to another, the slope tugs on the tiny peaks. Because the insect's front legs are closer to the slope that its rear legs, its front legs are tugged more strongly, and it is propelled forward and upward. In fact, the attraction is so strong, the insect may glide forward faster than 30 body lengths per second!
The larva of the waterlily leaf beetle uses an alternative strategy to scale a slippery meniscus. A poor swimmer, this creature simply arches its back, creating a meniscus at each end. The insect then gets pulled up the slope to a nice, juicy leaf. Courtesy of Hu and Bush
The same force is responsible for clumping breakfast cereal, such as Cheerios, in a bowl of milk (below). The meniscus created by a small floating object like a Cheerio attracts the meniscus produced by another nearby.
Don't lie: you've always wanted to know why the cereal ring formed in the bowl, haven't you?
Muse, September 2006, p. 28.
So how do these insects get out of the pond? It turns out water-walking insects rely on special tricks to propel themselves upward. Surprisingly, these don't require them to move their legs back and forth in a walking motion at all, say mathematicians David Hu and John Bush of the Massachusetts Institute of Technology. The MIT mathematicians used high-speed video to capture the meniscus-climbing antics of several tiny insects.
As this water treader (above) approaches a meniscus, its front and rear legs deform the water's surface to help it move up the slope. Courtesy of Hu and Bush.
Some water treaders, for example, have retractable claws on their front and hind legs that allow them to pull up on the water to create tiny peaks. Each peak is itself a meniscus. And, because one meniscus is attracted to another, the slope tugs on the tiny peaks. Because the insect's front legs are closer to the slope that its rear legs, its front legs are tugged more strongly, and it is propelled forward and upward. In fact, the attraction is so strong, the insect may glide forward faster than 30 body lengths per second!
The larva of the waterlily leaf beetle uses an alternative strategy to scale a slippery meniscus. A poor swimmer, this creature simply arches its back, creating a meniscus at each end. The insect then gets pulled up the slope to a nice, juicy leaf. Courtesy of Hu and Bush
The same force is responsible for clumping breakfast cereal, such as Cheerios, in a bowl of milk (below). The meniscus created by a small floating object like a Cheerio attracts the meniscus produced by another nearby.
Don't lie: you've always wanted to know why the cereal ring formed in the bowl, haven't you?
Muse, September 2006, p. 28.
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 longersome 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 gamefrom 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.
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 gamefrom 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 tokensone 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.
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 tokensone 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 stuffgames, puzzles, books, calculators, postersin 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 lifeand those CSI guys sure can figure out a lot from one "epithelial"!
Muse, April 2006, p. 43.
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 stuffgames, puzzles, books, calculators, postersin 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 lifeand 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.
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 youor 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.
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 youor 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 laughsuch 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.
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 laughsuch 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 revealingand fun.
Muse, November/December 2005, p. 22.
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 revealingand 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.
Answers:
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.
Answers:
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 kickand 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.
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 experimenteven 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.
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 experimenteven 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.
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.
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.
Topologistsmathematicians who study shapeshave 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 hoseif it's long enoughis quite likely to settle into a knot. There's no getting away from knotty situations!
Muse, March 2005, p. 29.
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.
Topologistsmathematicians who study shapeshave 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 hoseif it's long enoughis 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.
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
Advanced Floating
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.
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.
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).
The "pi" short story, called "Cadaeic Cadenza," is located at http://cadaeic.net/cadintro.htm (Mike Keith).
Muse, October 2004, p. 17.
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).
The "pi" short story, called "Cadaeic Cadenza," is located at http://cadaeic.net/cadintro.htm (Mike Keith).
Muse, October 2004, p. 17.
Subscribe to:
Posts (Atom)