Solved by Jan Schellenberger and Stefen Dorsett

Question:

Commutative Exponents

In a room of 31 people, show that at least two of them have the same number of friends in that room. Here, we say that no one can count him/herself as a friend, and that friendship is mutual (i.e. A is a friend of B if and only if B is a friend of A). Does the result hold for a room of 32 people?

Answer:

Solution from Jan Schellenberger

All people can have between 0 and 30 friends (that's 31 possibilities). 
There are also 31 people so the only way that none of the people have
the same number of friends then each person must have a unique number of
friends, that number being between 1-30.  Each and every number is
represented.  There must be a person who has no friends and one who has
30 friends.  But if someone has 30 friends, he must be friends with the
person who has no friends, but by the commutitive property of
friendship, this is a contradiction.  Therefore, this cannot be the
case, and two people must have the same number of friends.

- Jan

Solution from Stefan Dorsett

First let's try to construct a situation of a room of n people, n
greater than one, where no two people have the same number of friends,
remembering that if 'a' is a friend of 'b', then 'b' must be a friend of
'a', and 'a' cannot be a friend of 'a'. There are thus up to n-1 friends
that one person can have, and as low as zero. Consider the situation
where 'a' has n-1 friends: This implies that everyone in the room is a
friend of 'a', thus no one can have zero friends. Thus n-1 and zero are
mutually exclusive, and instead of a set of n numbers of friends, we
have a set of only n-1 numbers of friends. If we map the people to the
number of friends that they have, there are n people being mapped to n-1
numbers of friends, thus by the pidgeon hole principle, there must be at
least one number of friends that is mapped to twice, i.e. two people
have the same number of friends. So when we have a room with 31, 32 or
any number of people greater than one, there will always be at least two
people with the same number of friends in the room.

- Stefan