Jaipur Chess

 

Jai Mahal Palace, Jaipur, India, 2010.

Photo by I. Peterson

The Long Run

Quite often, in a race game governed strictly by chance, the player who starts out ahead stays ahead for most, if not all, of the race. This striking feature is worth examining more closely.

In a two-player coin-flipping game, heads and tails will each win half the time, on average (see "Rolls and Flips"). But in a game of a thousand flips, when the total number of heads versus the total number of tails is at issue, it is very likely that one player will be ahead in the cumulative scoring more than 90 percent of the time.

In other words, the proportion of time that, say, the number of heads exceeds the number of tails can be very high. Although it's equally likely that either of the two players will be in the lead at any given moment, one of them will probably have the lead nearly the whole time.

Such a counterintuitive reality hinges on the fact that, like dice, cards, and roulette wheels, coins don't have memories. Each coin toss is independent of all other tosses. Even if the first few tosses happen to result in more heads than tails, the probability of getting either a head or a tail on each subsequent toss remains precisely ½.

Whatever slight trend gets established at the beginning doesn't necessarily get washed out, even though, in the long run, the proportion of heads to tails generally gets closer and closer to ½ as the number of tosses increases.

Gamblers and other game players often incorrectly reason that because the numbers of heads and tails even out over the long run, a sequence of eight heads out of ten means that tails are somehow more likely to come up in the next ten or twenty tosses to establish a proper balance. They imagine that the probabilities involved are sometimes elastic, stretching more tightly or loosening as necessary to bring the results back in line with expected trends.

What people overlook is the fact that the proportion of heads and tails also approaches ½ if, in subsequent tosses, heads and tails appear equally often—as they should.

Suppose heads have shown up eight times and tails twice in the first ten flips. The proportion of heads is 0.8 at this stage, In the next two thousand turns, the players happen to toss a thousand heads (for a total of 1,008) and a thousand tails (a total of 1,002). Heads are still in the lead, but the proportion of heads is now considerably closer to 0.5 (or ½).

Thus, flipping four heads in a row with a fair coin doesn't make it any more likely that the next flip will be tails. But it does make it more likely that you will end up with 54 heads in 100 flips, as opposed to 50.

Similarly, in a simple, two-player race game involving a single die, the player who's ahead at any given time has the higher probability of winning. Even at a hundred squares from the goal, a player merely four spaces behind faces odds of two to one against winning if it's his opponent's turn to throw the die.

Gamblers at roulette tables in casinos fall into the same kind of trap when they keep track of the numbers that happen to come up on the wheel. They usually believe that they can identify patterns in the sequences of numbers that come up.

However, if the roulette wheel is truly unbiased, such efforts are fruitless. What happens on one turn of the wheel has no bearing on what occurs on the next.

Because the casino holds one or two numbers on the wheel as its own, the casino bank is certain to beat the majority of players in the long run. Those gamblers who continue to play long enough will be ruined sooner or later, and no system of betting and number or color selection can prevent such an outcome.

Of course, apparent patterns do inevitably come up in the distribution of the numbers, but these ephemeral patterns don't mean a thing unless the wheel were imperfect.

The 17th-century Russian novelist Fyodor Dostoyevsky (1821-1881) became seriously hooked on roulette in 1863, when he won a considerable fortune on his first foray into playing the wheel. In a letter to his brother Misha, Dostoyevsky wrote:

My dear Misha, in Wiesbaden, I invented a system, used it in actual play, and immediately won 10,000 francs. The next morning I got excited, abandoned the system and immediately lost. In the evening I returned to the system, observed it strictly, and quickly and without difficulty won back 3,000 francs.

When I arrived in Baden-Baden I went to the tables and in a quarter of an hour won 600 francs. This goaded me on. Suddenly I began to lose, could no longer keep my head, and lost every farthing.

So it went in Dostoyevsky's succession of roulette episodes across Europe—a journey marked by requests for loans, unpaid hotel bills, and pawned watches—until 1871, when he finally quit.

Dostoyevsky's masterful short novel The Gambler, written in haste in 1866 to settle a debt, presents a striking portrait of an individual irresistibly drawn into Lady Fortune's web. Dostoyevsky describes a gambler's obsession with the zero slot on the roulette wheel:

It was, of course, a rare happening for zero to come up three times out of some ten or so, but there was nothing particularly astounding about it. I had myself seen zero turn up three times running two days before, and on that occasion one of the players, zealously recording all the coups on a piece of paper, had remarked aloud that no earlier than the previous day that same zero had come out exactly once in twenty-four hours.

Wikipedia.

Dostoyevsky was certainly not the first to write about the lure of the luck of the draw. Girolamo Cardano (1501-1576), a brilliant, highly regarded physician and mathematician with an impressive array of intellectual achievements to his credit, was another player who found gambling irresistible.

