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.

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.