Snow Day Hike

 

Dorothy Stewart Trail, Santa Fe, New Mexico, 2020.

Photo by I. Peterson

The Shoelace Problem

How should shoes be laced? This seemingly simple question, rooted in everyday life, can provoke passionate argument—and evoke a mathematical response.

There are at least three common ways to lace shoes, as illustrated below: American (or standard) zigzag, European straight, and quick-action shoe store. Which lacing style a person uses depends on a variety of factors, ranging from aesthetic appeal to tying efficiency.

Indeed, lacing patterns can be quite complex, and different patterns require different lengths of lace. For the sake of conserving fiber, one might wonder which lacing pattern requires the shortest laces.

That was the question tackled by computer scientist John H. Halton. The shoelace question represents a special, restricted instance of the classic traveling salesman problem, in which a salesman must visit customers in a number of cities scattered across the country and then return home following the shortest possible route visiting each city only once (see "The Traveling Monkey").

In the shoelace problem, you have to find the shortest path from the top eyelet (or lacehole) on one side to the top eyelet on the other side, passing through every eyelet just once. Having ventured into the realm of mathematical modeling, you can idealize the lace to be a mathematical line of zero thickness and the eyelets to be equally spaced points arranged in two columns.

It's then possible to calculate the length of lace in terms of the number n of pairs of eyelets, the distance d between successive eyelets, and the gap g between corresponding left and right eyelets.

Applying the Pythagorean theorem and a little algebra, you end up with the following lace lengths:

American: g + 2(n − 1)√(d² + g²)

European: (n − 1)g + 2√(d² + g²) + (n − 2) √(4d² + g²)

Shoe store: (n − 1)g + (n − 1) ✕ √(d² + g²) + √[(n − 1)2d² + g²]

It turns out that if n is at least 4, the shortest laces are always American, followed by European, then shoe store. For n = 3, American remains shortest, but European and shoe-store lacings are of equal length.

Instead of taking an algebraic approach, however, Halton used a shortcut inspired by the geometry of paths traced by rays of light. The trick is to think of the lacing pattern as the path of a light ray reflected back and forth between a pair of mirrors. You can imagine that every time the ray hits an eyelet position, it continues in its original direction through a virtual lattice of points created by reflecting the original lattice of pairs of points in the mirror (see "Mirror Bounces").

In effect, instead of zigzagging, the lacing path is reflected at each eyelet so that it is straightened out as much as possible. By plotting such paths on a rectangular lattice, it's easy to see that the American lacing is the straightest and, hence, the shortest.

Halton went to demonstrate that the American zigzag lacing is the shortest among all possible lacings. Michal Misiurewicz later proved that the eyelets don't necessarily have to be arranged in two parallel rows with equal distances between consecutive eyelets for that to be true. Even when the eyelets are irregularly arranged, the standard lacing is shorter than any other lacing.

It turns out, however, that shorter lacings are possible if the lace doesn't have to pass alternately through the eyelets on the left and right side of the shoe.

Here are some alternative lacings you could try. The first two work only if your shoes have an even number of eyelet pairs. Watch out, though. You might find that by saving shoelace length, you end up with shoes that slip off your feet more easily or laces that break more often.

Mathematician Burkard Polster later revisited the shoelace problem. He argued that the lacing that uses the least amount of lace is a rarely used and unexpected type that he described as a "bowtie" lacing.

Bowtie lacing.

In his model, Polster considered an arrangement of 2n eyelets, situated at the points of intersection of two vertical lines and n equally spaced horizontal lines. He specified that the shoelace visit all eyelets and that every eyelet contribute toward pulling the two sides of the shoe together. Polster then defined a "dense" lacing to be one that zigzags back and forth between the two columns of eyelets, as in the standard American lacing.

This model revealed that there are several other "reasonable" ways of lacing shoes. Of these, the bow-tie method is the most efficient in terms of requiring the shortest lace yet using all the eyelets. However, the two traditional "dense" styles win when you're looking for the strongest lacing—that is, the one that gives the maximum tension on both sides of the shoe.

Which of the two is stronger depends on the distance between the two rows of eyelets: zigzag when the eyelets are close together and straight when they are farther apart.

Hundreds of years of trial and error have led to the strongest—if not the most efficient—way of lacing our shoes, Polster concluded. That's in the face of a staggering 51,840 possible lacings for a shoe with just five eyelets on each side, and millions more for shoes with a larger number of eyelet pairs!

For the definitive guide to lacing, see Polster's book: The Shoelace Book: A Mathematical Guide to the Best (and Worst) Ways to Lace Your Shoes (AMS, 2006).

Originally posted December 23, 2002

Rug Symmetries

 

Romany rug, 2019.

Truel in the Sun

Brilliant sunshine bakes a huddled row of ramshackle, weather-beaten buildings lining a dusty thoroughfare. Two gunfighters slam out of a decrepit saloon and stalk toward their posts at either end of the street. Facing each other, they prepare to draw their six-shooters.

Abruptly, a third gunfighter steps out. The duel has turned into a truel: the good versus the bad versus the ugly. Who shoots at whom?

Game theory typically deals with the consequences of players' actions, given the rules of the game. Researchers seek to determine the optimal outcome in a particular situation.

In a truel, each of the participants fires bullets at the others to try to eliminate them and survive. Game theorists are interested in the nature and timing of each player's actions against his or her opponents.

Truels can arise in a variety of real-life situations, ranging from fierce rivalry among animals living in close proximity to competition among major television networks. Such three-party conflicts are also often played out in the arena of international politics.

