Solution to How many do you know ?

There are at least two who know the same number of people

In a room with N > 1 people, show that there are at least two people who know the same number of people in the room. The assumption is that knowing someone is reciprocal so if A knows B, then B knows A.

Solution:

Suppose everyone wears a placard which lists the number of people they know in the room. Then the numbers on the placards can range from zero to N-1 (you do not count knowing yourself). This means there are N possible values for the numbers on the placards. However, if any of the numbers reads zero then none of the numbers can read N-1. Hence there are only N-1 possible numbers possible on the placards because one of zero and N-1 is excluded. Since there are N people in the room, at least two of the numbers on the placards must be the same.