Scissors and Cezanne
The game of rock-paper-scissors has been used to decide disputes from fights in the playground to battles in the boardroom. Two auction houses, Sotheby’s and Christie’s, famously settled a dispute over the right to auction a collection of impressionist paintings by Cézanne and Van Gogh by a single game of rock-paper-scissors.
Each auction house was given the weekend to come up with its choice of play. At great expense, Sotheby’s hired a team of top-ranking analysts to produce a winning strategy. The analysts concluded that because it’s a game of chance, a random choice is as good as any. So they went with paper. Christie’s simply asked the 11-year-old daughter of an employee what she would do. “Everyone always assumes you’ll do rock, so they’ll choose paper. So go with scissors,” she told them. Christie’s won the contract.
It just goes to show that math won’t always give you the edge.
HOW GOOD ARE YOU AT RANDOMNESS?
Our intuition is generally very bad at realizing the consequences of randomness. I’m going to offer you a bet. I’m going to toss a coin ten times. You give me $1 if there’s a run of three heads or three tails. If there isn’t, I’ll give you $2. Would you take the bet?
What if I upped what I offer to pay you to $4? I reckon that if you were unsure the first time, you would probably now take me on. After all, how likely is it that you’d get three heads or three tails in a row in ten tosses of a coin? Amazingly, you will get such a run over 82 percent of the time. So even if I’m paying out at $4 for no sequence of three, in the long run, I’ll still be making a profit.
The exact probability of tossing a coin ten times and getting a run of three heads or three tails in a row is . Here are the gory details of how to calculate this probability. Strangely enough, the Fibonacci numbers we met in chapter 1 are the key to working out the chances—yet more confirmation that these numbers are everywhere. If I toss a coin N times, there are 2N ways the coin could land. We’ll say that gN is the number of combinations with no runs of three heads or three tails: these are the combinations in which you will win the bet. We can calculate gN by using the rule for the Fibonacci numbers:
g N = g N – 1 + g N – 2
To get the numbers going, you just need to know that g1 = 2 and g2 = 4, because after one or two tosses, no combination can have three heads or three tails as we haven’t tossed the coin three times yet. So the sequence goes 2, 4, 6, 10, 16, 26, 42, 68, 110, 178, . . . There are therefore 1,024 – 178 = 846 different ways that ten coins can land and have a run of three heads or three tails. So the probability is , roughly 82 percent, that such a run would occur—and that I would win.
Why is the Fibonacci rule the key to calculating gN? Take all the combinations of N – 1 tosses with no runs of three heads or three tails. There are g N – 1 of these. Now make the N th toss the opposite of the (N – 1)th toss. Next, take all the combinations of N – 2 tosses with no runs of three heads or three tails. There are g N – 2 of these. Now make the (N – 1)th and N th tosses the opposite of the (N – 2)th toss. In this way, you generate all the combinations of N tosses with no runs of three heads or three tails.
HOW CAN I WIN THE LOTTERY?
This is the question I get asked the most when I say that I spend my life playing with numbers. But just like tossing a coin, the numbers that have come up in the previous weeks’ draws cannot influence the numbers that come up next Saturday. That’s what it means to be random, but some people will never be convinced.
Italy’s state-run biweekly lottery draw takes place in ten cities across the country, and participants have to choose numbers from 1 to 90. At one point, the number 53 ball had refused to appear in Venice after nearly two years of lottery draws. Surely, after so long, it was certain to come up the following week—or so thought many Italians. One woman bet all her family’s savings on 53 coming up. When it failed yet again to appear, she drowned herself in the sea. Even more tragically, a man shot his family and then himself after running up huge debts betting on the certainty of 53 appearing. It is estimated that Italians invested $3.8 billion—an average of $240 per family—on 53 being a winner.
There were even calls for the government to ban 53 from the draw to put an end to the country’s obsession with the number. When the dam finally burst on February 9, 2005, and the 53 ball popped up in the draw, $640 million was paid out to an unspecified number of lottery players. Inevitably, some people accused the state of deliberately withholding the 53 ball to avoid a huge payout, and it wasn’t the first time such a rumor had circulated. In 1941, the number 8 ball had failed to appear after 201 draws in Rome. Many believed that Mussolini had fixed its nonappearance and was siphoning off the nation’s bets on the 8 ball to help finance Italy’s war effort.
Now, to see how lucky you are, let’s play our own little lottery. I can’t promise you millions of dollars, but the good news is that this lottery is free to enter. To play Number Mysteries lotto, start by choosing six numbers from the 49 numbers on this ticket:
Figure 3.2
Chosen your numbers? To see whether you’ve won, go to the website www.random.org/quick-pick/, or use your smartphone to scan this code.
Select 1 ticket, United Kingdom, National Lottery, and click on “Pick Tickets.” If you don’t have Internet access, there is a predetermined choice of six numbers at the end of this chapter. Don’t cheat, though. Like solving a math puzzle, it’s much more fun to get the answer right yourself rather than looking it up.
What are your chances of picking all six numbers correctly and winning the lottery? To calculate the odds, you need to work out how many different possible choices of six numbers there are—call it N. Then the odds that you’ve chosen the winning numbers are 1 in N. As a warm-up, let’s start by looking at how many different ways there are to pick two numbers. There are 49 choices for your first number. For the second, you now have a choice of 48 numbers. Each choice of the first number can be paired with one of the remaining 48 numbers. So that gives us 49 × 48 possible pairs of numbers. But hold on—we’ve actually counted each choice twice. For example, if you chose 27 as your first number and then 23 as your second, that’s the same as if you’d chosen 23 first and then 27. So there are only half as many pairs of numbers as we first thought, which means that the number of pairs of numbers you can choose is ½ × 49 × 48.
Now to six numbers. There are 49 choices for the first number, 48 for the second, 47 for the third, 46 for the fourth, 45 for the fifth, and finally 44 choices for the last number. So that’s 49 × 48 × 47 × 46 × 45 × 44 combinations of six numbers—except that again, we’ve counted some combinations more than once. How many times, for example, have we counted the combination 1, 2, 3, 4, 5, 6? Well, we could have chosen any of these six as our first number (say, 5). That would leave five numbers as possible second choices (say, 1), four numbers for the next choice (say, 2), three for the next (say, 6), and two choices for the penultimate number (say, 4). The final number, then, has to be the one that’s left (in this case, 3). So we could have picked the six numbers 1, 2, 3, 4, 5, 6 in 6 × 5 × 4 × 3 × 2 × 1 different ways. This is true for any combination of six numbers. So we need to divide 49 × 48 × 47 × 46 × 45 × 44 by 6 × 5 × 4 × 3 × 2 × 1 to get the total possible number of ways to fill out the lottery ticket. The answer? 13,983,816.
This number also tells us your chance of winning, since it’s the total number of possible combinations of the ways the balls come out of the lottery machine. In other words, the chance of you choosing the correct combination in the total number of possible combinations is 1 in 13,983,816.
What are the chances that you got no numbers correct? We work it out the same way. Your first number has to be one of the 43 numbers that don’t get drawn, your second number one of the remaining 42, and so on. This gives 43 × 42 × 41 × 40 × 39 × 38 different combinations. But each combination has been counted 6 × 5 × 4 × 3 × 2 × 1 times. So the total number of combinations that have no numbers correct is 43 × 42 ?
? 41 × 40 × 39 × 38 divided by 6 × 5 × 4 × 3 × 2 × 1, or 6,096,454. So just under half the number of possible choices will have no numbers that match the winning numbers. To calculate your chance of not getting any numbers right, divide 6,096,454 by 13,983,816. That gives approximately 0.436, or a 43.6 percent chance that you’ve drawn a complete blank.
So you have a 56.4 percent chance of getting at least one number right. What are the chances of getting two numbers right? To calculate this, you need to find the number of combinations with two correct numbers. You have six choices for the first correct number and another five for the second number. That’s 6 × 5, but again you need to divide by 2 to correct for counting things twice. For the four numbers you get wrong, you have a choice of 43 × 42 × 41 × 40, which you need to divide by 4 × 3 × 2 × 1, which is the number of ways you’ve counted things twice. So the number of combinations with exactly two numbers right is
Table 3.1
Table 3.1 shows you the chances of guessing from zero to six numbers correctly, all calculated in the same way. To put these figures into some sort of perspective, if you bought a lottery ticket every week, then after just over a year, you might expect to have one ticket with at least three numbers correct. After about 20 years, you might have seen one ticket with at least four numbers correct. King Alfred, if he’d bought a ticket every week, might expect by now to have seen one ticket with five numbers correct. And if the first thought that entered the head of the first Homo sapiens was to pop down to the local newsstand and start buying a lottery ticket every week, then by now, he might have won the big prize once.
If you are ever lucky enough to win the big prize, then what you don’t want to happen is what transpired in the United Kingdom on January 14, 1995, in just the ninth week of the National Lottery. The jackpot that week was over $25 million. As the six numbered balls came out of the lottery machine, the winners must have been jumping up and down on their couches and shouting for joy. But when they came to claim their prize, they each discovered that he or she had to share the jackpot with another 132 holders of winning tickets. Each winner got a paltry $195,960.
How come so many people guessed the correct combination? The reason goes back to a point I made when we were looking at the game of rock-paper-scissors: we humans are notoriously bad at choosing random numbers. Given that fourteen million people play the UK National Lottery every week, many will find themselves being drawn to very similar numbers, such as the lucky number 7 or dates of birthdays or anniversaries (which exclude the numbers 32–49). One thing in particular that typifies many people’s choices is the desire to spread their numbers out evenly.
Here are the winning numbers in week 9 of the lottery:
Figure 3.3
This even spacing of numbers is not particularly characteristic of randomness: numbers are as likely to be clumped together as not. Of the 13,983,816 different possible combinations of lottery tickets, 6,924,764 will have two consecutive numbers. That’s 49.5 percent—very nearly half of all combinations. For example, in the previous week’s draw, the numbers 21 and 22 came up. The week after, 30 and 31 appeared.
But don’t get too addicted to consecutive numbers. You might think that 1, 2, 3, 4, 5, 6 is a clever choice. After all, by now you will hopefully appreciate that this combination is as likely as any other (i.e., extremely un likely!). If you won the jackpot with this combination, you’d hope to walk away with the whole pot. But apparently, over ten thousand people in the United Kingdom choose this combination each week—which just goes to show how clever the UK population really is—so you’d have to share your winnings with ten thousand other clever people.
Why Numbers Like to Clump
Here’s how to calculate how many lottery tickets have two consecutive numbers. Mathematicians often use a clever trick of looking at a problem the other way around, and that’s what you can do here. First, you count the tickets with no consecutive numbers, then subtract the result from the total number of possible combinations to find how many combinations have consecutive numbers.
First, pick any six numbers from the numbers 1 to 44 (you’ll see in a moment why you’re only allowed numbers up to 44, not 49). Call your choice of numbers A(1), . . . , A(6), with A(1) the smallest and A(6) the largest. Now, A(1) and A(2) could be consecutive, but A(1) and A(2) + 1 won’t be. A(2) and A(3) could be consecutive, but A(2) + 1 and A(3) + 2 won’t be. So if you take the six numbers A(1), A(2) + 1, A(3) + 2, A(4) + 3, A(5) + 4, and A(6) + 5, none of them will be consecutive. (The restriction of choosing numbers up to 44 becomes clear now, because if A(6) is 44, then A(6) + 5 is 49.)
By using this trick, you can generate all the tickets with no consecutive numbers simply by picking six numbers from 1 to 44 and spreading them out by adding a little to each one. And we find that the number of tickets with no consecutive numbers is the same as the number of combinations of six numbers from 1 to 44. There are
such choices. So the number of tickets with consecutive numbers is
13,983,816 – 7,059,052 = 6,924,764
HOW TO CHEAT AT POKER AND DO MAGIC USING THE MILLION-DOLLAR PRIME-NUMBER PROBLEM
Crooked gamblers and magicians don’t shuffle cards the way the rest of us do. But with hours of practice, it’s possible to learn how to do something called the perfect shuffle. In this shuffle, the pack is cut exactly in two and then the cards are interwoven one at a time from the two piles of cards. If you’re playing poker, this shuffle is very dangerous.
Let’s imagine four people sitting around the poker table: the dealer, his accomplice, and two unsuspecting gamblers who are about to be stung. The dealer puts four aces on top of the pack. After one perfect shuffle, the aces are two cards apart. After another perfect shuffle, the aces are four cards apart—perfectly placed for the dealer to deal his accomplice a hand with four aces.
The perfect shuffle comes into its own in the hands of a magician who can exploit an interesting property that it has. If you take a pack of 52 cards and do the perfect shuffle eight times, then amazingly, the cards all return to their original positions in the pack. To the onlooker, the shuffling seems to have totally randomized the pack. After all, eight shuffles done by a normal gambler is more than most do at the beginning of a game. In fact, mathematicians have proved that it takes only seven shuffles by a normal cardplayer for the pack to lose all of its original structure and become random. But the perfect shuffle is no ordinary shuffle. Think of the pack of cards as being something like an eight-sided coin, and the perfect shuffle as being the rotation of the coin by an eighth of a turn. After eight rotations, the coin comes back to its starting position.
How many times would you have to do the perfect shuffle on a pack with more than 52 cards for them to return to their original positions? If you add two jokers and do the perfect shuffle with a pack of 54 cards, it will take 52 shuffles to come full circle. But if you add another ten cards to make 64, it will now take just six perfect shuffles to return the pack to its original order. So what is the math that tells you how many times you need to perfectly shuffle a pack of 2N cards (it has to be an even number) to return all the cards to their starting positions?
Number the cards 0, 1, 2, and so on up to 2N – 1, and you will see that with the perfect shuffle, the position of each card essentially doubles each time. Card 1 (which is actually the second card) becomes card 2. After another shuffle, card 2 becomes card 4, then card 8. The math is easier if we give the first card the number 0.
Where do the cards farther down the pack go? The way to work out the location of each card is to think of a clock with 2N – 1 hours on it, so a 52-card pack is like a clock with hours from 1 to 51. If you want to know where card 32 went, then double 32, which you do by starting at hour 32 and counting 32 hours on, which gets you to 13 o’clock. To work out how many times I have to do the perfect shuffle to get all the cards back to their original position, I have to work out how many times I have to double numbers on this clock for them to return to the original positi
on. Actually, I just have to look at the number 1 and work out how many times I have to double 1 to get back to 1. On the clock with 51 hours, here is where I get by repeatedly doubling the 1:
1→2→4→8→16→32→13→26→1
And what works for 1 will work for all the other numbers, because essentially, doing eight perfect shuffles is the same as multiplying the positions of the cards by 28, which is the same as multiplying by 1—that is, it leaves each card where it is.
What is the maximum number of times you would have to shuffle the pack to get back to the original order? Pierre de Fermat proved that if 2N – 1 is prime, and you keep doubling on a 2N – 1 clock, then after 2N – 2 doublings, you’ll definitely be back where you started. So for a 54-card pack, since 54 – 1 = 53 is prime, 52 perfect shuffles will certainly be enough.
We need a slightly more complicated formula to calculate the maximum number of perfect shuffles if 2N – 1 is not prime. If 2N – 1= p x q, where p and q are prime, then (p – 1) × (q – 1) perfect shuffles is the maximum needed to return the pack to its original order. So for a 52-card pack, 52 – 1 = 3 × 17, and so (3 – 1) × (17 – 1) = 2 × 16 = 32 perfect shuffles will certainly be enough—but, in fact, you can get away with just eight perfect shuffles. (In the next chapter, I will prove Fermat’s bit of magic and explain how the same bit of mathematics is at the heart of the codes used to protect secrets on the Internet.)