In the December 1997 Mathematics Magazine, D. Marc Kilgour and Steven J. Brams, in their article "The Truel," provided a detailed look at truels, highlighting how small changes in the rules can lead to startlingly different, sometimes counterintuitive outcomes.

Here's a typical decision problem involving a truel. It concerns a three-cornered gunfight among Arnold, Bert, and Charlie. Everyone knows that Arnold's probability of hitting his target is .3, Charlie's is .5, and Bert never misses. The truelists must fire at their choice of target in succession, in the cyclical order Arnold, Bert, and Charlie, until only one man is left. What should Arnold's strategy be?

To study target selection, one can think of the three players as standing at the corners of an equilateral triangle. Each player shoots at an opponent at one of the other two corners. Several firing rules are possible: sequential in fixed order (players fire one at a time in a fixed, repeating sequence, as in the sample problem), sequential in random order (the first player to fire and each subsequent player is chosen at random from among the survivors), or simultaneous (all surviving players fire at the same time in every round).

In certain truels, a participant is allowed to shoot in the air rather than to try to eliminate an opponent. That would be the optimal strategy if the firing order is fixed and each player has only one bullet and is a perfect shot. If the first shooter misses intentionally, he eliminates himself as a threat, and the other two fight it out, leaving two survivors in the end. Any other course of action would lead to the first shooter's own demise, with only one survivor.

"Even if the players have an unlimited supply of bullets, the truel may still terminate with more than one survivor because no player wants to be the first to fire," Kilgour and Brams noted. Indeed, under the fixed firing order rule, no player has an incentive to eliminate another player. Only in the case of simultaneous firing is there a chance that nobody survives.

Most of the mathematical research on truels concerns the relationship between a player's marksmanship (probability of hitting a target) and his or her survival probability. It's possible to show, for example, that better marksmanship can actually hurt in many situations.

In a sequential truel in which participants are not allowed to shoot in the air, a player maximizes his survival probability by firing at the opponent against whom he would less prefer to fight in a duel—regardless of what the other players do. If his shot misses, it makes no difference who the target was. If the shot hits the target, the shooter is better off because his opponent in the next duel is weaker. Thus, the first shooter fires at the opponent whose marksmanship is higher.

In general, depending on the marksmanship values, the survival probabilities of the truelists could end up in any order, including one that is the reverse order of shooting skill.

Kilgour and Brams examined a wide variety of scenarios, including situations that involve pacts, unlimited amounts of ammunition, different firing orders, and limits on the number of rounds.

"Optimal play can be very sensitive to slight changes in the rules, such as the number of rounds of play allowed," Kilgour and Brams concluded. "At the same time, some findings for truels are quite robust: the weakness of being the best marksman, the fragility of pacts, the possibility that unlimited supplies of ammunition may stabilize rather than undermine cooperation, and the deterrent effect of an indefinite number of rounds of play (which can prevent players from trying to get the last shot)."

"Some of these findings are counterintuitive, even paradoxical," they continued. "An understanding of them, we believe, might well dampen the desire of aggressive players to score quick but temporary wins, rendering them more cautious. In particular, contemplating the consequences of a long and drawn-out conflict, truelists may come to realize that their own actions, while immediately beneficial, may trigger forces that ultimately lead to their own destruction."

Originally posted January 26, 1998

Granite Chief

 

Lake Tahoe, California, 1996.

Westport

Westport, Ontario, 1992.

Photo by I. Peterson

Geometry out of Latvia and Africa

Both of my parents were born and grew up in the tiny Baltic country of Latvia. I remember, as a young child in northern Ontario, intently watching my father painstakingly color in tiny squares of a grid to create a symmetric design. Using yarn and needle, my mother would then transfer that geometric pattern to cloth, creating a wall hanging, a pillow cover, or some other decorative article.

Example of Latvian needlework featuring a geometric design.

Geometric patterns with a high degree of symmetry are characteristic of much of traditional Latvian folk art (see also Latvian Folk Art Museum and Latvian Needlework).

Latvian weaving (above) and vase (below) with highly symmetric designs.

See "The Investigation of the geometry and composition of Latvian folk art designs" by Silvija Kukle and colleagues.

Examples of traditional Latvian silver (and amber) jewelry, including Namejs rings and bracelets.

I have long been intrigued by the geometric designs created by various cultures, both past and present, throughout the world. I'm impressed by the variety of such patterns.

At the same time, there are wonderful similarities among designs in different parts of the world, even when there's no evidence of direct contact between the groups. That's a consequence of the underlying mathematics. Given a set of rules, there are many instances in which the number of possibilities is finite. The five regular polyhedra (Platonic solids) and the 17 wallpaper symmetries are good examples.

My introduction to geometry in African folk art came with the beautifully illustrated book Geometry from Africa: Mathematical and Educational Explorations by mathematician and educator Paulus Gerdes. He provided a fascinating guided tour of geometric ideas encoded in carved patterns, woven designs, sand drawings, and other products created by people south of the Sahara.

"The development of geometrical thinking starts early in African history," Gerdes noted in the first chapter. He described a variety of geometrically decorated artifacts, from rock paintings and engravings to decorated pots and textiles, some of which are more than 2,000 years old.

Symmetry is a prominent trait of many of these patterns. Textiles woven by the Tellem people in an area that is now in the Republic of Mali, for example, feature intricate combinations of white and indigo cotton threads to produce symmetric strip and planar patterns of various types.

Example of a Tellem textile pattern.

