Let n be a natrual number greater than 1 Prove that is there

Let n be a natrual number greater than 1. Prove that is there are n people at a party, then there are at least 2 people who know the same number of people at the party. Assume that if person A knows person B, the person B knows person A. (Hint: Can all possible numbers of acquaintances be simultaneously possible?)

Solution

The number of possible aquaintances for each of the n people must be one of the n numbers: 0,1,2,....n-1

These are n unique numbers.

However, it is not possible for each person to have n distinct number of acquaintances. If person A has 0 acquaintainces, no person can have n-1 acquaintances.

Hence, the possibilitiles must be n-1 numbers: 1,2,3...n-1 or 0,1,2,...(n-2)

In either case, by the pigeon hole principle, there must exist 2 people having the same number of acquaintances.