The Number Mysteries: A Mathematical Odyssey through Everyday Life (MacSci)
Page 17
For example, if the fortune-teller cast the hexagram
Figure 4.12
it would indicate “conflict.” But if the lines came out the other way around and you got
Figure 4.13
that would indicate “hidden intelligence.”
Leibniz was more interested in the fact that Shao Yong, a Chinese scholar of the eleventh century, had pointed out that each symbol could be attached to a number. If you write 0 for a broken line and 1 for a solid line, then reading the first hexagram from top to bottom would give you 111010. In decimal numbers, each position corresponds to a power of 10, and the number in that position tells you how many powers of 10 to take. So 234 is 4 units, 3 tens, and 2 hundreds.
But Leibniz and Shao Yong weren’t working in decimal, but binary, where each position is a power of 2. In binary, the number 111010 stands for no units, one lot of 2, no 4s, one lot of 8, one lot of 16, and one lot of 32. Add these up and the total is 2 + 8 + 16 + 32 = 58. The beauty of binary is that you need only two symbols, rather than the ten in decimal, to represent any number. Two lots of (decimal) 16 become one lot of the next power of 2, which is 32.
Leibniz saw that this way of representing numbers was very powerful if you wanted to mechanize calculations. There are very simple rules for adding binary numbers. At each position, 0 + 1 = 1, 1 + 0 = 1, and 0 + 0 = 0. The fourth possibility is 1 + 1 = 0, with the secondary effect that a 1 is carried over and added to the next position to the left. When we add 1000 to 111010, for example, we get a domino effect as the 1s cascade up the number:
1000 + 111010 = 10000 + 110010 = 100000 + 100010 = 1000000 + 000010 = 1000010
Leibniz designed beautiful mechanical calculators. One of them used ball bearings to represent 1s and an absence of balls to represent 0s, turning the process of addition into a fantastic mechanical pinball machine. Leibniz believed that “it is unworthy of excellent men to lose hours like slaves in the labour of calculation which would safely be relegated to anyone else if machines were used.” I think most mathematicians would agree.
Figure 4.14 A reconstruction of Leibniz’s binary calculator.
It wasn’t only numbers that people started to represent as strings of 0s and 1s, but letters, too. Although humans found Morse code a very powerful tool for communicating, machines were less adept at picking up the subtle differences between dots and dashes spelling out letters and knowing when one letter had finished and the next had begun.
In 1874, Émile Baudot proposed coding each letter of the alphabet as a string of five 0s and 1s. By making every letter the same length, it was clear where the last letter finished and the next one began. Using five 0s and 1s allowed Baudot to represent a total of 2 x 2 x 2 x 2 x 2 = 32 different characters. The letter x + became the string 10111, for example, while y was 10101. This was a huge breakthrough, because messages could now be coded onto a paper tape on which holes were punched to represent 1s and blanks—the absence of a hole—represented 0s. A machine could read this tape and send the signal down a wire at high speed, and a teleprinter at the other end could automatically type out the message.
The Baudot code has since been superseded by a whole host of other codes that exploit the same idea of using 0s and 1s to represent everything from text to sound waves, and from JPEGs to movie files. Every time you log on to iTunes and download a Coldplay track, your computer receives a huge onslaught of 0s and 1s, which your MP3 player knows how to decode. Contained inside the numbers are the messages to tell your speaker or headphones how to vibrate so that you can hear Chris Martin’s dulcet tones. And it may have been the fact that in our digital age, the music is simply a stream of 0s and 1s that inspired the cover of Coldplay’s third album.
Figure 4.15 The cover of Coldplay’s third album used the Baudot code.
Baudot’s original code is the key to unlocking the secret message embedded in the cover’s graphic. The pattern can be divided into four columns with five blocks in each column. The colored blocks should be interpreted as 1s, and the gaps as 0s. Because it is sometimes hard to tell which way up the tape should be, the machine punches a fine dividing line between the upper two blocks and the three below. That’s why there’s a line separating the gray blocks and the colored blocks on the cover’s graphic.
The first column on the cover reads color-blank-color-color-color, which translates into 10111, the Baudot code for x. The last column becomes the Baudot code for y. The middle two columns are slightly more interesting. Five 0s and 1s gives you the possibility of 32 symbols, but quite often, we want more than this, since there are numbers, punctuation marks, and other symbols we might want to communicate. To cope with these demands, Baudot came up with a cunning way to expand the range. Just as a keyboard uses a shift key to get access to a whole range of other symbols using the same keys, Baudot used one of the string of five 0s and 1s as the equivalent of the shift key. So if you come across 11011, you know the next string will be from the extended set of characters.
And the second column on the cover is Baudot’s shift key. To decode the blank-blank-blank-color-color in the third column, we need to consult the extended character set, shown in Figure 4.16. I’m sure most people will be expecting to find the symbol for &. But 00011 stands not for &, but for the numeral 9. So the real title of Coldplay’s third album as encoded with the Baudot code is X9Y, not X&Y. Were the members of Coldplay playing a joke on us? Probably not. There is just one block difference between the Baudot code for 9 and &, so it was probably a mistake, which perfectly illustrates one of the problems with many of these codes: when you make a mistake, it’s difficult to tell. It’s in detecting errors such as this that the mathematics of codes truly comes into its own.
Figure 4.16 The Baudot code.
This website lets you create your own Coldplay album cover: www.ditonus.com/coldcode. Or use your smartphone to scan this code.
WHICH OF THESE NUMBERS IS CODE FOR A BOOK: 0521447712 OR 0521095788?
I’m sure you’ve seen the ISBN—the International Standard Book Number—on the back of every book. In its ten digits, the ISBN uniquely identifies the book, as well as tells you its country of origin and its publisher. But that’s not all this code does. The ISBN has a little magic worked into it.
Say I want to order a book and I know its ISBN. I type the number in, but I’m in a hurry and I make a mistake. You might think I’d end up with the wrong book, but that won’t happen because ISBNs have an amazing property: they can detect errors in themselves. Let me show you how.
Here are some genuine ISBNs from some of my favorite books:
Table 4.5
Underneath each digit, I’ve multiplied the digit by its position in the code. So in the first ISBN, 0 gets multiplied by 1, 5 by 2, 2 by 3, and so on. Then I’ve added up all these new numbers and written the total at the end of the row. Notice anything about all these numbers that have been cooked out of the ISBN? Here are some more numbers you get by performing this calculation on other real ISBNs: 264, 99, 253.
Have you spotted the pattern? The calculation always gives a number that’s divisible by 11. This is not an amazing coincidence, but an example of cunning mathematical design. It’s only the first nine digits that contain the information about the book. The tenth digit is included just to make this total number extracted from the ISBN divisible by 11. You might have spotted that some books have an X instead of a number as their tenth digit. For example, another of my favorite books has ISBN 080501246X. The X actually stands for 10 (think roman numerals). In this case, you needed to add a multiple of 10 to the end of the ISBN to make the number you get from the ISBN divisible by 11.
If I get one of the digits wrong when I type out my ISBN, the calculation will give me a number that isn’t divisible by 11, and the computer will know that I’ve made an error and ask me to type it in again. Even if I get two digits the wrong way around, which people often do when typing a number, it will also pick up this mistake, and rather than sending me the wrong book, it will ask
me to send the correct ISBN. Pretty clever stuff. So now you can check which of the numbers in the title of this section is really the ISBN of a book and which one is the imposter.
With so many books continuing to be published, ISBNs were starting to run out. So it was decided that from January 1, 2007, ISBNs would have 13 digits. Twelve digits would once again identify the book, publisher, and country of publication, and the thirteenth would keep track of any errors that might creep in. But divisibility by 10 rather than 11 is the key to the 13-digit ISBNs now used by publishers. Look at the ISBN for this book, which you can find on the back. It has 13 digits. Add up the second, fourth, sixth, eighth, tenth, and twelfth digits and multiply the sum by 3. Now add on the other digits. The total will be divisible by 10. If you make a mistake in writing down the ISBN, the calculation will often give you a number not divisible by 10.
HOW TO USE CODES TO READ MINDS
You will need 36 coins to perform this trick. Give your unsuspecting friend 25 of the coins and ask him to arrange the coins in a 5 x 5 grid, with heads and tails showing at random. He might lay down the coins like this:
Table 4.6
Now you say, “In a minute, I’m going to ask you to turn over one of these coins—a head or a tail. Then I’ll read your mind and tell you which of the coins you turned over. Now, I might be able to remember the order of the 25 coins, so let’s make it even more difficult for me and make the square even bigger.”
Next, you add more coins, apparently at random, to make an extra row and column and increase the grid to 6 x 6 = 36 . . . except that you aren’t adding the extra coins randomly at all. What you do is count how many tails there are in each row and each column, starting with the first column. If there are an odd number of tails in this first column, then place the extra coin at the bottom of this column with a tail showing. If there are an even number of tails (0 counts as an even number for this purpose), place the extra coin at the end of this column with a head showing.
Do the same for each column, and then add a coin at the end of each row using the same criterion. There will now be a space at the bottom right to fill to complete the square. Make it a head or a tail according to whether the column above it has an even or odd number of tails. Interestingly, this will also record the parity (i.e., whether even or odd) of the number of tails in the bottom row, too. Can you prove that this is always true? The trick lies in spotting that this number is telling you whether there are an odd or even number of tails in the 5 x 5 grid.
Anyway, the grid now looks like this:
Table 4.7
Now you are ready to do the trick. Turn your back and ask your friend to turn over one coin so that it changes from a head to a tail or vice versa. When that’s done, turn around again. Concentrate on the grid and announce that you’re now going to read your friend’s mind and identify the coin that was turned over.
Of course, you aren’t reading your friend’s mind at all. You go back to the original 5 x 5 block of numbers and count the heads and tails in each column and row. You note whether there are an odd or even number of tails and check it against the heads and tails you added, because they indicate the parity of tails in each column. Now that your friend has turned over one of the coins in the 5 x 5 grid, there will be one row and one column in which the coins you added give a false reading. Look at where that column and row intersect and you will find the coin that was turned over.
You should now be able to identify which coin has been changed in the grid:
Table 4.8
The first column in the 5 x 5 grid has an even number of tails, but the coin you added at the bottom of this column was a tail, indicating that there were originally an odd number of tails. So the first column contains the coin turned over by your friend.
Now for the rows. It is in the second row that things don’t match up: there are an odd number of tails, but your “check digit” indicates that there should be an even number. Now you can read your friend’s mind: “You turned over the coin in the first column, second row.” A round of applause from the impressed audience.
What happens if your friend has turned over one of the coins you put down? No problem. Now the bottom right corner won’t indicate the parity of either the last row or the last column. If it doesn’t match the last row, you’ll know that one of the entries in the last row has been changed, so you check each of the columns to see which one doesn’t match up. If you find that it’s the sixth column that doesn’t match, then it’s actually the coin in the bottom right corner that got turned.
Here’s the grid again, but with one of your coins turned over. Can you identify it?
Table 4.9
It’s the one at the top right corner. The head at the bottom right corner tells you that there should be an even number of tails sitting above it in the last column—but there are an odd number. Now check the rows. The first row doesn’t match up because the head at the end of the row is saying that there should be an even number of tails to the left of it. But there are an odd number, and that tells you that the top right coin was turned over.
This is the basis of what is called an error-correcting code, which is used by computers to correct errors in messages that might have crept in during transmission. Change the heads and tails into 0s and 1s, and suddenly, the grid becomes a digital message. For example, each column in the 5 x 5 grid that is laid down at the beginning of the trick could represent a character in the Baudot code, and the grid in the trick would then be a message five characters long. The extra columns and rows are added by the computer to keep track of any errors.
So if we wanted to send the coded message on the front of Coldplay’s third album, we could use a similar trick applied to a 5 x 4 grid to detect when and where any error occurred. Here is the album cover as it should have been, with the colored blocks changed to 1s and the gaps to 0s:
Table 4.10
Now we add an extra column and row with 0s and 1s to indicate whether each column or row has an even or odd number of 1s:
Table 4.11
Now let’s imagine that there’s been an error during transmission and one of the numbers got flipped, and the graphic designer received the following message:
Table 4.12
By using the check digits in the last column and row, the graphic designer can spot the error. The second row and the third column don’t match up.
Error-correcting codes like this are used in everything from CDs to satellite communications. You know what it’s like when you’re talking to someone on a phone and you can’t make out everything that person says. When computers talk to each other, they have the same problem, but by using clever mathematics, we’ve managed to come up with ways to encode data so that we can get rid of this interference. This is what NASA did when the spacecraft Voyager 2 sent back its first pictures of Saturn. By using an error-correcting code, NASA was able to turn fuzzy images into crystal-clear pictures.
HOW TO TOSS A COIN FAIRLY ACROSS THE INTERNET
Error-correcting codes help to communicate information clearly. But often, we want to use our computers to send secret information. In the past, Mary Queen of Scots, Lord Nelson, or anyone else intending to exchange secret messages needed to meet in advance with their agent to agree on the code that both parties would be using. In our modern computer age, we often need to send secret messages. When we’re shopping online, we send our credit card details to people we’ve never met before, to websites we’ve just clicked on. Doing business on the Internet would be impossible with the old cryptography, where everyone first had to meet face-to-face. Luckily, mathematics provides a solution.
To explain the idea, let’s start with a simple scenario. I want to play chess with someone over the Internet. I live in London, and my opponent is in Tokyo. We want to toss a coin to see who goes first. “Heads or tails?” I email my opponent. He writes back to say that he calls heads. I toss the coin. “Tails,” I email back. “I start.” Is there any way we can make sure I haven’t cheated
?
Amazingly, you can toss a coin fairly over the Internet, and it’s the mathematics of prime numbers that makes it possible. All primes are odd except for 2 (which is the odd prime because it’s the only even one). If we divide one of these odd prime numbers by 4, it leaves a remainder of 1 or 3. For example, 17 divided by 4 leaves a remainder of 1, and 23 divided by 4 has a remainder of 3.
As we know from chapter 1, the ancient Greeks proved two thousand years ago that there are an infinite number of primes. But are there an infinite number of primes that leave a remainder of 1 upon division by 4, or an infinite number that leave a remainder of 3? This was one of the questions that Pierre de Fermat challenged mathematicians with 350 years ago, though an answer had to wait until the nineteenth century and for the German mathematician Gustav Lejeune Dirichlet. He introduced some extraordinarily complicated mathematics to show that half the primes leave a remainder of 1 and half the primes leave a remainder of 3—no remainder is favored over the other. Just what mathematicians imply by “half” when they talk about the infinite is complicated. But essentially, it means that when you look at the primes that are less than any particular number, then pretty much half of them will have a remainder of 1 upon division by 4.
So whether a prime leaves a remainder of 1 or 3 upon division by 4 is no less “biased” than whether a fair coin lands heads or tails. For the purpose of our coin-tossing problem, let’s associate heads with the primes with a remainder of 1 upon division by 4, and tails with primes that have a remainder of 3 upon division by 4. Now here comes the clever bit of math. If I take two prime numbers, say 17 and 41, both from the heads pile—the ones that have a remainder of 1 upon division by 4—and multiply them together, the answer also has a remainder of 1 upon division by 4: for example, 41 x 17 = 697 = 174 x 4 + 1. If I take two primes, say 23 and 43, both from the tails pile and both with a remainder of 3 upon division by 4 . . . well, it’s not what you might be expecting. When I multiply them together, they also give a number that has a remainder of 1 upon division by 4: in this case, 23 x 43 = 989 = 247 x 4 + 1. So the product of the primes gives no hint about whether they’re from the heads pile or the tails pile. This is what we can exploit to play “Internet heads or tails.”