Girolamo Cardano. MAA Mathematical Portrait Gallery.

Around 1564, Cardano wrote The Book on Games of Chance, in which he presented competent analyses of backgammon and several other dice games, along with a variety of card games that included an early version of poker. He also excelled at chess, which at that time was accompanied by betting and handicapping.

In a section on who should play and when, Cardano offered the following advice about moderation in gambling:

So, if a person be renowned for wisdom, or if he be dignified by a magistracy or any other civil honor or by a priesthood, it is all the worse for him to play…. You should play rarely and for short periods, in a suitable place, for small stakes, and on suitable occasions, or at a holiday banquet.

It was advice that Cardano himself had trouble heeding. Erratic, argumentative, and obsessed, he gambled incessantly, sending his family into the Milan poorhouse for long stretches. In his brutally frank autobiography, he remarked:

During many years—for more than forty years at the chess boards and twenty-five years of gambling—I have played not off and on but, as I am ashamed to say, every day. Thereby I have lost esteem, my worldly goods, and my time. There is no corner of refuge for my defense, except if someone wishes to speak for me, it should be that I did not love the game but abhorred the circumstances which made me play: lies, injustices, and poverty, the insolence of some, the confusion in my life, the contempt, my sickly constitution and unmerited idleness, the latter caused by others.

The irrational superstitions and strategies of gamblers testify to the extraordinarily vast landscapes of possibility in games of chance. Unpredictability reigns, with patterns appearing out of nowhere, then mysteriously disappearing. Anything is possible, yet the possibilities are doled out in measured doses.

Faced with the astonishing scope of chance, the compulsive gambler lives on the brink, ever focused on the next spin of the wheel or roll of the die.

Using the mathematics of chance, you can predict outcomes, establish conditions for guaranteeing certain results, or, at the very least, show whether any particular game is worth playing.

Games provide structured situations in which people can compute probabilities, often with great precision, and test their hypotheses. They can then bring this knowledge to bear not only in games but also in everyday situations in which uncertainty and randomness play a role. Understanding the laws of probability can guide their decisions in a wide range of matters.

Of course, games teach nothing unless you pay attention to the odds and learn to deal with them. But even precise calculations may not be enough in the face of human greed and deceit.

In his 1753 novel The Adventures of Ferdinand, Count Fathom, Tobias Smollett (1721-1771) noted that his hero, Fathom, learned to "calculate all the chances with the utmost exactness and certainty," only to be fleeced by a team of swindlers. A knowledge of mathematics is no proof against human folly.

The theory of probability combines commonsense reasoning with calculation. It domesticates luck, making it subservient to reason. It stands as an attempt to master the vagaries of uncontrollable circumstance in the face of unavoidable ignorance.

Nonetheless, the tantalizing patterns that come and go among the infinite possibilities of randomness have a way of entangling the human mind. Randomness and pattern intermingle in mysterious ways. Where there is one, the other inevitably lurks.

Previously: Change of Face

Next: Party Games

Change of Face

The serious gamblers in casinos hang out at the craps tables. The basic rules of this two-dice game are simple, but the bewildering array of options for betting on various outcomes creates a fast-paced, insidiously seductive pastime, in which a heady brew of chance, intuition, experience, calculation, and superstition come into play.

The shooter tosses two dice. If a total of seven or eleven comes up on a beginning roll, the shooter and those wagering with him win whatever amount they bet. If a two, three, or twelve total (called craps) shows up, the shooter and his companions lose.

Players betting against the shooter win if a two or three comes up. They neither lose nor win for a double six (twelve). Any of the remaining six totals (four, five six, eight, nine, and ten) on a beginning roll starts off a different sequence of play, with different possible bets.

Suppose a shooter replaces the standard dice with a pair of new dice whose faces are marked as follows: 1, 2, 2, 3, 3, 4 and 1, 3, 4, 5, 6, 8. Should the other players or the casino management object?

First, we can check whether the probabilities of the various sums with the new dice are different. We can do this by displaying in a table all the ways in which each sum from two to twelve can be obtained with the two different pairs of dice.

Substituting a pair of "weird" dice with faces labeled 1, 2, 2, 3, 3, 4 and 1, 3, 4, 5, 6, 8 for a pair of standard dice has no effect on games in which only the sums matter. For both sets of dice, there's only one way to roll a sum of two, two ways to roll a sum of three, and so on, as shown in charts of sums corresponding to the possible outcomes for standard dice (left) and weird dice (right). In games in which rolling doubles plays a role, however, there is a difference. There are six ways to roll doubles with standard dice and only four ways to roll doubles with weird dice (shaded squares).

Interestingly, the unusually marked dice (known as Sicherman dice) and the standard dice have exactly the same frequencies for the possible sums. There's only one way to roll a two, two ways to roll a three, and so on.

