4. Show that in any group of n people there are at least two people who have the same number of friends in the group.

We break it into two cases to make the reasoning simpler:

Step-by-step explanation:

Case 1: There is no one in the group who is friends with everyone else.

Since the group is of n people, and no one is friends with everyone else, we then know that no one has n-1 friends (since that would be being friends with everyone else in the group). So in this case people either have 0, 1, 2, ..., n-2 friends. However, we have n different people on the group, and the options for his/her number of friends are either 0,1,2, ..., n-2, which are n-1 options. Therefore, there's no way all the n people have a different number of friends, since there's only n-1 options available. So, in this case we can conclude that at least two people will have the same numer of friends.

Case 2: There is someone in the group who is friends with everyone else. Since someone is friends with everyone else, that means no one has 0 friends (since everyone will at least have that friend that is friends with everyone else). So in this case people have either 1,2, ..., n-1 friends. However, we have n different people on the group, and the options for his/her number of friends are either 1,2, ..., n-1, which are n-1 options. Therefore, there's no way all the n people have a different number of friends, since there's only n-1 options available. So, in this case we can conclude also that at least two people will have the same number of friends.

In any case we can see that there's at least two people who have the same number of friends.