Prove that at a party where there are at least 2 people ther

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

Let the party have n people where n>=2

If possible let us assume there are 2 people who do not know the same number of other people there

If n =2, then either each does not know the other or both know each other. Hence they cannot know the same no of other people

Let n>2

If every person has distinct numbers of known people

then the no of distinct persons they know must be >=0 and <n

As each person has a distinct number the only possibility is

one persons knows 0 persons, 2 nd knows 1 person, .....nth person known n-1 persons.

There is no other way of getting n distinct numbers below n-1.

Now let us take A who knows 0 person and Z who knows n-1 persons.

As z knows n-1 persons, he knows all other persons, hence he knows A also

THis implies A knows Z and contradicts the fact that no of persons A knows is 0.

Thus it follows that at a party where there are at least 2 people, there are 2 people who know the same number of other people there