Although the numbering on the weird dice is completely different from that on the standard dice, all the odds are exactly the same for rolling any given sum. You could make the substitution at the craps table as far as the sums are concerned (see "Weird Dice" by Joseph Gallian).

The trouble is that craps betting puts certain combinations, such as doubles, in special roles (for example, the double six on a beginning roll). With the weird dice, there's no way to get a double two, five, or six, and there are two ways to get a double three.

Changing the dice would have a considerable impact on many board games in which rolling doubles or other special combinations affects a player's fate (see "Weird Dice").

In Monopoly, players buy, sell, rent, and trade real estate in cutthroat competition to bankrupt their opponents, They take turns throwing a pair of dice , with the totals indicating how many spaces to proceed along an outside track that includes 22 color-coded properties, four railroads, two utilities, a Luxury Tax square, an Income Tax square, three Chance squares, and three Community Chest squares. Corner squares are marked Go, Just Visiting/In Jail, Free Parking, and Go to Jail.

Players start at Go. A double warrants a second throw, but three consecutive doubles sends a player directly to the In Jail square. To get out of jail, the player must throw a double. If she succeeds, whatever sum she gets decides how many spaces to advance along the board (see also "Monopoly Cheat Sheet").

However, using the nonstandard dice gives a lower probability of rolling doubles (only 4 out of 36 instead of 6 out of 36). Moreover, the chances of landing on a square six spaces away goes up twofold and the chances of landing four, ten, or twelve spaces away on a move out of jail are zero. 

Thus, if you happen to own the property St. James Place, which is six spaces away from jail, you are likely to collect lots of rent from players escaping jail. On the other hand, the owner of Virginia Avenue (four spaces away from jail) loses out on the extra business.

In fact, according to calculations made in one study, the change in dice moves St. James Place up from tenth to the sixth most frequently visited space in the game. Virginia Avenue descends from 24th to  27th in the rankings.

It's possible to prove mathematically that the weird dice represent the only alternative numbering of a pair that provides the same sum probabilities as standard dice. Of course, it doesn't matter how you arrange the six numbers on each die, though you can opt for symmetry by placing the numbers so that each set of opposite sides totals five or nine.

You can work out alternative numbering schemes not only for cubic dice but also for dice in the shape of a tetrahedron (four triangular faces), an octahedron (12 pentagonal faces), and an icosahedron (20 triangular faces). (See "Renumbering the Faces of Dice" by Duane M. Broline.)

For example, a pair of standard octahedrons marked 1, 2, 3, 4, 5, 6, 7, and 8 have the same sum probabilities as a pair with one marked 1, 3, 5, 5, 7, 7, 9, 11 and the other marked 1, 2, 2, 3, 3, 4, 4, 5. Either set would work in a two-dice game.

There are also other ways to get the same sum results as two standard cubic dice. For example, you can use a tetrahedral die labeled 1, 1, 4, 4 combined with a spinner with 18 equal segments labelled 1, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 7, 7, and 8. This combination yields the same sum probabilities as an ordinary pair of cubes labeled 1 through 6.

Using weird dice brings a fresh perspective to games of chance. It provides a welcome opportunity for examining the interaction between rules and randomizers.

Previously: Climbing and Sliding

Next: The Long Run

Climbing and Sliding

The origins of the game of Chutes and Ladders (or its Snakes and Ladders counterpart) go back many centuries to India and a board game called moksha patam (a Hindu concept that is akin to heaven and hell). Designed as a way of instructing children in religious values, the game graphically depicts the coexistence of good and evil and illustrates the impact of chance on human affairs.

In the game, checkerboard pilgrims follow a winding path that is shortened by virtuous deeds and lengthened by sinful acts or wrongdoing. They triumph when they climb ladders that represent faith, reliability, and generosity, and they fail when they slither down snakes that signify disobedience, vanity, and greed. A die dictates the fortunes of the road.

The game's design and rules have varied over the years. Typically, a grid ten squares long and ten squares wide, the game board features several ladders and snakes (or chutes). The number of shortcuts and detours, their length, and their placement all affect how the game proceeds.

A classic Indian design may have twelve snakes and eight ladders, with one long snake reaching back down to the starting square and a ladder of more modest length extending to the winning square at the top of the board.

In modern Western versions of the game, the moralizing usually takes on a gentler cast, and the snakes are often replaced by chutes (slides). Usually, the number of ladders equals the number of snakes, though in some upwardly mobile versions the ladders predominate.

Example of a Chutes and Ladders game board.

In most of these game designs, the distribution and number of snakes and ladders probably reflect trial-and-error experience when it comes to a combination that makes a pleasing game.

However, although rolls of a die determine the moves, it's possible to use mathematics to analyze the game and figure out where to place the snakes and ladders to ensure that the game is neither too long nor too short.

