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.

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.

Tower Research Capital LLC Strategist interview questions & answers

Popular interview questions of Strategist