Geometrical knowledge also played a crucial role in the shaping of articles of clothing, such as tunics, from the woven material, Gerdes said. A Tellem tailor would work with several different kinds of knots and stitches, for instance.

In succeeding chapters, Gerdes showed how you can discover or derive the Pythagorean theorem from African designs, explored the role of symmetry (with suggestions for home and classroom crafts projects), and focused on the geometry of the sona sand drawings among the Chokwe people in south-central Africa.

Example of a sona sand drawing.

The sand drawing above illustrates a fable: Sambálu, the rabbit (positioned at point B, lower right), discovers a salt mine (point A, center). Immediately, the lion (point C, upper left), the jaguar (point D, upper right), and the hyena (point E, lower right) demand possession, asserting the rights of the strong. The rabbit, affirming the inviolable rights of the weak, then quickly makes a fence to isolate the mine from all usurpers. Note that only from B can you go to point A, without going beyond the line that represents the fence.

To many people, African geometry remains an unknown, rarely glimpsed realm. This book helped dispel some of the mystery, revealing a rich tapestry of geometric designs and concepts.

Originally posted November 29, 1999

Aspen Gold

 

Aspen Vista trail, Santa Fe National Forest, New Mexico, 2020.

Photos by I. Peterson

Moebius Scarf

Möbius Scarf by Cliff Stoll.

A Möbius strip is a one-sided, one-edged surface. You can make one by giving a strip of paper a half-twist, then taping the ends together. The scarf is knitted so that it forms a loop with one continuous surface.

See also "Immersed in Klein Bottles" and "Folding a Klein Bottle."

Icosahedral Slices

1,2 Icosahedron by Steve Morse.

The icosahedron is one of the five Platonic solids. Its twenty faces are equilateral triangles, with five meeting at each corner. In the model above, each face is further divided into six congruent 30-60-90 triangles, for a total of 120 triangles. The model is constructed from 15 slotted rings lying in 15 planes.

Photos by I. Peterson

Purse of Fortunatus

Fortunatus X by Susan Goldstine.

According to legend, the purse of Fortunatus continually replenished itself as coins were withdrawn from it.

A story by Lewis Carroll (Charles L. Dodgson) describes how to make such a purse from four handkerchiefs. The resulting form is a model of a topological structure known as the projective plane.

A projective plane can be constructed by gluing both pairs of opposite edges of a rectangle together giving both pairs a half-twist. It is a one-sided surface, but cannot be realized in three-dimensional space without crossing itself.

Creating a model of Fortunatus's Purse presents an interesting challenge for both artisans and mathematicians.

Photos by I. Peterson

Medieval Harmony

Philippe de Vitry (1291-1361) was one of the most prominent figures in medieval music. He was the author of an important music theory text, Ars Nova, which introduced new rhythmic schemes and musical notation. He had a deep knowledge of philosophy, rhetoric, and mathematics.

In many ways, de Vitry's interests and accomplishments reflected the Pythagorean view that music is a subdivision of arithmetic, as shown, for example, in the simple mathematical relations between pitch and length of a string (see Circles of Dissonance). His work honored the dictum of the Roman philosopher Boethius (480-524) that "music is number made audible."

One of de Vitry's observations concerned numbers that can be written as a power of 2 multiplied by a power of 3. In modern terms, such numbers would be expressed as 2ⁿ x 3^m, where n and m are integers. He called them harmonic numbers.

Here's a table of all harmonic numbers less than 1000.

De Vitry focused on pairs of harmonic numbers that differ by 1: 1, 2; 2, 3; 3, 4; and 8, 9. As it happens, those particular pairs correspond to musically significant ratios, representing an octave, fifth, fourth, and whole tone. He wondered whether there are any other such pairs of harmonic numbers.

In 1342, Levi ben Gerson, also known as Gersonides (1288-1344), proved that the original four pairs of harmonic numbers are the only ones that differ by 1. Here's how his proof went (using modern notation).

If two harmonic numbers differ by 1, one must be odd and the other even. The only odd numbers are powers of 3 (top row of chart, above). Hence, one of the two harmonic numbers must be a power of 3 and the other a power of 2 (first row and first column of chart). The basic task then involves solving two equations:

2ⁿ = 3^m + 1 and 2ⁿ = 3^m − 1.

Gersonides had the idea of looking at remainders after division of powers of 3 by 8 and powers of 2 by 8. For example, 27 divided by 8 gives a remainder of 3. For powers of 3, the remainders all turn out to be 1 or 3, depending on whether the power is even or odd. The remainders for powers of 2 are 1, 2, 4, then 0 for all powers higher than 2.

For 2ⁿ = 3^m + 1, when m is odd, 3^m has remainder 3, and 2ⁿ = 3^m + 1 must then have the remainder 4, so n = 2 and m = 1. That gives the consecutive harmonic numbers 3, 4. When m is odd, the equation gives the consecutive harmonic numbers 1, 2.

For 2ⁿ = 3^m − 1, when m is odd, 3^m has remainder 3, so 2ⁿ = 3^m − 1 has remainder 2; as a result, n = 1 and m = 1, to give the consecutive harmonic numbers 2, 3.

The final case, when m is even, is a little trickier and requires substituting 2k for m, then solving the equation 2ⁿ = 3^2k − 1 = (3^k − 1)(3^k + 1). That gives the consecutive harmonic numbers 8, 9. QED.

Interestingly, the theorem about harmonic numbers proved by Gersonides has connections with Fermat's last theorem and with the abc conjecture, a topic of some interest among number theorists.

 

Originally posted January 25, 1999

Moebius Accordion