Of course, you could test a board design by playing hundreds of games and recording the results. Alternatively, you can use a mathematical approach named for mathematician Andrey A. Markov (1856-1922) to compute the average length of a game.

Markov studied systems of objects that change from one state to another, according to specified probabilities. When an initial state can lead to subsequent states, and these states, in turn, can lead to additional states, the result is a Markov chain.

Suppose we examine a game of Chutes and Ladders in which there's only one player. Initially the player's token is off the board, and we call this condition state 0. The first roll of a die produces either one, two, three, four, five, or six, meaning that the player can move his (or her) token to one of the squares numbered 1, 2, 3, 4, 5, or 6 after the first roll.

If the player is lucky and rolls a one, he goes to square 1, and then up the ladder to square 38 without an additional turn. Rolling a four would again put him on a ladder, this time taking him to square 14.

So, as the result of one turn the player can end up in state 2, 3, 5, 6, 14, or 38, with an equal probability of 1/6. Squares 1 and 4 aren't considered states because the token doesn't come to rest there. Similarly, the top of any chute doesn't count as a state.

For the second roll of the die, the game can be in one of six states, and we must consider each possibility separately.

Suppose, for example, that the first throw puts the player in state 2. From there, the second roll moves him to square 3, 4, 5, 6, 7, or 8. Because 4 is the bottom of a ladder, the player immediately ascends to 14. So, starting from state 2, the player can move to state 3, 5, 6, 7, 8, or 14 with equal probability.

If the first roll happened to put the player in state 14, the second roll would bring him to square 15, 16, 17, 18, 19, or 20 with equal probability. However, landing on square 16 would plunge him back to 6. Hence, from state 14 the player can move with equal probability to state 6, 15, 17, 18, 19, or 20.

After two rolls, the game can be in a total of 21states. These states, however, are not equally likely. For example, there's only one way to reach state 44 at the end of two rolls: by rolling a one and then a six. Therefore, the probability of ending up in state 44 after two rolls is 1/6 ✕ 1/6 = 1/36.

In contrast, there are three ways of getting to state 31: by rolling three and six, by rolling five and four, and by rolling six and three. Thus, the probability of being in state 31 after two throws is (1/6 ✕ 1/6) + (1/6 ✕ 1/6) + (1/6 ✕ 1/6) = 3/36.

Such calculations can be carried out for three, four, or more rolls to create a complicated Markov chain showing how the game progresses from one set of states to another. For any position of the token, a player can readily determine the probability of ending up on that square.

You can also use the same technique to analyze particular situations. For instance, to place a chute so as to minimize a player's chance of climbing a particular ladder, you can construct a table giving the probabilities of climbing a ladder when a ladder is a given number of spaces ahead, first with no chutes in the way and then with a single chute on one of the intervening squares in front of the ladder.

A player who is one square in front of the ladder has one chance in six of rolling a one to get to the ladder, giving a probability of 1/6, or about .17. A player two squares in front can get to the ladder by rolling either a two (probability 1/6) or two ones (1/36) for a combined probability if 1/6 + 1/36, or .19.

A player who starts at square three must roll a three (1/6), two and one (1/36), one and two (1.36), or one, one, and one (1/216), for a total probability of .23, to reach the ladder.

If there is no chute, the probability of reaching the ladder turns out to be highest when the player is six spaces away.

You might think that placing a single chute immediately in front of a ladder would serve as a strong guard, but calculating the probabilities of landing there instead of on the ladder shows it to be the least effective position. A chute six squares in front is much more difficult to circumvent without missing the ladder as well.

Some of these factors come into play in some well-known versions of Chutes and Ladders. In one version, the top row, or last ten squares, on the board has three chutes. One chute is two squares in front of the finish line. A second is five squares in front, and a third is seven in front.

These chutes turn out to be effective guards, and more often than not a player wins by taking the ladder from square 80 directly to the winning 100th square, completely bypassing the treacherous final stretch.

.

Indeed, the likelihood of such a finish is measured by the fact that all three chutes in the top row land the player in the row that leads to the shortcut ladder in square 80, with no other obstacles standing in the way.

An alternative version, called Gigantik® Snakes & Ladders, has a very different set of snakes and ladders. The large game board has two places in which a guard snake immediately precedes a ladder, one near the beginning and another near the end. It also has two lengthy snakes slithering down from the top row and no ladder directly to the finishing square, so that games tend to take longer than those on a standard Chutes and Ladders board.

The theory of Markov chains offers a powerful method of analyzing probabilistic behavior in a variety of systems. Nowadays computers can readily handle large numbers of states, and researchers can quickly analyze the outcomes and fairness of such games as Chutes and Ladders and Monopoly.

The same techniques can also be used in science to model the wanderings of molecules drifting in air, the foraging patterns of birds, and the fluctuations of prices on a stock market.

