Prove that any group of 20 people will contain at least one pair of people with the same a

Dottie Parra

Dottie Parra

Answered question


Show that any group of 20 people will at least have one pair of members who have the same number of friends. (Here, you can let S={p1,p2,,p20} be an arbitrary set of 20 people, and define n(pi) for 1i20 to be the number of friends for person pi within this group. Assume friendship is symmetric, so if someone has 0 friends in the group then there cant

Answer & Explanation



Skilled2021-08-21Added 100 answers

Step 1 
We will use the Pigeonhole Principle, which states that if n boxes contain n+1 things, at least one box must contain at least n objects.
There are 20 people. So, one can have a maximum of 19 friends (friend with everyone). 
Step 2 
So, 20 people should be put in 19 boxes for the number of friends: 1 friend, 2 friends, 3, 4, …, 19. There are 19 boxes and 19+1 objects. Therefore, by the pigeonhole principle with n=19, there is at least one box with two objects, which means, at least one number (of friends) is assigned to two people. 
If one person has 0 friends, then the maximum will reduce to 18. That is, a person is friends with 18 others (excluding himself and the person with no friends). Then, n=18 and 18+1=19 people must be assigned to 18 boxes (1, 2, 3, …, 18 friends). 
If there are two people having 0 friends, then we already have these two people with same number of friends (0). 
Hence, at least two of them have the same number of friends.

Do you have a similar question?

Recalculate according to your conditions!

New Questions in Discrete math

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?