100 Essential Things You Didn't Know You Didn't Know (10 page)

Surprisingly, ‘hard’ problems are not necessarily horribly complicated or mind-bogglingly difficult. They just involve a lot of possibilities. Multiplying together two large prime numbers is a computationally ‘easy’ task. You can do it in your head, with pencil and paper or on a calculator, as you wish. But if you give the answer to someone else and ask them to find the two prime numbers that were used in the multiplication, then they might be facing a lifetime of searching with the world’s fastest computers.

If you want to try one of these ‘hard’ problems for yourself, one that sounds deceptively easy, then find the two prime numbers that add up to give 389965026819938.
^fn1

These ‘trapdoor’ operations – so called because, like falling through a trapdoor, it is so much easier to go in one direction than in the reverse – are not altogether bad things. They make life difficult for us but they also make life difficult for people whose lives we are trying to make difficult for a very good reason. All the world’s principal security codes exploit trapdoor operations. Every time you shop online or extract cash from an ATM machine you are using them. Your pin number is combined with large prime numbers in such a way that any hacker or computer criminal wanting to steal your account details would have to factor a very large number into the two big prime numbers that were multiplied together to get at it. This is not impossible in principle, but it is impossible in practice in a sensible period of time. A criminal with the world’s fastest computer at his disposal might crack
the
encryption in several years, but by then the codes and account numbers would have been changed.

For this reason very large prime numbers are very valuable things, and some have been patented when written in a certain form. There is no limit to the number of prime numbers – they go on forever – but there is a largest one that we have been able to check for primeness by ensuring that it has no factors. There is no magic formula that can generate all prime numbers, and it is suspected that no such formula exists. If it did, and it was found, there would be a major crisis in the world. Any government agency that found it would undoubtedly keep it top secret. Any academic who found it and made it public without warning would bring the world tumbling down. All military, diplomatic and banking codes would become easily breakable by fast computers overnight. The world of online commerce would face a serious threat to its continued existence. We would have to move to iris, or fingerprint, or DNA-based recognition systems that relied on unique features of our biochemistry rather than numbers stored in our memories. But these new indicators would still need to be stored in a secure way.

The factoring of prime numbers is a ‘hard’ problem. Even if it is cracked and shown to be an ‘easy’ problem by means of a magic formula, you might think that we could just use some other ‘hard’ problem to encrypt sensitive information so that it still takes ages to reverse the operation and extract it. However, it is known that if one of the problems we believe to be ‘hard’ could be shown to be ‘easy’ by means of some new discovery, then that discovery could be used to turn all the other computationally ‘hard’ problems into ‘easy’ ones. It really would be a magic bullet.

^fn1
The answer is 5569 + 389965026814369.

28

Is This a Record?

I always thought that record would stand until it was broken.

Yogi Berra

Records – remember those those little discs of black vinyl that your parents owned that made a noise when spun on a turntable at high speed? Well, mathematicians are more interested in the other sort of records: the biggest, the smallest and the hottest. Are they predictable in any way?

At first you might think not. True, they follow a trend of getting ‘better’ – they wouldn’t be records if they didn’t – but how could you predict whether a Michael Johnson or an Ian Thorpe was going to come along and break record after record? Amazingly, the women’s world record in the pole vault was broken on eight separate occasions by Yelena Isinbayeva in one year alone. Records like this are not random in a very important sense. Each new record is the result of a competitive effort that is not independent of all the previous attempts at the same feat. Pole vaulters learn new points of technique and continually train to improve their weaknesses and refine their technique. All you can predict about records like this is that they will be set again, eventually, although there might be a very long wait for the next one.

However, there are different sorts of records that arise in sequences of events that are assumed to be independent of each other. Good examples are record monthly rainfalls, record high or
low
temperatures in one place over hundreds of years, or the heights of the record highest tides. The assumption that each event is independent of its predecessors is a very powerful one that allows us to make a striking prediction about how likely it is that there will be a record – irrespective of what the record is for. It could be rain, snow, fall of leaves, water levels, wind speeds or temperature.

