Among a group of persons, every pair of persons together know exactly one other person (knowing is mutual). Denote by the difference between the number of persons known by a member of the group who knows the largest number of persons among the group, and the number of persons known by another member who knows the smallest number of persons among the group. Find the maximum possible value of and all other possible value(s) of .
Solution
The only possible (and hence the maximum) is .
Indeed, by the friendship theorem, there must be one person who knows everyone else. We give a proof as follows.
WLOG, assume and do not know each other. If knows , then and know a person in common. Note that the function mapping to is well-defined, and it is a bijection between the set of persons known by and the set of persons known by . Hence any two persons who do not know each other know the same number of persons.
Let be the set of all persons who know exactly persons, where is chosen such that . Let be the complement of . Note that each person in must know every person in . Otherwise, this person must know exactly persons from the above observation, and hence this person should belong to by definition.
If , then we choose two persons and in arbitrarily. Since they only know one person in common, we must have . In this case the person in knows everyone.
If , then the person in knows everyone.
If , then everyone knows exactly persons. On the one hand, there are pairs of persons in this group. On the other hand, there are pairs of persons knowing a particular person in common. Therefore, we have
But this implies , which has no solution. (In this case, we make use of the fact that is not of the form . But the friendship theorem does apply to any number of persons.)
Therefore, we have proven there exists a person who knows everyone. For every other person , in order that and know exactly one person in common, must know exactly one person apart from . Thus, the other persons can be paired up such that only the two persons in the same pair know each other. Hence, the only possible is .