In 2001, artist Susan Happersett came up with a novel twist on the venerable Möbius strip: a playful, eye-catching creation she described as a Möbius accordion.

The Happersett Accordion by Susan Happersett.

A Möbius strip, or band, is the remarkable one-sided surface that results from joining together the two ends of a long strip of paper after twisting one end 180 degrees. Mathematicians, magicians, artists, and many others have been playing with this intriguing object since its discovery in the 19th century by August Ferdinand Möbius (1790-1868), a professor at the University of Leipzig in Germany.

Happersett combines her interest in mathematics with a passion for visual art. In the 1980s, as an undergraduate working toward a degree in mathematics at Drew University, she found herself particularly intrigued by courses on symbolic logic and infinity. She also enjoyed an art course that involved going to New York City to visit galleries, museums, and artist's studios.

"I had always felt there were aspects of mathematics that possessed natural grace and beauty," Happersett said. "I could not understand when people told me they disliked mathematics. I became determined to find a visual way to express the intrinsic aesthetics of mathematics."

To learn the practical side of creating art, Happersett next went to Montclair State University. While earning a graduate degree in fine arts, she spent a lot of time working with grids, exploring different ways of dividing up surface areas, then plotting various functions, sequences, and series. "These graphs allowed me to study the aesthetic characteristics of functions, sequences, and series in a purely visual language," Happersett said.

Happersett followed up her art education with more mathematics, taking courses in logic at Hunter College, where she earned a master's degree in mathematics in 1993. She worked as a high school mathematics teacher until 1995.

While attending Hunter, Happersett started playing with the idea of creating her own visual language based on markings drawn in the boxes of a surface-spanning grid. "In this mathematical language, it is the number of strokes per grid space that holds significance," she says. "The placement of the strokes is random."

For several of her artworks, Happersett used the Fibonacci sequence of whole numbers to determine the number of strokes per box. In the Fibonacci sequence, each new term is the sum of the previous two terms: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, and so on.

Fibonacci numbers come up surprisingly often in nature. Many flowers, for example, have three, five, or eight petals. Pineapples and pine cones have rows of diamond-shaped scales, which spiral around both clockwise and counterclockwise. If you count the number of spirals, you are likely to find 8, 13, or 21.

Happersett's set of beautifully printed, accordion-folded artbooks, Box of Growth, features grid spaces that are filled in with a specific number of strokes per row, where the number is determined by the Fibonacci sequence.

"Creating these patterns has become a type of meditation," Happersett noted. "Quite often I will make a series of drawings that are based on the evolution of a particular growth pattern. These completed drawings then work together as a book or a wall installation."

In 2000, Happersett created several artworks that were displayed at a New York City artbooks show called "Fireworks." In one, she filled in the grid of squares on a strip of stiff paper, 22 inches long and 2.5 inches wide, with 13 strokes per box, using blue ink on one side and red on the other. She then creased the strip into accordion folds and glued the ends together to form a Möbius strip. Happersett named the result Thirteen Original Colonies.

Thirteen Original Colonies by Susan Happersett. 

Happersett's Möbius accordion features black and white markings on a brown strip, with 13 markings, or strokes, per box. "I chose 13 because of the superstition regarding that number and the mysterious illusion created by the two faces—black and white—of the accordion," Happersett said. "Also, 13 is a Fibonacci number, so I could not resist."

The Happersett Accordion by Susan Happersett.

Intricately printed copies of The Happersett Accordion are available from Purgatory Pie Press in New York City. Each unfolded copy comes with a droll certificate of authenticity, along with assembly instructions and the mandatory warning that the product is a mind-boggling "Möbius device."

Happersett's approach to mathematical art focuses on algorithms. She makes the rules, then sees what happens. "By creating algorithmically generated drawings, I hope to reveal the grace and balance that I see in mathematics," Happersett said.

Originally posted June 11, 2001

See also "Möbius and His Band" and "Nature's Numbers."

Pierre Elliott Trudeau (1919-2000)

Prime Minister Pierre Elliott Trudeau (1919-2000) (with Marion McGaw), Liberal Party of Canada reception, Ottawa, Ontario, 1970.

Photo by I. Peterson

Pierre Trudeau autograph, Toronto, Ontario, 1970.

Alpha 'n' Beta I

 

A Magic Knight's Tour

For as long as the game of chess has existed, there have been puzzles involving chessboards and chess pieces. Some of the most enduring conundrums have involved knights.

According to the rules of chess, a knight makes an L-shaped move that shifts its position by a single square in one direction and two squares in a perpendicular direction. Indeed, the knight is the only chess piece that covers an asymmetrical pattern of squares.

One of the most venerable of chess puzzles is that of the knight's tour: Following the rules of chess, is it possible for a knight to tour a chessboard in such a way that it visits each square of the board exactly once?

Such problems intrigued Leonhard Euler (1707–1783), and he spent some time working on this puzzle and its generalization to boards of different sizes and shapes. Many others have followed in his footsteps.

It turns out there's a huge number of different knight's tours of a standard chessboard. In some cases, the knight ends up just a knight's move away from its initial starting position.

If the successive squares that a knight visits are numbered from 1 to 64, in order, and the numbers form a magic square, the path is called a magic tour. A magic square is a square array of numbers such that each row and column and the two main diagonals sum to the same number (the magic constant).

Knight's tours in which the rows and columns sum to the same number but the diagonals do not are known.

Example of a knight's tour in which the rows and columns have the same sum (260), but the diagonals add up to 348 and 168.

The question remains: Are there are any fully magic knight's tours of the standard chessboard?