Previously: Tumbling Dice

Next: Chance of Face

The Die Is Cast

"Iacta alea est."

—Attributed by Suetonius to Julius Caesar (100-44 B.C.)

A die tumbles out of a cupped hand, bounces on the carpet a few times, rolls a short distance, then teeters to a stop. The uppermost face of the white cube shows four black dots arranged in a square.

Grinning, a child briskly moves a red token four squares to the right along the bottom row of a large checkerboard grid. The token lands on a square marked with the foot of a ladder. The player immediately takes the shortcut, advancing the token up the rungs to a higher row. Just ahead lies a square ominously marked with the upper end of a chute—the start of a costly detour.

With moves governed entirely by the roll of a die, Chutes and Ladders (earlier versions featured snakes and ladders) is a racecourse on which children of different ages and their elders can meet on an equal footing. Physical prowess and breadth of knowledge are immaterial on such a field. Only luck comes into play.

The playing of games has a long history. We can imagine the earliest humans engaged in contests of physical strength and endurance, with children racing about playing tag and great heroes (such as Heracles) struggling against daunting obstacles, as recorded in ancient myths.

Written references to games go back thousands of years, and archaeologists have recovered a wide variety of relics that they interpret as gaming boards and pieces.

In the year 1283, when the king of Castile, Alfonso X (1224-1284), compiled the first book of games in European literature, he testified to the importance of games-playing in medieval society.

"God has intended men to enjoy themselves with many games," he declared in the book's introduction. Such entertainments "bring them comfort and dispel their boredom."

Even in Alfonso's time, many of the board games he described were already hundreds of years old. Chess, the king's favorite, had been developed in India centuries earlier. Backgammon, one of the great entertainments of thirteenth-century nobility, had evolved from the Roman game tabula.

Succeeding centuries brought new amusements, along with variations on old ones. Each age and place had its particular favorites: the dice-and-counter game of pachisi in India, the coin-sliding game of shove ha'penny in William Shakespeare's England, the ancient game of go in China and Japan, and the card game cribbage in seventeenth-century Europe and America. In the Victorian era in Great Britain, nearly every parlor featured a wooden board of holes and pegs for the game of peg solitaire.

Amusement remains the motivation underlying the explosion of ingenuity that has created a bewildering array of addictive computer, video, and arcade games, various forms of online and casino gambling, and new sports ranging from beach volleyball to snowboarding, along with novel board games and puzzles to tickle the mind.

"With their simple and unequivocal rules, [games] are like so many islands of order in the vague untidy chaos of experience," author Aldous Huxley (1894-1963) wrote several decades ago. "When we play games, or even when we watch them being played by others, we pass from the incomprehensible universe of given reality into a neat little man-made world, where everything is clear, purposive and easy to understand."

In these miniature worlds, competition brings excitement. Randomness serves as an equalizer. Chance introduces an element of suspense. Risk amplifies the thrill of play to an intoxicating level.

These tiny microcosms also attract mathematicians, who can't resist the distinctively human pleasure of learning the secrets of games. Who stands to win? What's the best move? Is there an optimal strategy? How long is a game likely to take? How do rules combine with chance to produce various outcomes? How are fairness and randomness linked?

In games of chance, each roll of a die, toss of a coin, turn of a card, or spin of a wheel springs a delicious surprise. Anyone can play. Anyone can win—or lose. Mathematics helps dispel some of the mystery surrounding unpredictable outcomes. It embodies an ever-present urge to tame the unruliness of Lady Fortune.

Using mathematical reasoning, we can't predict the outcome of a single roll of a die, but we can alter our expectations in the light of such an analysis. We may take comfort in the notion that, if the die is fair, each face of it will come up equally often in the long run.

More generally, we can begin to make sense of and exploit the patterns that inevitably appear and disappear among the infinite possibilities offered by random choices.

Previously: Infinite Possibility

Next: Rolls and Flips

Party Games

Like driftwood spars, which meet and pass

Upon the boundless ocean-plain,

So on the sea of life, alas!

Man meets man,—meets and quits again.

—Matthew Arnold (1822-1881), "Switzerland"

In work and play. from hour to hour and year to year, we pass from one gathering to another. Sometimes we are surrounded by people we know; sometimes we find ourselves in the presence of strangers. The restless ebb and flow of human concourse appears to be random, yet there are curious patterns present in the composition of these random groupings of strangers and acquaintances who come and go.

Whether in large crowds, modest social gatherings, or small groups, people congregate in all sorts of combinations of strangers and acquaintances. Consider the varied possibilities in a party of six.

You're one of six people at a dinner party. You look across the table at your five companions. You would undoubtedly find that the dinner party includes either a group of at least three people who all know one another or a group of at least three people who don't know one another.

