+0  
 
0
354
2
avatar

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

Best Answer 

 #1
avatar+78557 
+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
Sort: 

2+0 Answers

 #1
avatar+78557 
+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
 #2
avatar
0

Thanks for the help 

Guest Aug 24, 2014

10 Online Users

avatar
avatar
We use cookies to personalise content and ads, to provide social media features and to analyse our traffic. We also share information about your use of our site with our social media, advertising and analytics partners.  See details