Innovation Through Accident



Crisis in Wonderland

 

Stupid Math Tricks

 

Paul Erdos (1913-1996) was one of the greatest mathematicians of all times, working with number theory. He has been called the mathematician of mathematicians and the oddball of oddballs. He lived for mathematics. He had no life, no home, no possessions, no interests other than mathematics and only spoke to people who loved mathematics. Everyone else, to use his description, was “dead”. He slept for 3 hours a day and spent the rest on mathematics. He ate very little (no time) and traveled widely with all his belongings in a plastic bag, looking for fellow mathematicians to live with for a few days (he really never had a home, but lived with whoever he could find). His hosts have said that he had no idea how to cut an apple or how to wash his underwear.

 

Mathematicians pride themselves as being the pursuers of the purest science of all sciences. So pure and so sublime is the purest form of mathematics, that it is blasphemy to ask “what is the use of this”. Practical applications are impure. But if course, mathematics shape out lives everyday. From buildings to toilets, from the cheap Chinese toys to supersonic aircraft, everything is crafted by mathematics.

 

An old joke is quite relevant. A man flying a hot air balloon got lost. So he descended and asked a woman walking in a field “Where am I?” She thought for some time and then replied. “In a hot-air balloon”. Immediately the balloonist realized she was a mathematician, for three reasons (1) She thought before replying (2) What she said was absolutely correct and (3) Her reply was totally useless.

 

However, much to the chagrin of real mathematicians, there is fun in mathematics. Paul Erdos would of course turn over in his grave if he heard that.

 

Marriage by Mathematics

 

People meet people, people marry people. When and how should someone decide to marry? Every time, John meets a suitable lady, he must make an important decision – to attempt to marry her or to move on to find a better mate. The problem is how does he know he will ever meet a better mate?

 

Lets do this mathematically. Suppose someone had 100 cards with 100 random numbers on them. He shows them to you one by one and you have to guess when you have seen the highest number in the whole pack (analogous to the best lady). The goal is to do it as soon as possible. You could wait till you have seen them all, then you will really find the largest number (in case of ladies, John has to wait his entire life to decide), but the sooner you make your move the better it is for you. Mathematicians have worked this out, and the best compromise is to pick the highest number after looking at 37 cards. That is about one third of your way into the game. Actually its not one third, but 1/e, where e is about 2.71828.

 

Suppose we assume the range of marriageable ages for women is about 18 to 40 and for men is about 20 to 45. Then a woman has 22 years to look for a mate, and a man has 25 years, but if a person waits too long, all the good ones will all be taken. Using the above strategy, the 1/e point for women is age 26.1 and for men is at age 29.1. Hence, this is the best time to take the plunge. The same theory, with a twist, can be used for arranged marriages. If you have gathered n prospects, make contact with the first random n/e prospects and then pick the best.

 

This technique is of course, quite useful in a variety of optimization problems.

 

The Birthday paradox

 

We are at a party. There are lots of people in a room. How many people must there be such that there are two people in the room with the same birthday (ignoring leap years). Of course, even if there are just 2 people, it is possible, though unlikely, that they will have the same birthday.

 

If there are 366 people then you are guaranteed to find at least 2 people sharing the same birthday. This is called the Pigeon Hole Principle, which states “If you stuff n pigeons into n-1 holes, then there must be a hole with more than one pigeon”.

 

However, there is an even more interesting situation. If there are just 23 people in a room, the probability of two people having the same birthday is more than half. This means, that quite often, in a gathering of over 23 people, there are people sharing the same birthday. In fact, if there are 40 people in a room, the probability of two people sharing a birthday is over 90%. Quite difficult to believe, but its true. This is called the Birthday Paradox.

 

Apart from the fun factor, the birthday paradox happens to be an important principle that is used to determine the difficulty of cracking certain encryption codes. That is, a code that looks difficult to crack, can be shown to be quite weak, using the Birthday Paradox.

 

Measuring a Wall

 

Watch Jim measure a wall. Jim is a Mathematician. He has this wall in his backyard, about 30 feet long, that he needs to measure. If he was an Engineer, he would get a foot-ruler and then use it repeatedly until he found the length of the wall. Since he is a Mathematician, he does not posses a foot-ruler.

 