The reason for this certainty lies in a mathematical proof that any gathering of six people will always automatically include one or the other of these two groupings. No such guarantee is possible when five or fewer people are present.

To prove that any party of six must contain at least three acquaintances or at least three strangers, you could write down all the possible combinations, starting with a group in which everyone knows one another. However, there are 32,768 such possibilities.

This number reflects the fact that any pair in a group of six must be either acquainted or strangers. Moreover, there are six choices of people for the first member of a pair, which leaves five choices for the second member of the pair, for a total of 30 possibilities. Because the order of the choices in a particular case doesn't matter (picking Alice first and then Barry is the same as picking Barry, then Alice), the number of possibilities that count is down to 30/2, or 15. Overall, for two possible relations (stranger or acquaintance), the number of possibilities is 2¹⁵, or 32,768.

Luckily, there's a shorter path to a proof. You need consider only two particular cases.

Suppose a party is attended by the conveniently named guests Alice, Barry, Charles, Diana, Edith, and Frank. Of the five partygoers Barry, Charles, Diana, Edith, and Frank, either at least three are friends of Alice or at least three are strangers to Alice.

Suppose Alice knows Barry, Charles, and Diana. If either Barry and Charles, Barry and Diana, or Charles and Diana are friends, then Alice and the acquainted pair make three people who know one another. Otherwise Barry, Charles, and Diana are mutual strangers.

In the second case, suppose Alice knows only two (or fewer) of the others, say, Barry and Charles. If either Diana and Edith, Diana and Frank, or Edith and Frank are strangers, then Alice and the unacquainted pair make three people who do not know one another. Otherwise, Diana, Edith, and Frank are mutual acquaintances.

This argument covers all possible cases for each of the six dinner-party guests.

The result represents a special case stemming from a branch of mathematics known as Ramsey theory, named for the mathematician Frank Plumpton Ramsey (1903-1930).

Instead of talking about six people, you could consider groups consisting of any number of people. Instead of specifying just two relationships (acquaintances and strangers), you could have any number of mutually exclusive relations. For example, you could consider people (or nations) who are allies, foes, and neutral parties—representing three mutually exclusive relationships—embroiled in a widespread conflict.

In general, Ramsey theory concerns the existence of highly regular patterns in sufficiently large sets of randomly selected objects, whether they are gatherings of people, sequences of randomly generated numbers, randomly placed points in the plane, or even stars in the night sky.

Tabulating the outcomes of 2,500 flips of a coin by sequentially filling in the squares of a 50-by-50 grid (black for tails, white for heads) produces a random array. It is not difficult, however, to pick out fragments of patterns among the black or white squares, in much the same way that you can find patterns among stars randomly scattered across the sky. In this case, one array represents tosses of a fair coin and the other represents tosses of a slightly biased coin. Can you tell which is which?

It's straightforward to convert a party puzzle into a graph theory problem. In general, a graph consists of an array of points, or vertices, connected by straight lines, which are often called edges.

In the dinner-party case, you can draw a point for each of the six people present in the group. You can then draw lines to join the points, with each line colored red to signify two people who know each other or blue to mean the two people are strangers. When all pairs of points are joined, the resulting network of points and lines is known as a complete graph.

Depending on the relationships specified in a given case, such a graph may contain only red lines (all acquaintances), only blue lines (all strangers), or a mixture of red and blue lines joining the points. The problem comes down to proving that no matter how the lines are colored, you can't avoid producing a red triangle (representing three mutual acquaintances) or a blue triangle (three strangers).

A graph depicting relationships among six people at a party, where red lines link acquaintances and blue lines connect strangers.

Such a coloring is guaranteed for a complete graph of six points, but not necessarily for a graph of five or fewer points, as the following figure demonstrates.

This graph representing the relationships of five people shows that it is possible to obtain a gathering in which there is no group of three strangers or three acquaintances. In other words, there is no triangle in the diagram that is made up entirely of red or blue lines.

Wolfgang Slany turned the party problem into a two-person game he called HEXI (see his paper "Graph Ramsey Games"). You and your opponent take turns coloring in the uncolored edges of a complete graph laid out as a hexagon, with each player using a different color. The first person to build a triangle with all three edges of the same color loses.

Slany also had a variant of the game in which a player may choose to color in more than one edge with each turn.

In both cases, Ramsey theory ensures that HEXI never ends in a draw.

Previously: The Long Run

Next: Pigeonhole Congestion

Poe's Secrets

Writer Edgar Allan Poe (1809-1849) is famous for his short stories of the mysterious and the macabre. Poe's tale "The Gold-Bug," published in 1843, is sometimes cited as one of the best works of fiction that turn upon a secret message.

"The Gold-Bug" is about a secret message written in invisible ink on a scrap of parchment. The deciphered message leads to a buried chest filled with fabulous treasure. Here's the coded message that Poe included in his story:

