Friends at a party

Puzzle

An extremely popular mathematician threw a party. Including himself, there were 15 people at the party. Must there have been at least two people with the same number of friends present? Explain.

Hint

Assume friendship is mutual, i.e. if A is a friend of B then B is a friend of A.

Solution

The least number of friends a person might have is 0 (gatecrasher) and the greatest is 14 (friends with everyone, excluding themselves). There are as many integers in that range as there are people at the party, so if everyone has a different number of friends, then every number from 0 to 14 must be equal to that number for some person.

But if some person (very likely the mathematician) has 14 friends, and we assume friendship is always mutual, then there can be no person with 0 friends. Everyone must have at least one friend, namely the person with 14 friends.

Therefore the assumption that everyone has a different number of friends leads to a contradiction, and by reducto ad absurdum we conclude that at least two people must have the same number of friends.