No one was sure of the answer until 2002, when a team used computers to check all the relevant possibilities and concluded that there are no magic knight's tours on an eight-by-eight chessboard (see "Computing Magic Knight Tours"). The team did find a total of 140 distinct "semimagic" tours in which just the rows and columns have the same sum.

Interestingly, magic knight's tours are not possible on n x n boards, when n is odd. They are possible for all boards of size 4k x 4k, for k greater than 2.

Chess pieces and chessboards lend themselves to all sorts of puzzles and mathematical investigations. A while ago, for example, there was a flurry of attention paid to knight coverings for large chessboards. The problem was how to cover a chessboard with the smallest number of knights so that every square on the board is either occupied by a knight or attacked by a knight.

For this puzzle, the optimal solutions for boards of sizes 3 x 3 to 10 x 10, along with 12 x 12 and 13 x 13, have been known since the 19th century. The best solution for 11 x 11 was found in 1973 and the best one for 14 x 14 in 1977. In 2000, Frank Rubin found good solutions for boards as large as 26 x 26.

And there's much more, especially involving knights and standard chessboards.

"Mathematically, the choice of (2,1) and of the 8 x 8 board may seem to be a special case of no particular interest," Noam D. Elkies and Richard P. Stanley wrote in their article "The Mathematical Knight" in the Mathematical Intelligencer. "But long experience points to the standard knight's move and chessboard size as felicitous choices not only for the game of chess but also for puzzles and problems involving the board and pieces."

Originally posted October 6, 2003

See also "Knight Moves in 3D."

Geometry in Court

The TV series Numb3rs highlighted how mathematics can play a role in solving crimes.

Even though the episodes were sometimes rather fanciful, they still illustrated ways in which various types of math can help illuminate mysteries, confirm conjectures, and point to villains.

In real life, math can also be relevant in the courtroom or come up in legal disputes.

In 2005, the Pythagorean theorem was a deciding factor in a case before the New York State Court of Appeals. A man named James Robbins was convicted of selling drugs within 1,000 feet of a school. In the appeal, his lawyers argued that Robbins wasn't actually within the required distance when caught and so should not get the stiffer penalty that school proximity calls for.

The arrest occurred on the corner of Eighth Avenue and 40th Street in Manhattan. The nearest school, Holy Cross, is on 43rd Street between Eighth and Ninth Avenues.

Law enforcement officials applied the Pythagorean theorem to calculate the straight-line distance between the two points. They measured the distance up Eighth Avenue (764 feet) and the distance to the church along 43rd Street (490 feet), using the data to find the length of the hypotenuse, 907.63 feet.

Robbins' lawyers contended that the school is more than 1,000 feet away from the arrest site because the shortest (as the crow flies) route is blocked by buildings. They said the distance should be measured as a person would walk the route.

However, the seven-member Court of Appeals unanimously upheld the conviction, asserting that the distance in such cases should be measured "as the crow flies."

"Plainly, guilt under the statute cannot depend on whether a particular building in a person's path to a school happens to be open to the public or locked at the time of a drug sale," Chief Justice Judith S. Kaye wrote in the opinion, as reported in the Nov. 23, 2005, New York Times.

Originally posted November 27, 2006

Morning Hike

Black Canyon trail, Santa Fe National Forest, New Mexico, 2020.

Photo by N. Henderson

Mastering Mastermind

Games offer wonderful playing fields for developing mathematical problem-solving skills.

For educator Mathew Mitchell, the preferred training ground is a classic game called Mastermind. "Students young and old are fascinated by simple yet challenging games," he wrote in his book Mastermind Mathematics: Logic, Strategies, and Proofs.

Mastermind involves hypothesis testing and deductive reasoning, Mitchell noted. It is also an activity that many people of a wide range of ages find highly enjoyable.

In Mastermind, a codemaker secretly selects a sequence of four colors, typically represented by colored pegs. The codemaker can use any combination of colors picked from the six different colors that are available, including two or more of the same color.

A player's goal is to determine the codemaker's hidden sequence, making as few guesses as possible. With each guess, the player displays a sequence of four colored pegs, and the codemaker indicates how many of those pegs are the correct color and in the right position and how many more are the correct color but in the wrong position.

Suppose the pegs are red (R), blue (B), yellow (Y), green (G), white (W), and orange (O).

Codemaker's secret sequence: R W B G

Player's first guess: W Y B O

In this example, the codemaker would indicate that the player has one peg of the right color in the right position and one peg of the right color in the wrong position but would give no clue that the blue peg (B) and the white peg (W) are the relevant choices.

With six colors and four positions, a codemaker can select from 6⁴ (or 1,296) possible combinations. One useful beginning strategy for a player is to find the colors first, then determine the correct positions. By focusing initially on color, you have only 126 possible groupings to consider. Once you have the colors, you need look at no more than 24 possible arrangements of that set of colors.

Once in a while, however, you might find that you need to know one or two positions before you can work out all the colors. "This brings up an important point about strategies," Mitchell remarked. "They do not always work."

Here's one example where position information helps you out. 

Game 1

Guess 1: W R O O 

Three pegs are the right color and in the right position.
Guess 2: W B B B

One peg is the right color but is in the wrong position.

Foundation strategies such as pursuing subgoals (such as colors first, then positions), making charts, using deductive reasoning, and eliminating possibilities can serve as powerful tools for quickly working out Mastermind codes. Try solving this one.

Game 2

Guess 1: G B B B

One peg is the right color and in the right position.
Guess 2: O B W W

Nothing is correct.

