Kenneth Rosen Edition 7 Exercise 6.2 Question 40 (Page No. 406)

Question

Prove that at a party where there are at least two people, there are two people who know the same number of other people there.

Answer 1

In a group of N people, a person may have 0, 1, 2, ..., N − 1 friends. Assume to the contrary that all N people have different number of friends. Then for each number in the sequence 0, 1, 2, ..., N − 1 there must be a person with exactly this number of friends. In particular, there is at least one with N − 1 friends. But, if so, all others have this person 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, ..., N − 1. 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.