Maths Olympiad Prep

Library / /43 of 48

Combinatorics Difficulty 7.9 National olympiad, round 2 Prove it Asia Pacific Mathematics Olympiad (APMO)

A set of 19901990 persons is divided into non-intersecting subsets in such a way that
(a) no one in a subset knows all the others in the subset;
(b) among any three persons in a subset, there are always at least two who do not know each other; and
(c) for any two persons in a subset who do not know each other, there is exactly one person in the same subset knowing both of them.
(i) Prove that within each subset, every person has the same number of acquaintances.
(ii) Determine the maximum possible number of subsets.
Note: it is understood that if a person AA knows person BB, then person BB will know person AA; an acquaintance is someone who is known. Every person is assumed to know one's self.

Solution

(i) Let SS be a subset of persons satisfying conditions (a), (b) and (c). Let xSx \in S be one who knows the maximum number of persons in SS.
Assume that xx knows x1,x2,,xnx_{1}, x_{2}, \ldots, x_{n}. By (b), xix_{i} and xjx_{j} are strangers if iji \neq j. For each xix_{i}, let NiN_{i} be the set of persons in SS who know xix_{i} but not xx. Note that, for ij,Nii \neq j, N_{i} has no person in common with NjN_{j}, otherwise there would be more than one person knowing xix_{i} and xjx_{j}, contradicting (c).
By (a) we may assume that N1N_{1} is not empty. Let y1N1y_{1} \in N_{1}. By (c), for each k>1k>1, there is exactly one person yky_{k} in NkN_{k} who knows y1y_{1}. This means that y1y_{1} knows nn persons, namely x1,y2,,ynx_{1}, y_{2}, \ldots, y_{n}.
Because nn is the maximal number of persons in SS a person in SS can know, y1y_{1} knows exactly nn persons in SS. By precisely the same reasoning we find that each person in NiN_{i}, i=1,2,,ni=1,2, \ldots, n, knows exactly nn persons in SS.
Letting y1y_{1} take the role of xx in our argument, we see that also each xix_{i} knows exactly nn persons. Note that, by (c), every person in SS other than x,x1,,xnx, x_{1}, \ldots, x_{n}, must be in some NjN_{j}. Therefore every person in SS knows exactly nn persons in SS and thus has the same number of acquaintances in SS.

(ii) To maximize the number of subsets, we have to minimize the size of each group. The smallest possible subset is one in which every person knows exactly two persons, and hence there must be exactly five persons in the subset, forming a cycle where two persons stand side by side only if they know each other. Therefore the maximum possible number of subsets is 1990/5=3981990 / 5=398.

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 and solution reproduced as published; topic and difficulty added by this site.