Guess 3: Y R Y R
One peg is the right color and in the right position; one more is the right color.

Guess 4: Y B Y Y

One peg is the right color but in the wrong position.

Guess 5: O B O R

One peg is the right color and in the right position. You should now have enough clues to solve the puzzle.

Mitchell also presented a number of strategies applicable specifically to Mastermind. "You can glean a great deal of information from patterns," he asserted. Certain peg positions and color combinations often offer important clues.

Spotting particular game patterns can help you solve codes. Consider the following pair of guesses.

Guess 1: B O R G

Two pegs are the right color.

Guess 2: B O R W

Three pegs are the right color.

The only difference between the rows is the color in the fourth position. Yet, according to the feedback from the codemaker, a third peg now has the right color. From that change, you can readily deduce that W is the correct color and G is incorrect.

In general, Mitchell noted, if two rows differ by only one color and the number of feedback pegs changes from one row to the next, then it must be the one changed color that caused the increase (or decrease) in response.

Try out your pattern-searching strategies on the following game.

Game 3

Guess 1: G B R B

One peg is the right color but in the wrong position.

Guess 2: B G B Y

One peg is the right color and in the right position; one more is the right color.

Guess 3: R Y B R

One peg is the right color but in the wrong position.

Guess 4: O W G Y

One peg is the right color and in the right position; two more are the right color.

Guess 5: O G Y O

Three pegs are the right color and in the right position.

There's much more in Mitchell's book, all the way up to formal proofs. Indeed, it's amazing how much mathematical activity you can get out of playing Mastermind over and over again. And if the standard version isn't challenging enough, you can always increase the number of colors and the number of slots.

One more thing. The book's many sample game situations give you something to work on when no one happens to be around to set the secret codes for you. Or you can try an online version of Mastermind.

Originally posted October 11, 1999

ANSWERS

Game 1: B R O O

Game 2: G Y G R

Game 3: O G Y G

Absolutely Abnormal

Identifying the normal (or even the abnormal) in mathematics can pose serious difficulties.