Let’s pick on the annual rainfall in the UK as our example. In the first year that we keep records the rainfall must be a record. In year two, if the rainfall is independent of what it was in year 1, then it has a chance of 1/2 of being a record by beating the year-1 rainfall and a chance of 1/2 of not beating the year-1 rainfall. So the number of record years we expect in the first two years is 1 + ½. In year 3 there are just two ways in which the six possible rankings (i.e. a 1 in 3 chance) of the rainfall in years 1, 2 and 3 could produce a record in year 3. So the expected number of record years after 3 years of record keeping is 1 + ½ + ⅓. If you keep on going, applying the same reasoning to each new year, you will find that after n independent years of gathering data, the expected number of record years is the sum of a series of n fractions:

1 + ½ + ⅓ + ¼ + . . . + 1/n

This is a famous series that mathematicians call the ‘harmonic’ series. Let’s label as H(n) its sum after n terms are totalled; so we see that H(1) = 1, H(2) = 1.5, H(3) = 1.833, H(4) = 2.083, and so on. The most interesting thing about the sum of this series is that it grows so very slowly as the number of terms increases,
^fn1
so H(256) = 6.12 but H(1,000) is only 7.49 and H(1,000,000) = 14.39.

What does this tell us? Suppose that we were to apply our
formula
to the rainfall records for some place in the UK from 1748 to 2004 – a period of 256 years. Then we predict that we should find only H(256) = 6.12, or about 6 record years of high (or low) rainfall. If we look at the rainfall records kept by Kew Gardens for this period then this is the number of record years there have been. We would have to wait for more than a thousand years to have a good chance of finding even 8 record years. Records are very rare if events occur at random.

In the recent past there has been growing concern around the world about the evidence for systematic changes in climate, so called ‘global warming’, and we have noticed an uncomfortably large number of local climatic records in different places. If new records become far commoner than the harmonic series predicts, then this is telling us that annual climatic events are no longer independent annual events but are beginning to form part of a systematic non-random trend.

^fn1
In fact, when n gets very large H(n) increases only as fast as the logarithm of n and is very well approximated by 0.58 + ln(n).

29

A Do-It-Yourself Lottery

The Strong Law of Small Numbers
: There are not enough small numbers to satisfy all the demands placed upon them.

Richard Guy

If you are in need of a simple but thought-provoking parlour game to keep guests amused for a while, then one you might like to try is something that I call the Do-It-Yourself Lottery. You ask everyone to pick a positive whole number, and write it on a card along with their name. The aim is to pick the smallest number
that is not chosen by anyone else
. Is there a winning strategy? You might think you should go for the smallest numbers, like 1 or 2. But won’t other people think the same, and so you won’t end up with a number that is not chosen by someone else. Pick a very large number – and there are an infinite number of them to choose from – and you will surely lose. It’s just too easy for someone else to pick a smaller number. This suggests that the best numbers are somewhere in between. But where? What about 7 or 11? Surely no one else will think of picking 7?

I don’t know if there is a winning strategy, but what the game picks up on is our reluctance to think of ourselves as ‘typical’. We are tempted to think that we could pick a low number for some reason that no one else will think of. Of course, the reason why opinion polls can predict how we will vote, what we will buy, where we will go on holiday, and how we will respond to an
increase
in interest rates is precisely because we are all so similar.

I have another suspicion about this game. Although there is an infinite collection of numbers to choose from, we forget about most of them. We set a horizon somewhere around 20, or about twice the number of people in the game, if it is larger, and don’t think anyone will pick anything bigger than this. We then exclude the first few numbers up to about 5 on the grounds that they are too obvious for no one else to choose as well and choose from those that remain with roughly equal probability.

