A group of n people is such that a symmetric relation of knowing another exists in the group. i.e. the relation is A knows B. and being symmetric if A knows B then B knows A. Prove that there exist at least 2 people who know the same number of people.

Question

Accepted Answer

In a group of people with a symmetric relation of knowing each other, there will always be at least two people who know the same number of people.

Consider the person who knows the maximum number of people in the group.
If there is no one who knows the same number of people, then everyone else must know a different number of people.
But this would mean that the total number of people known by everyone else is different from the total number of people known by the person who knows the maximum.
This contradicts the symmetric property of the relation, so there must be at least two people who know the same number of people.

Asked in Tower Research Capital LLC

A group of n people is such that a symmetric relation of knowing another exists in the group. i.e. the relation is A knows B. and being symmetric if A knows B then B knows A. Prove that there exist at least 2 people who know the same number of people.

Top Strategist Interview Questions Asked at Tower Research Capital LLC

Interview Questions Asked to Strategist at Other Companies