8

Bingo Befuddlement

8.1 THE PROBLEM

In the introduction (I.7), I discussed nontransitive dice. Nontransitivity can also occur in many other situations, far removed from dice. A game that kids love to play (some adults, too!), rock, paper, scissors, is nontransitive because while the rock breaks the scissors and the scissors cuts the paper, the paper covers the rock. For a more analytical example, imagine that we have nine tennis players ranked 1, 2, 3, 4, 5, 6, 7, 8, and 9 in increasing order of skill (8 always beats players 1 through 7, and always loses to player 9). Imagine further that these nine players form three teams A, B, and C, each with three players, as shown below:

(It is interesting to note in passing that this particular structure is the famous Lo Shu, the unique three-by-three normal magic square that was known to the Chinese thousands of years before Christ [normal means the square is formed by using consecutive integers, starting with 1]. As it happens, this has absolutely nothing to do with what I am about to show you; it’s simply a historical aside that I couldn’t resist mentioning.)

These three teams, A, B, and C, engage in a series of matches, where a match means each player on a team plays one game with all the players on the opposing team. That is, a match consists of nine games. Now, notice that A wins a match with B by a score of 5 to 4 (8 wins all three of his games, 1 never wins, and 6 wins two games). Also, B wins a match with C, also by a score of 5 to 4 (3 wins one game, 5 wins two games, and 7 wins two games). So, A beats B and B beats C. Does that mean that A beats C? No, because C beats A by a score of 5 to 4 (4 wins one game, 9 wins three games, and 2 wins one game). The match results are not transitive. Very surprising, I think, but the numbers are beyond reproach.

In this new puzzle you’ll see yet another case of nontransitivity that will be much more challenging to solve. In the cases of the dice and the tennis team problems we could study the interactions involved literally by counting. In this new problem there are so many possibilities that, unless you are a very patient person, you’d go quietly insane trying to do the arithmetic by hand. (Try it and see!) Here we’ll find a computer to be our salvation. Another interesting twist to what is a probabilistic problem is that the computer analysis will not produce probabilistic estimates but rather will give us exact results! Here’s the problem.

We start with four two-by-two bingo cards, A, B, C, and D. Two players each select adjacent cards, and then the numbers 1 through 6 are called in random order, one after the other, without repetition. That is, after six calls the numbers are exhausted. The first player to complete a horizontal row on his card wins. The claim here is that, on average, A beats B, B beats C, C beats D, and—here’s the big claim—if we complete the loop, then D beats A. The problem is to confirm this claim, and to find the probabilities by which the winning cards beat the losing cards. It’s important to realize that ties are possible (both players yell “Bingo!” simultaneously). For example, suppose cards A and B are being played. Then all sequences of called numbers that start with 1, 4, 2 result in a tie. Or if cards B and C are being played, all sequences of called numbers that start with 2, 5, 4 result in a tie. So don’t forget about the possibility of ties.

8.2 COMPUTER SIMULATION

Since the six numbers 1 through 6 are called without repetition, there is only a finite number of possible sequences; specifically, there are 6! = 720 sequences. Although finite, this is far too many to allow a reasonable hand calculation of how each pair of cards plays for each possible sequence, but it’s a simple task for a computer. The MATLAB^® code bingo.m does just that, playing each and all of the 720 possible sequences for any two given cards, all the while keeping track of which card wins on each sequence (or if a tie occurs).

When run for the given pairs, the code determined the probabilities we are after:

while the reverse probabilities are

and that for each of the card pairings,

Here’s a walkthrough on how bingo.m works. First I’ll give a brief description of the general approach. The code plays cards X and Y against each other, where X and Y are each set equal to one of the cards A, B, C, or D (the particular choice is yours). As the numbers of a sequence are called, each sub-square in the X and Y cards is examined to see if it matches the current called number, and if it does, the sub-square entry is set equal to zero. The code “knows” when a card achieves bingo when one of the sums of the card’s rows equals zero (this approach uses the advanced mathematical fact that 0 + 0 = 0). If that happens for just one of X and Y, then that card wins. If both X and Y achieve a zero-sum row at the same time, we have a tie. A win or a tie is certain to occur by the end of any sequence. The code then restores X and Y to their initial card values (which were destroyed as sub-square entries were set to zero), and a new sequence is played.

Now, here’s a bit more detail. The first two lines of the code define A, B, C, and D. The next line uses MATLAB^®’s wonderful command perms to generate a matrix of all the permutations of the components of the vector that is the argument of the command. That is, P is a 720-by-6 matrix whose 720 rows are the permutations of the integers 1 through 6. The code then sets x (the number of times card X wins) to zero, y (the number of times card Y wins) to zero, and ties (the number of times X and Y tie) to zero. The code then begins to loop through each of the rows of P, using the entries of a row as the current calling sequence, as follows.

After setting X = D (or X to any of the other possible cards) and Y = A (or Y to any of the other possible cards), row is set equal to the next available row of P, xbingo and ybingo are both set equal to zero (xbingo = 1, for example, means X has achieved bingo), and keepplaying is set equal to 1. The variable i is set equal to 1, which will step the code through the components of row to generate the calling sequence.

A while loop is then entered and, as long as keepplaying remains equal to 1, the components of row are called, one after the other; each time the appropriate sub-square of X and/or Y is set to 0. Then the row-sums of X and Y are calculated and, if a zero sum is found, either (or both) of xbingo and ybingo is (are) set equal to 1. (If neither is set equal to 1, then i is increased by one and the next component in row is called.) If both are equal to 1, then we have a tie (and tie is increased by one). If only one is equal to 1, then we have a win (and either x or y is increased by one). In any case, if bingo has occurred, then keepplaying is set equal to 0, which then causes the code to exit the while loop. This reinitializes the code variables (in particular, X and Y), and the next row of P is played.