pigeonhole

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

http://math.stackexchange.com/questions/445487/prove-that-at-a-party-with-at-least-two-people-there-are-two-people-who-know-th

Comments

but the question in the link assumes that each person knows atleast one person which is not the case here..

Answer 2

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.

https://gateoverflow.in/338531/kenneth-rosen-edition-7th-exercise-6-question-40-page-no-406