The clever treasure seeker in story, William Legrand, assumed that symbols stood for letters of the alphabet, with no spaces left between the words of the message. He noticed that the character "8" appears 33 times, far more often than any other character. In the English language, the letter that occurs most often is "e."

Starting with that clue, he went on to look for combinations of three characters that might represent "the"—a very common word in English. Legrand could then guess that the semicolon represents "t" and 4 represents "h."

Following such hints, Legrand deciphered the secret message. Clues contained in the mysterious message eventually led him to a fortune in gold and jewels.

Poe had a longstanding interest in cryptology. When he for a short time became editor of Graham's Lady's and Gentleman's Magazine in Philadelphia, he offered to solve cryptograms sent to him by readers and, while waiting for responses, wrote an essay about secret writing for the July 1841 issue of the magazine.

When Poe ended the contest 6 months later, he claimed to have solved the 100 or so legitimate ciphers that readers had submitted. In his final "addendum" on the topic, published in the December issue, Poe included two ciphers from "a gentleman whose abilities we very highly respect." He attributed the ciphers and accompanying notes to W.B. Tyler and challenged readers to solve the puzzles. Poe never published the solutions.

No one seemed to have paid much attention to the ciphers until 1985. That's when Poe scholar Louis A. Renza suggested in an essay, titled "Poe's Secret Autobiography," that Tyler and Poe were the same person.

English professor Shawn Rosenheim took up Renza's theory and, in his 1996 book The Cryptographic Imagination: Secret Writing from Edgar Poe to the Internet, furnished additional circumstantial evidence pointing to Poe as the author of the two ciphers.

Meanwhile, in 1992, intrigued by Rosenheim's ongoing research on the topic, Terence Whalen took a break from working on his dissertation to tackle the puzzle. He solved the first of Tyler's cryptograms, which consisted of a long string of various typographic symbols.

The key to the solution was Whalen's recognition that the three-symbol pattern ", † § "—repeated seven times in eight lines—represents the word "the."

The deciphered passage proved to be lines from the 1713 play Cato, a Tragedy by English essayist Joseph Addison (1672-1719). Whalen's solution, however, did not settle the question of who created the cipher.

The second cipher, which used several different symbols for each English letter in the text, was much more difficult.

Determined to obtain a solution, Rosenheim offered a prize of $2,500 for deciphering the cryptogram. The contest received a substantial boost in 1998 when Jim Moore of Bokler Software, which builds cryptographic components for software developers, created a website devoted to the puzzle.

Rosenheim and Moore fielded hundreds of inquiries from around the world. The puzzle was finally solved in July 2000 by Gil Broza, a software engineer in Toronto.

It turned out that the number of different symbols for a given letter depended on the relative frequency with which that letter appears in English text. So, there were two symbols standing for "z" and 14 symbols for "e." Given the brevity of the cipher, would-be sleuths couldn't count on applying information about letter frequencies to crack the code.

Broza assumed that the symbols in the cryptogram were properly broken up into English words and proceeded from there, eventually using a computer to check for patterns and sort through various possibilities.

Broza's solution revealed that the original cipher contained more than two dozen mistakes, which had been introduced by the typesetter or the puzzle's originator. The deciphered text begins, "It was early spring, warm and sultry glowed the afternoon. The very breezes seemed to share the delicious languour of universal nature,…"

That certainly doesn't sound like Poe, but the text echoes themes that he favored. The passage is probably taken from some unknown novel or story of the period, Rosenheim said. It's still possible, though not certain, that Poe himself composed both ciphers.

There is something mysterious even in the decrypted cipher, Rosenheim added, not only because we do not know who enciphered it but also because it reminds us of the uncanny and limited immortality writing sometimes affords.

Originally posted November 13, 2000

Fair Play and Dreidel

For centuries, the game of dreidel has been part of the festivities associated with Hanukkah. Surprisingly, it turns out that this ancient pastime is also an unfair game.

The dreidel is a four-cornered top or spinner having sides labeled with the Hebrew letters Nun, Gimel, He, and Shin.

Any number of players can participate, with each player contributing a penny or some other unit to the pot to start the game. The players then take turns spinning the dreidel until each player has had a turn. Then they spin again in the same order. The game continues until the players reach some mutually agreed stopping point.

Each spin has four equally likely outcomes. If the letter Nun (N) comes up, there's no payoff, and play passes to the next player. If Gimel (G) comes up, the player collects the entire pot, and everyone contributes a penny to form a new pot. If He (H) comes up, the player collects half the pot. If Shin (S) comes up, the player adds a penny to the pot.

In 1976, mathematician Robert Feinerman proved, as reported in the article "An Ancient Unfair Game," that the first player has a greater expected payoff than the second player, who in turn has a greater expected payoff than the third player. Thus, the first player has an unfair advantage over the second player, and so on.

