Question

Problem 7. Show that in a room full of 20 people there are 2 people who have the same number of friends present. Friendship is symmetric. If A is friends with B then B is friends with A.

Answer 1

Solution 1
A person at the party can have 0 up to 19 friends at the party. However, if someone has 0 friends at the party, then no one at the party has 19 friends at the party, and if someone has 19 friends at the party, then no one has 0 friends at the party. Hence the number of possibilities for the number of friends the 20 people at the party have must be less than 20. Hence two people at the party have the same number of friends at the party.

Solution 2

Note, as in the first solution, that in general, in a group of 20 people, a fellow may have 0, 1, 2, ..., 19 friends. Assume to the contrary that all 20 people have different number of friends. Then for each number in the sequence 0, 1, 2, ..., 19 there must be a fellow with exactly this number of friends. In particular, there is at least one with 19 friends. But, if so, all others have this fellow as a friend, implying that there is no one with no friends at all. Therefore, the only possible numbers of friends come from the shortened sequence: 1, 2, 3, ..., 19. By the Pigeonhole Principle, there are at least two with the same number of friends, so that our assumption that this is not true proved wrong, thus it must be indeed true.