Number of people

Another quick and very simple post, A few weeks ago, I was talking with my family about the number of people in a party, how to make everyone know each other and that kind of stuffs. At one moment of the talk my father said: "You cannot know everyone at the party.", then he said: "which is the average of people you may know at the party". Time went by and I kind of forgot the talk, but yesterday a college of mine said (in a complete different talk): "Not everyone knows the same number of people". Then I remember everything and I wondered to myself: "At my father's party, which is the probability of having at least two people that know the same number of people?". By knowing I mean "sometime talked to the guy!"

Think about the problem a bit, there is a trick :-).


Well, the probability is 1. You will always have at least two persons that know the same number of people. The demonstration is really, really simple, the problem is creating a correct model.

Imagine every person at my father's party as a vertex of a Graph (the number of people is n). The act of knowing someone is an edge, and the number of people someone knows is what we call in graph theory: the degree of the vertex.

Let's assume that we cannot find two persons that know the same number of people, in our case, if we order the degree of the vertex for n persons, the only possibility we may have is: {0,1,2,...n-1} (this is call the degree sequence of the graph, and knowing myself is not considered because it's a stupid idea). As we can see on the extremes of the degree sequence (0 and n-1) we have a contradiction, because if the person number 1 doesn't know anyone at the party, then person number n cannot know everyone at the party because it means that he knows number 1 ! (so they know each other)

Damn!, Someone reported a bug, I should get back to work  now! :-)

Have a nice day!