Showing posts with label maths and life. Show all posts
Showing posts with label maths and life. Show all posts

Wednesday, April 3, 2013

"So Close No Matter How Far" - Six Degrees of Separation

What if you have to send a message to some person you don't know directly and communication mediums such as email, mail or telephone were unavailable? Then the only method of communication will be via personal contacts. We can search for a friend of us who directly know the intended the recipient. But what if, none of our friends know the recipient directly? Then probably we have to depend on some other intermediate person who can connect one of our friends to the intended recipient. What if there is no such person. Then another intermediate person is required. 

This gives the rise to an interesting question , "What is the maximum number of such intermediate people needed to make sure that we can send a message to anyone in the world ? " or in other words "What is the minimum number of people between any two people in the world ?".

In six degrees of separation concept it says that this value is 6. This concept was introduced by the
The Film
Hungarian Author Frigyes Karinthy in one of his short stories in the year 1929 named "Chains". This was later popularized by a play named "Six Degrees of Separation" written by John Guare. There is also a film titled "Six Degrees of Separation" based on the same story (Will Smith is the main actor.Yet this film is boring) .

So there are at most only five intermediate persons between any two people in the world. I can personally send a mail to Barrack Obama via five intermediate persons. I can contact Chuck Norris via five people. I can connect with Mr.ABC from country XYZ through just five persons. It sounds so amazing and fascinating. So the real question is "is it true ?" Though this was initially introduced as a concept many people have tried to prove it mathematically and practically and amazingly most of those attempts have been somewhat successful. 

In 1967, American sociologist Stanley Milgram devised a way to test the theory, which he called "the small-world problem." He randomly selected people in the mid-West to send packages to a stranger located in Massachusetts. The senders knew the recipient's name, occupation, and general location. They were instructed to send the package to a person they knew on a first-name basis who they thought was most likely, out of all their friends, to know the target personally. That person would do the same, and so on, until the package was personally delivered to its target recipient.Although the participants expected the chain to include at least a hundred intermediaries, it only took (on average) between five and seven intermediaries to get each package delivered. Milgram's findings were published in Psychology Today. This has confirmed the number of links is actually close to six.

Apart from that experiment there were many other experiments and theories. Some of them used mathematical derivations and assumptions as well. With the advancement of technology there are several internet experiments which have tried to check the validity of this concept. One of the interesting experiments is the game "Six Degrees of Kevin Bacon" which was invented as a play on the concept. The goal is to link any actor to Kevin Bacon through no more than six connections, where two actors are connected if they have appeared in a movie or commercial together. It was created by four students at Albright College in Pennsylvania, who came up with the concept while watching Footloose. On the 13th of September, 2012, Google made it possible to search for any given actor's 'Bacon Number' through their search engine. The "Oracle of Bacon" gives a version of this game based on the IMDB database. Using this we can search for the connection between any two actors. Even the Sri Lankan Actors are connected with Kevin Bacon or any other International actors with a very small degree of connection. As an example "Kamal Addaraarchchi" is connected with "Kevin Bacon" via just three intermediate actors. 



There may be tribal groups in the world who have never encountered other civilizations. Thus finding a connection with them will be an impossible thing. In that case this concept will not be true. Apart from that fact all other improvements in technology has resulted in a well connected world. Thus the six degrees of freedom will most probably be true for most of the people in the world. And it is expected that this value of six will be further reduced with the development of the communication technology, transportation facilities and multimedia . Thus the connectivity in the world is so tight and as humans we are "So Close No Matter How far" .



Thursday, March 14, 2013

Pi Day

Today is the "Pi DAY". We have dedicated special dates to celebrate various reasons. And March 14 (or in numbers 3-14) is the day dedicated to celebrate the mathematical constant "Pi". The representation of this date consists the first three digits of the mathematical constant "Pi". Thus it is selected as the "Pi" day. It is a day celebrated by mathematics lovers and probably a day hated by maths haters.
Pi Day Google Doodle 

There are sites specially designed to celebrate this day such as http://www.piday.org/. And it contains useful information about the constant "Pi". Alternatively another day is celebrated as the "Pi" approximation day which fall on July 22nd (22/7) which represents the widely used approximation value of "Pi".

Thursday, February 21, 2013

The Cake Cutting Problem - Fair Division Problem (Part 1)


As humans we tend to own everything. When dividing something among people we need to own a fair portion, if not a bigger portion. Thus problems regarding dividing has become the source of many conflicts, wars and sometimes crimes. Cake Cutting problem is an interesting thing in mathematics which deals with dividing a cake between several people such that each person is fully satisfied with the piece he gets.The generalized dividing problem is also known as the fair division problem and there are several algorithms to solve this. This problem is very much associated with real life problems.


Basics


Before solving the problem of fair division the word "Fair" should be defined properly. Fair can mean two things. The first condition is everyone should be satisfied, that the piece they got is at least an equal portion of the total resources. That is, if the resource is divided between n people each person should feel that they have received at least 1/n portion. The other condition is that every person should feel that no one has received more than himself. In other words everyone should feel that they received the largest part. Satisfying the first condition is less problematic than the second. Thus sometimes the dividing problem is limited to satisfy only the first condition. Yet the human behavior demands not only the first condition but also the second condition should be satisfied so that everyone is happy about the division of the resource. The problems which mandate the second condition is also known as Envy Free division. 

Also the criteria to decide the value of each portion is important. In the simplest case the value of each piece is based on its size. But in complex (and practical) cases the value of each piece will be different     to each participant. One participant may value a piece of cake with more icing on it while one prefer a  piece with cherries. Even under these conditions the definition of fair will help us to tackle the fair division problem easily.


Simplest Case



The simplest case is the division of a cake between two people. This can be easily solved using the divide and choose method. In this scenario one person divide the cake into two pieces which he thinks that is fair. The other person gets the chance to select a piece he like. The other piece is left to the first person. As the first person initially divided the cake in to two fair parts he gets a fair portion. Although second person do not agree with the division of the cake in to two as fair he gets the chance to select any piece. Thus he will also be satisfied with the piece he gets.


The Case of Three


The next case is the division of a cake between three people. There are several methods to solve this fair division problem for three people. Almost all these methods can be generalized to solve problems containing more than three people.The divide and select approach which was used for two person case can not be extended to solve this.  And there are solutions which seems plausible but proved wrong when thoroughly analyzed.

Let's now analyze one such incorrect approach. Let the three people be named as A,B and C. This solution includes following steps.


  • A cuts the cake in to two pieces where he thinks one is 1/3 and the other is 2/3 of the cake.
  • B cuts the 2/3 part of the cake in to two fair pieces.
  • C chooses any piece he likes.- So C is satisfied
  • Then A chooses.
  • Finally B chooses.
Now lets analyze the above solution. Since C selects first, clearly C is satisfied. If C has chosen a piece that is cut by B then A can select the initial piece he cut. If C has selected the initial piece cut by A, then A can select one of the pieces cut by B. As A initially divided in to 1/3 and 2/3 parts, at least one piece cut by B should be 1/3. So A is satisfied in any case. The problem is with B. If B thinks the initial cut by A is not fair (ie. The smaller piece is larger than 1/3 of the cake) B is only satisfied with that piece. Thus if that piece is selected by A or C then B is left unsatisfied. Thus the solution given here is not correct.