Prove that in a gathering of N persons there is always 2 persones of them that have same amount of friends among these persons. Thanks for the help

Guest Aug 23, 2014

#1**+10 **

I'm wondering if the phrasing of this question should be "at least two."

Consider the following pentagon in which the vertices represent 5 people at a gathering........call them A,B, C,D, E.

Now, suppose that all the people there are total strangers to one another. Then, it's clear that there are more than two people who have the same number of friends at the gathering. In fact, there are 5 people who have the same number of friends.......namely ......none!!!

But, if the phrase includes"at least two," then it's true. Suppose we have some polygon with a "large number" of alphabetical vertices - call the number "n" -, and let each vertex represent a "person." Now, connect every vertex with every other vertex and let these connections represent the associations between people. In this instance everyone knows the same number of people - (n-1). Now, erase any one of the connected lines. Then, the two vertexes (people) that were connected by this line now know the same number of people (n-2). And if we continued in this fashion of erasing lines, there would always be at least two vertices that had the same valence (valence is the number of lines meeting at one vertex). And thus, there would always be at least two people who knew the same number of people!! For instance, suppose we erased AB and AC. Then B and C would know the same number of people - in this case, everybody else except "A." Or, if we erased AB, BC and AC, then A, B, and C would know the same number of people - (n-3).

I realize that this isn't a "formal" proof, but I think it demonstrates the idea. Perhaps someone on the site could give a more "formal" one??? I'm sure there's a simpler way, I just don't happen to know it....!!!

CPhill
Aug 24, 2014

#1**+10 **

Best Answer

I'm wondering if the phrasing of this question should be "at least two."

Consider the following pentagon in which the vertices represent 5 people at a gathering........call them A,B, C,D, E.

Now, suppose that all the people there are total strangers to one another. Then, it's clear that there are more than two people who have the same number of friends at the gathering. In fact, there are 5 people who have the same number of friends.......namely ......none!!!

But, if the phrase includes"at least two," then it's true. Suppose we have some polygon with a "large number" of alphabetical vertices - call the number "n" -, and let each vertex represent a "person." Now, connect every vertex with every other vertex and let these connections represent the associations between people. In this instance everyone knows the same number of people - (n-1). Now, erase any one of the connected lines. Then, the two vertexes (people) that were connected by this line now know the same number of people (n-2). And if we continued in this fashion of erasing lines, there would always be at least two vertices that had the same valence (valence is the number of lines meeting at one vertex). And thus, there would always be at least two people who knew the same number of people!! For instance, suppose we erased AB and AC. Then B and C would know the same number of people - in this case, everybody else except "A." Or, if we erased AB, BC and AC, then A, B, and C would know the same number of people - (n-3).

I realize that this isn't a "formal" proof, but I think it demonstrates the idea. Perhaps someone on the site could give a more "formal" one??? I'm sure there's a simpler way, I just don't happen to know it....!!!

CPhill
Aug 24, 2014