Maths Olympiad Prep

Library / /62 of 136

Combinatorics Difficulty 7.8 National Olympiad, round 2 Prove it Hong Kong

Among a group of 451451 persons, every pair of persons together know exactly one other person (knowing is mutual). Denote by nn 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 nn and all other possible value(s) of nn.

Solution

The only possible (and hence the maximum) nn is 448448.

Indeed, by the friendship theorem, there must be one person who knows everyone else. We give a proof as follows.

WLOG, assume AA and BB do not know each other. If XX knows AA, then XX and BB know a person YY in common. Note that the function mapping XX to YY is well-defined, and it is a bijection between the set of persons known by AA and the set of persons known by BB. Hence any two persons who do not know each other know the same number of persons.

Let S1S_1 be the set of all persons who know exactly kk persons, where kk is chosen such that S11|S_1| \ge 1. Let S2S_2 be the complement of S1S_1. Note that each person in S2S_2 must know every person in S1S_1. Otherwise, this person must know exactly kk persons from the above observation, and hence this person should belong to S1S_1 by definition.

If S22|S_2| \ge 2, then we choose two persons XX and YY in S2S_2 arbitrarily. Since they only know one person in common, we must have S1=1|S_1| = 1. In this case the person in S1S_1 knows everyone.

If S2=1|S_2| = 1, then the person in S2S_2 knows everyone.

If S2=0|S_2| = 0, then everyone knows exactly kk persons. On the one hand, there are (4512)\binom{451}{2} pairs of persons in this group. On the other hand, there are (k2)\binom{k}{2} pairs of persons knowing a particular person in common. Therefore, we have
451(k2)=(4512). 451 \binom{k}{2} = \binom{451}{2}.

But this implies k(k1)=450k(k-1) = 450, which has no solution. (In this case, we make use of the fact that 451451 is not of the form k2k+1k^2 - k + 1. But the friendship theorem does apply to any number of persons.)

Therefore, we have proven there exists a person AA who knows everyone. For every other person BB, in order that AA and BB know exactly one person in common, BB must know exactly one person apart from AA. 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 nn is 4502=448450 - 2 = 448.

Figure 1

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.