So Jim goes to his neighbor and borrows a foot ruler, and places it against one end of the wall. Now, Jim realizes, one foot-ruler would not be enough, a lot of wall still remains to be measured. So he goes to another neighbor to get another foot-ruler. He places this ruler, after the first one, and realizes he needs more. By the time he finishes measuring the wall, he has borrowed 30 foot-rulers, from 30 neighbors.

 

Very pleased with himself, for having successfully performed an engineering feat, Jim goes out to return all the rules he has borrowed, but then he realizes he has no idea which ruler belongs to who. Being a good mathematician, he randomizes them (mathematical term for shuffling them), and returns them to random neighbors.

 

Now, here is the question. What is the chance that some neighbor gets his own ruler back? Probably pretty small. So lets ask the opposite question. “What is the chance that not a single neighbor got his own foot-ruler back?”. The probability of this happening should be quite high. And it should get higher the more neighbors there are—that is if he borrowed 100 rulers the chances of everyone getting wrong rulers would be even higher.

 

Actually it is not. The chance of no one getting the right ruler is quite low. It is about 37%, Which means, it is very likely (63%) at least one (or more) got the correct ruler. And this probability does not change even if the number of neighbors increase—in fact the larger the number of neighbors, the closer the probability is to 36.79%. Strange but true. Where did the 36.79% come from? It came from the very famous number, the number e. The probability for everyone getting the wrong ruler is 1/e, which is about 0.3679.

 

Six Degrees of Separation

 

Legend has it that any two people is separated by a small degree, typically about 6. That is if we take John in New York, and Rajiv in Delhi, it is very likely, we can find a six other people forming a chain of acquaintances from John to Rajiv. This story is also called the Small World Paradox. This surprising (almost) fact cannot be mathematically proven, as it obviously not totally true. For example, there is probably no connection between a Russian village dweller and an isolated tribal in the Amazon forest.

 

Statistical studies have shown that the small number of connections is indeed almost always true. The degree of separation amongst most people tends to be about six, and in some rare cases rises to 10. Another study involving web pages show that most web pages are also related by a small degree—that is to go from one web page to another needs a small number of click (on hyperlinks).

 

Movie actors talk of the Kevin Bacon game, where each actor tried to find the separation between him or her, and Kevin Bacon (Kevin Bacon is a not too well known actor). Of course, it is not quite surprising that every actor is a few steps away from Kevin Bacon, given the huge number of collaborators each person in the acting business has.


The “Erdos Number” was invented in honor of Paul Eros. Erdos has the Erdos number 0. Any person who has coauthored a paper with Erdos has an Erdos number 1, there are 507 of them (shows the prolific collaboration Paul Erdos was known for). Coauthors of people who coauthored with these people have Erdos number 2, and there are estimated to be about 6,000 of them. The largest number of people, who have Erdos numbers, have the number 5 (should have been 6). As the number increases, the population drops off. In the year 2000 there was only 1 person, known to have an Erdos number 15. Of course, this will change as time progresses.

 

Yours truly, has an Erdos number of 3.

 

The Number e

 

Marrying and measuring led us to the inverse of e. What is this e? In mathematics, e is a very famous number, much more famous than the ubiquitous pi or p. p is used by engineers, mathematicians prefer e.

 

It is hard to characterize e as a real life number. One of the best examples compares simple interest with compound interest. Let us say, you keep Rs. 100 in a bank account earning x% simple interest (that is, the interest does not earn interest). The money doubles in y years. If however, you were earning compound interest, in y years, the money would grow e times. Of course, we know e is 2.7182. And, surprisingly, the above result is independent of Rs. 100 or x or y.

 

 

Partha Dasgupta is on the faculty of the Computer Science and Engineering Department at Arizona State University in Tempe. His specializations are in the areas of Operating Systems, Cryptography and Networking. His homepage is at http://cactus.eas.asu.edu/partha.

 

 

 

 

 

 

 

 

 Partha Dasgupta