"Furthermore, this unfairness is accentuated if a stopping rule is used which does not guarantee an equal number of turns to each player," Feinerman noted.

Feinerman derived the following formula for the expected value of the payoff on the nth spin with N players:

Some two decades later, Felicia Moss Trachtenberg extended Feinerman's results and worked out a way to make the game fair. The key is to change the ratio of the amount a each player puts in the pot to begin the game (or collects after spinning G) and the amount p of the penalty paid for spinning S.

"The modified game of dreidel will be fair just when p/a = N/2, where N is the number of players," Trachtenberg said. Thus, for four players, if the ante is 1 penny, the penalty should be 2 pennies.

To see why this ratio works, notice that the amount in the pot when the first player spins is Na. The player's possible payoffs are 0, Na, Na/2, and −p, depending on which side of the dreidel comes up. For the game to be fair for the second player, the expected payoff must remain constant from the first to the second spin, and that can happen only if the ratio p/a equals N/2.

In the standard version, the ratio is less than N/2, which biases the game toward the first player. It's also possible to bias the game toward the last player by making the ratio greater than N/2.

Trachtenberg evidently learned the lesson of her research, at least with regard to the standard game. The brief biography that appears with Trachtenberg's article in the September 1996 College Mathematics Journal noted: "In the future, Felicia intends to go first when playing dreidel, especially against her husband, Ari Trachtenberg, a renowned dreidel enthusiast."

Originally posted December 2, 1996

Minesweeper Logic

The game Minesweeper was one of the more insidious time wasters once readily available to users of Microsoft Windows-based computers. It was easy to become addicted to this seemingly simple solitaire game, in which strategy, logic, and luck added up to a potent, mind-teasing mixture.

In the basic version of the game, the player faces a gray landscape of 64 blank squares in an eight-by-eight grid. The object is to locate 10 randomly placed "land mines" hidden among the playing field's squares, working as quickly as possible without detonating any of them. Larger boards are also available.

To uncover a square, the player clicks on it with the left mouse button. If the square harbors a mine, the player loses. If instead a number (from 1 to 8) appears on the square, it specifies how many mines are present in the eight squares surrounding the numbered square.

It's clear, for example, that finding a square numbered 8 means that all eight adjacent squares contain mines. If the square remains blank, there are no mines in the surrounding squares.

To mark a square suspected of containing a mine, the player clicks on it with the right mouse button, putting a little flag on the square.

The first few moves require one or more wild, potentially fatal guesses. Given that uncertainty, is it better to start in a corner, on the side, or in the middle? The choice depends on the sorts of things that can happen on subsequent moves, which are not the same for every starting position. Experts recommend beginning somewhere in the middle.

If you survive the initial phase, you can then rely on logic to carry you the rest of the way—most of the time. There are a few situations in which you may be forced to guess a mine's location to complete a game.

It doesn't take long to develop strategies for playing and beating the game. In general, clearing a board rapidly requires a form of pattern recognition. For example, if an uncovered square is labeled 1, and there is only one covered square touching it, that covered square must be a mine.

Finding a square with the number 1 next to a suspected mine means that all other unknown squares surrounding the numbered square can be safely uncovered (assuming you marked the mine correctly). In fact, if you have found all the mines around a given numbered square, you can uncover the remaining squares by clicking the numbered square with the left and right mouse buttons simultaneously.

You can also take advantage of a little quirk. In some versions of Minesweeper, Microsoft programmers designed the game so that the first click never hits a mine. If the square originally contained a mine, the computer moves it to the top left-hand corner of the board or to the first available square to its right.

A while ago, mathematicians Patti Frazer Lock and Allan A. Struthers took the business of developing Minesweeper strategies one step further. They used the game in the classroom to introduce students to formal mathematical proofs.

In Lock's sophomore courses, students played a few games, then tried to evaluate various types of positions to determine which squares are definitely safe and which ones are definitely mined. The exercise gave them a sense of what, given the rules and the evidence, to conjecture, then prove or test.

"Putting a flag on a square is a theorem—you know there's a bomb there," Struthers explained.

Students ended up learning reasoning techniques, such as proof by contradiction or the role of counterexamples, that not only apply to Minesweeper but also were useful for proving theorems later in their mathematics courses.

See also "Minesweeper and Hypothetical Thinking Action Research & Pilot Study" by Jacob J. Walker.

Originally posted May 3, 1999

Reference:

Lock, P.F., and A.A. Struthers. 1999. Using the game Minesweeper to introduce students to proofs. Abstracts of Papers Presented to the American Mathematical Society 20(No. 1):189.

Mackenzie, D. 1999. Addicted to logic. American Scientist 87(May-June):217.

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

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."

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

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