Pages

A facebook friendship problem


Do you know that facebook has its own mathematical problem? It is called the facebook friendship problem. Never heard of it?!

Well, this problem is to prove that if you pick out 6 arbitrary people on facebook, then among these 6 people, you can find 3 people such that they are all mutually friend of each other, or there are no friendships among them at all. 

For example, in the figure below, on the left we have 6 people: Amy, Ben, Cindy, Dan, Emma and Francis. If two of them are friend on facebook then we connect them by a purple line, and if they are not friend on facebook then we connect them by a blue line. 

We can see that in this example, we can pick out 3 people, which are Amy, Dan and Emma, they are all mutually friend of each other because they are connected by purple lines. The same is true for Francis, Ben and Cindy.
In the example on the right, we have 6 people: Kate, Linda, Matt, Noah, Olivia and Peter. Among them we can pick out 3 people, which are Olivia, Noah and Matt, there are no friendships among them because they are connected by blue lines. The same is for Peter, Noah and Matt.