Maths Olympiad Prep

Library / /21 of 24

Combinatorics Difficulty 8.8 Shortlist Prove it Romania

Let n3n \ge 3 be a natural number, and let F\mathcal{F} be a family consisting of at most nn distinct subsets of the set {1,2,,n}\{1, 2, \dots, n\} with the property that one can consider nn distinct points in the plane, labeled with the numbers 1,2,,n1, 2, \dots, n, then draw segments between some of these points such that, for any distinct numbers i,j{1,2,,n}i, j \in \{1, 2, \dots, n\}, the points labeled ii and jj are connected by a segment if and only if the number ii belongs to exactly jj subsets in F\mathcal{F}. Find the maximum possible value of the sum of the number of elements of the sets in F\mathcal{F}.

Solution

For k{1,2,,n}k \in \{1, 2, \dots, n\}, denote by ak=card{FFkF}a_k = \text{card}\{F \in \mathcal{F} \mid k \in F\}.

Then ak{0,1,,n}a_k \in \{0, 1, \dots, n\}, and the sum whose maximum we want to estimate is
s=FFcard(F)=k=1nak. s = \sum_{F \in \mathcal{F}} \text{card}(F) = \sum_{k=1}^{n} a_k.
The connection condition implies that if akka_k \neq k, then aak=ka_{a_k} = k, for any k{1,2,,n}k \in \{1, 2, \dots, n\}. Conversely, any function satisfying this condition corresponds to a family F\mathcal{F} verifying the hypothesis.

Therefore, the numbers aka_k form pairs of two distinct numbers; otherwise, if ai=aj=aa_i = a_j = a, then aa is connected both to ii and to jj, which would imply i=ji = j.
We deduce that
sn+(n1)++1=n(n+1)2. s \le n + (n-1) + \dots + 1 = \frac{n(n+1)}{2}.
Finally, observe that the maximum n(n+1)2\frac{n(n+1)}{2} is attained for any family F\mathcal{F} for which aak=ka_{a_k} = k for all k{1,2,,n}k \in \{1, 2, \dots, n\}; for example, the family F0\mathcal{F}_0 formed by {1},{1,2},,{1,2,,n}\{1\}, \{1, 2\}, \dots, \{1, 2, \dots, n\}.

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.