In 1909, mathematician Émile Borel (1871-1956) introduced the concept of normality as one way to characterize the resemblance between the digits of a mathematical constant such as pi (the ratio of a circle's circumference to its diameter) and a sequence of random numbers.

Émile Borel. MAA Convergence Photo Gallery.

If a number is normal, digit sequences of the same length occur with the same frequency. A constant would be considered normal to base 10 if any single digit in its decimal expansion appears one-tenth of the time, any two-digit combination one-hundredth of the time, any three-digit combination one-thousandth of the time, and so on.

In the case of pi, you would expect the digit 7 to appear 1 million times among the first 10 million decimal digits of pi. It actually occurs 1,000,207 times—close to the expected value. Each of the other digits also turns up with approximately the same frequency, showing no significant departure from predictions. (See "Is Pi Normal?" by Stan Wagon.)

A number is said to be "absolutely normal" if its digits are normal not only to base 10 but also to every integer base greater than or equal to 2. In base 2, for example, the digits 1 and 0 would appear equally often.

Borel established that there are lots of normal numbers. Finding a specific example of a normal number, however, proved much more difficult.

In 1933, D.G. Champernowne showed that the carefully constructed number 0.12345678910111213…, created by writing all the positive integers in a row as a single decimal, is normal to base 10. You can construct analogous normal numbers for other bases.

At the same time, although it is known that almost all real numbers are absolutely normal, no one has yet proved even a single, "naturally occurring" real number to be absolutely normal.

Mathematician Greg Martin turned his attention to the opposite extreme—real numbers that are normal to no base whatsoever. He described his successful search for such an "absolutely abnormal" number in the October 2001 American Mathematical Monthly.

To start with, every rational number is absolutely abnormal. For example, the fraction 1/7 can be written in decimal form as 0.1428571428571…. The digits 142857 just repeat themselves. Indeed, an expansion of a rational number to any base b or b^k eventually repeats. Hence, a rational number "is about as far from being simply normal to the base b^k as it can be," Martin remarked.

Martin focused on constructing a specific irrational absolutely abnormal number. He nominated the following candidate, expressed in decimal form, for the honor:

α = 0.6562499999956991999999…9999998528404201690728…

The middle portion (shown in bold) of the given fragment of α consists of 23,747,291,559 9's.

Martin's formulation of this number and proof of its absolute abnormality involved so-called Liouville numbers, named for Joseph Liouville (1809-1882).

One example of a Liouville number is 0.1100010000000000000000010000…, where there is a 1 in place 1, 2, 6, 24,…, n! and 0 elsewhere. Liouville had introduced such numbers as examples of transcendental numbers—real numbers that are not roots of polynomial equations with integer coefficients.

The construction that he found, Martin concluded, "easily generalizes to a construction giving uncountably many absolutely abnormal numbers."

Originally posted November 5, 2001

Probabilities in Bingo

One of the little pleasures of our annual winter vacation is an evening Bingo party. After a day of sledding and cross-country skiing, it's relaxing to indulge in a social game that requires minimal thought, affords young and old the same chance of winning, and has a strong element of suspense.

To play Bingo, each player has one or more cards divided into squares. Each card has five rows and five columns. The columns are labeled from left to right with the letters "B," "I," "N," "G," and "O." The center square is designated "free." The five squares in column B contain different numbers selected from the interval 1 to 15. Column I contains five numbers from the interval 16 to 30. Column N contains four numbers from the interval 31 to 45. Column G contains five numbers from the interval 46 to 60, and column O contains five numbers from the interval 61 to 75.

An announcer randomly selects numbers from 1 to 75, calling out each one while players mark the appropriate grid square if that number appears on their cards. In standard Bingo, the player's goal is to be the first to mark an entire row, column, or diagonal. There are 12 winning configurations. Eight of these configurations do not involve the use of the center "free" space, and four (column N, row 3, and the diagonals) do.

What makes the game suspenseful is the tantalizing uncertainty about when someone will achieve a Bingo. It's natural to wonder how long a typical game would last. More precisely, what is the average number of calls required to complete a game for a given number of players?

"The analysis turns out to be straightforward, but obtaining the numerical results would be tedious without a computer," David B. Agard and Michael W. Shackleford noted in their 2002 article on bingo probabilities in the College Mathematics Journal.

In presenting their data, Agard and Shackleford also remarked that some care must be taken in doing the analysis. Several previous efforts had failed to take into account the fact that "the events representing completion of the 12 possible Bingos are neither independent nor mutually exclusive," they pointed out.

One crucial tabulation involves determining the number of subsets of the 12 possible Bingos of a particular size that cover a particular number of squares. For example, four covered squares can produce one Bingo in four different ways, and five covered squares can produce one Bingo in eight different ways.

Overall, there is approximately a 50 percent chance that one card will require at most 41 calls to complete a Bingo, and approximately a 90 percent chance to complete a Bingo in at most 54 calls, the researchers concluded.

However, a typical game involves many more than one card. Because the assumption of independence does not hold for different Bingo cards, the analysis is much more complicated. Agard and Shackleford turned to computer simulation to find the probability distribution for the number of calls to achieve the first Bingo in a game played with m randomly generated cards.

"For a game involving 100 cards, there is virtually no chance it will take more than thirty numbers to produce a Bingo," the researchers reported. "For even a small game of ten cards it is a near certainty to have produced a Bingo by the fiftieth number called."

These odds apply only to the standard version of Bingo. Other variants also occur—X-out, four corners, postage stamp, blackout—and have their own probability distributions. Shackleford also worked out the cumulative probability distributions for the number of calls to complete these types of Bingos. See also "Durango Bill's Bingo Probabilities."

Indeed, with Bingo a common pastime in gambling casinos and elsewhere, it can be a serious business.

Originally posted August 26, 2002

Testing for Divisibility

The crisp new dollar bill that I have just taken from my wallet bears the serial number 24598176. It's easy to tell that the number is exactly divisible by 2 but not by 5. Is it divisible by 3? by 4? by 11?

 
In a 1962 Scientific American article, Martin Gardner noted that during the 15th and 16th centuries in Renaissance Europe, the rules for checking whether one number is divisible by another without a remainder were widely known, particularly because of their usefulness in reducing large-number fractions to their lowest terms.

The advent of decimal arithmetic reduced the need for such tests. "Few people, including many mathematicians, know all the simple rules by which large numbers can be tested quickly for divisibility by numbers 1 through 12," Gardner remarked.

More recently, Eli Maor observed in an article on divisibility that, at one of his presentations, none of the teachers present appeared to know the quick divisibility test for 11.

Nowadays, in a world where calculators are ubiquitous, divisibility rules may seem little more than quaint relics of a distant past. Nonetheless, they can be handy for solving digital puzzles, reducing fractions, and as targets for algorithm development.

Here's a set of rules for numbers from 2 to 12.

2 A number is divisible by 2 if and only if its last digit is even (ending in 0, 2, 4, 6, and 8).

For example, because the final digit 6 is an even number, 24598176 is divisible by 2.

3 Sum the digits. If the result is more than one digit, sum again and continue until one digit remains. If the final digit (called the digital root of the number) is a multiple of 3 (3, 6, or 9), the number is divisible by 3. This also means that you can scramble the digits of any multiple of 3 and still have a number that is a multiple of 3.

For example, 2 + 4 + 5 + 9 + 8 + 1 + 7 + 6 = 42; 4 + 2 = 6. Because the digital root of 24598176 is 6, which is divisible by 3, the original number must be divisible by 3.

4 A number is divisible by 4 if and only if the number represented by the last two digits is a multiple of 4.

Because 76 is divisible by 4, 24598176 is divisible by 4.

5 A number is divisible by 5 if and only if its last digit is 0 or 5.

6 A number is divisible by 6 if and only if it is divisible by both 2 and 3 (that is, it's an even number divisible by 3).

The number 24598176 is divisible by both 2 and 3, so it must be divisible by 6.

7 Multiply the last digit of the number by 2. Subtract that product from the number obtained by deleting the last digit of the original number. Repeat the two steps as necessary. The original number is divisible by 7 if and only if the resulting number is divisible by 7.

For example, 6 ✕ 2 = 12; 2459817 − 12 = 2459805; 5 ✕ 2 = 10; 245980 − 10 = 245970; 0 ✕ 2 = 0; 24597 − 0 = 24597; 7 ✕ 2 = 14; 2459 − 14 = 2445; 5 ✕ 2 = 10; 244 − 10 = 234; 4 ✕ 2 = 8; 23 − 8 = 15. Because 15 is not divisible by 7, neither is 24598176.

8 A number is divisible by 8 if the number represented by its last three digits is a multiple of 8.

Because 176 is divisible by 8, 24598176 is divisible by 8.

9 A number is divisible by 9 if and only if it has a digital root of 9.

For example, because the digital root of 24598176 is 6 (see 3, above), the number is not divisible by 9.

10 A number is divisible by 10 if and only if it ends in 0.

11 Take the digits from right to left, alternately subtracting and adding. The original number is divisible by 11 if and only if the resulting number is divisible by 11. (Assume that 0 is divisible by 11.)

For example, 6 − 7 + 1 − 8 + 9 − 5 + 4 − 2 = −2. Because −2 is not divisible by 11, 24598176 is not divisible by 11.

12 A number is divisible by 12 if and only if it is divisible by both 3 and 4.

The number 24598176 is divisible by both 3 and 4, so it must be divisible by 12.

In the case of 7, the rule is sufficiently complicated that it takes nearly as much effort to check for divisibility as it would take to perform the division operation itself. Indeed, dozens of algorithms for testing for 7 have been devised over the years, but none of them represents a significant time-saver.

In the 2002 article "Divisibility: A Problem Solving Approach Through Generalizing and Specializing," Rina Zazkis described a student investigation of how one algorithm for testing for 7 (the one mentioned above) could be generalized to other prime numbers.

Surprisingly, the same algorithm can be applied to determine divisibility by 3. For 24598176, the resulting number is 15 (see 7, above), which is divisible by 3.

Variants of this recipe, which Zazkis described as a "trimming" algorithm, work for other prime numbers.

19 Multiply the last digit of the number by 2. Add that product to the number obtained by deleting the last digit of the original number. Repeat the two steps as necessary. The original number is divisible by 19 if and only if the resulting number is divisible by 19.

For example, 6 ✕ 2 = 12; 2459817 + 12 = 2459829; 9 ✕ 2 = 18; 245982 + 18 = 246000; 0 ✕ 2 = 0; 24600 + 0 = 24600; 0 ✕ 2 = 0; 2460 + 0 = 2460; 0 ✕ 2 = 0; 246 + 0 = 246; 6 ✕ 2 = 12; 24 + 12 = 36. Because 36 is not divisible by 19; the original number is not divisible by 19.

It's possible to devise a divisibility rule based on some sort of trimming algorithm for any prime, p, except 2 and 5. "The existence of a trimming algorithm for p depends on the existence of a multiple of p which is larger by 1 or smaller by 1 than a multiple of 10," Zazkis noted.

Can a similar algorithm be used to determine divisibility by a composite number? Are there other algorithms that can be generalized to work for primes?

The realm of divisibility tests has all sorts of avenues for further investigation and algorithm development.

Originally posted August 19, 2002

Playing Pig Optimally

The simple dice game known as Pig is surprisingly complex when you're trying to find an optimal strategy for playing it.

The game's object is to be the first player, rolling a die, to reach a total of 100 points. On each turn, a player rolls a die as many times as he or she wishes, totaling the score of the rolls until the player decides to end the turn and pass the die to his or her opponent.

However, if the player rolls a 1, he or she immediately loses all the points accumulated during that turn, and the die passes to the other player. The big decision at any point during a turn is whether to roll or stop (hold). In general, it doesn't pay to be greedy.

A roll is successful if any one of 2, 3, 4, 5, or 6 comes up. On average, you gain four points per roll. Your chance of rolling 1 is just one in six. So, it seems to make sense to continue rolling the die until you accumulate 20 points during a turn. If you stop then, the odds would be in your favor.

However, this isn't the full story. There are circumstances when the "hold at 20" strategy isn't optimal.

Consider the following scenario. Your opponent has a score of 99 and would likely win in the next turn. You have a score of 78, and you've just reached 20 during your turn, for a new total of 98. In this case, your probability of winning the game with one additional roll is higher than the probability of winning if you ended the turn and allowed the other player to roll.

It was such subtleties that got computer scientist Todd W. Neller to analyze the two-player game in detail and find a strategy for true optimal play. His key insight was the understanding that playing to maximize points for a single turn isn't the same thing as playing to win.

Neller wrote a computer program to compute all the relevant probabilities, using a technique known as value iteration, and colleague Clif Presser created dramatic visualizations of the results. See "The Game of Pig."

The results show that the "hold at 20" strategy comes close to representing optimal play only when both players have low scores. When either player has a high score, it's best to try to win each turn.

Amazingly, between these extremes, there's a great deal of variability in the best strategy to follow in any given situation. When the results are plotted in three dimensions, with player 1's score on one axis, player 2's score on the second axis, and the turn total on the third axis, the surface representing the roll/hold boundary has a remarkably intricate, wavy structure (below).

Indeed, the cross section representing the roll/hold boundary when your opponent has a given score is surprisingly irregular  (below). For example, suppose your opponent's score is 30. If you're playing optimally and have a low score, you have to take greater risks to catch up. If you have a high score, it's better to play much more conservatively.

In general, as shown by the irregular landscape of the roll/hold boundary for Pig, details of optimal play can be far from intuitive.

Interestingly, if both players play optimally, the starting player wins 53 percent of the time. If the first player plays optimally and the second uses a "hold at 20" strategy, the optimal player wins 58.7 percent of the time. When the "hold at 20" player goes first, that player wins 47.8 percent of the time.

Pig has many variants, including versions that require two dice, somewhat different rules, or more than two players. Each one has its own peculiarities, and each is worthy of analysis. See visualizations of Neller's analyses of some of these versions.

"Seeing the 'landscape' [of optimal play] is like seeing the surface of a distant planet sharply for the first time having previously seen only fuzzy images," Neller and Presser concluded in the journal article "Optimal Play of the Dice Game Pig" describing their results. "If intuition is like seeing a distant planet with the naked eye, and a simplistic, approximate analysis is like seeing with a telescope, then applying the tools of mathematics is like landing on the planet and sending pictures home."

Originally posted May 31, 2004