A systematic study of preferences would involve playing this game many times over with a large sample of players (say 100 in each trial) to look at the pattern of numbers chosen and the winning choices. It would also be interesting to see how players changed their strategy if they played the game over and over again. A computer simulation of the game is not necessarily of any use because it needs to be told a strategy to adopt. Clearly the numbers are not chosen at random (in which case all numbers would get chosen with equal likelihood). Psychology is important. You try to imagine what others will choose. But the temptation to think that you don’t think like anyone else is so strong that almost all of us fall for it. Of course, if there really was a definite strategy for picking the lowest number, everyone would be acting logically to adopt it but that would prevent them choosing a number that no one else chose, and they could never win with that strategy.

30

I Do Not Believe It!

It is quite a three-pipe problem and I beg that you won’t speak to me for fifty minutes.

Sherlock Holmes

You are appearing live in a TV game show. The manic presenter shows you three boxes, labelled A, B and C. One of them contains a cheque made out to you for £1 million. The other two contain photos of the presenter. He knows which box contains the cheque, and that cheque will be yours if you pick the right box. You go for Box A. The presenter reaches for Box C and shows everyone that it contains one of the pictures of himself. The cheque must be in Box A or Box B. You picked Box A. The presenter now asks you if you want to stick with your original choice of Box A or switch to Box B. What should you do? Maybe you have an impulse that urges you to switch your choice to Box B, while another voice is saying, Stick with Box A; he’s just trying to make you switch to a less expensive option for his employers.’ Or perhaps a more rational voice is telling you that it can’t possibly make any difference because the cheque is still where it always was and you either guessed it right first time or you didn’t.

The answer is remarkable. You should switch your choice to Box B! If you do this you will
double
your chance of picking the box that contains the cheque. Stick with the choice of Box A and you have a 1/3 chance of winning the cheque; switch to Box B and the chance increases to 2/3.

How can this be? At first, there is a 1 in 3 chance that the cheque is in any box. That means a 1/3 chance that it’s in A and a 2/3 chance that it’s in B or C. When the presenter intervenes and picks a box, it doesn’t change these odds because he always picks a box that doesn’t contain the cheque. So after he opens Box C there is still a 1/3 chance that the cheque is in A but now there is a 2/3 chance that it is in B because it definitely isn’t in C. You should switch.

Still not convinced? Look at it another way. After the presenter opens Box C you have two options. You can stick with your choice of Box A and this will ensure you will win if your original choice was right. Or you can switch boxes, to B, in which case you will be a winner only if your original choice was wrong. Your first choice of Box A will be right 1/3 of the time and wrong 2/3 of the time. So changing your box will get the cheque 2/3 of the time while staying with your first choice will be a winning strategy only 1/3 of the time.

You should by now be convinced by this mind-changing experience.

31

Flash Fires

I will show you fear in a handful of dust

T.S. Eliot,
The Waste Land

One of the lessons that we have learned from a number of catastrophic fires is that dust is lethal. A small fire in an old warehouse can be fanned into an explosive inferno by efforts to extinguish it if those efforts blow large amounts of dust into the air where it combusts and spreads the fire through the air in a flash. Anywhere dark and unvisited – under escalators or tiers of seats, or in neglected storage depositories – where dust can build up unnoticed in significant quantities is a huge fire risk.

Why is this? We don’t normally think of dust as being particularly inflammable stuff. What is it that transforms it into such a deadly presence? The answer is a matter of geometry. Start with a square of material and cut it up into 16 separate smaller squares. If the original square was of size 4 cm × 4 cm, then each of the 16 smaller squares will be of size 1 cm × 1 cm. The total surface area of material is the same – 16 square centimetres. Nothing has been lost. However, the big change is in the length of the exposed edges. The original square had a perimeter of length 16 cm, but the separate smaller squares each have a perimeter of 4 cm and there are 16 of them, so the total perimeter has grown four times bigger, to 4 × 16 cm = 64 cm.