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

Prove that any group of 20 people will contain at least one pair of people with the same amount of friends within the group. (Here, you can let $$\displaystyle{S}={\left\lbrace{p}_{{{1}}},{p}_{{{2}}},\ldots,{p}_{{{20}}}\right\rbrace}$$ be an arbitrary set of 20 people, and define $$\displaystyle{n}{\left({p}_{{{i}}}\right)}$$ for $$\displaystyle{1}\leq{i}\leq{20}$$ to be the number of friends for person $$\displaystyle{p}_{{{i}}}$$ within this group. Assume friendship is symmetric, so if someone has 0 friends in the group then there can't be someone with 19 friends. Similarly, if someone has 19 friends in the group then there can't be anyone with 0 friends in the group. What are the possible values of $$\displaystyle{n}{\left({p}_{{{i}}}\right)}.?{)}$$.

• Questions are typically answered in as fast as 30 minutes

Plainmath recommends

• Get a detailed answer even on the hardest topics.
• Ask an expert for a step-by-step guidance to learn to do it yourself.

l1koV
Step 1
We will use Pigeonhole Principle: If $$\displaystyle{n}+{1}$$ objects are placed in n boxes, then one at least one box contains two 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 $$\displaystyle{19}+{1}$$ objects. Therefore, by the pigeonhole principle with $$\displaystyle{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, $$\displaystyle{n}={18}$$ and $$\displaystyle{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.