75th NMO Selection Tests

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

Then $a_k\in \{0,1,\dots ,n\}$, and the sum whose maximum we want to estimate is $$s=\sum _{F\in \mathcal{F}}\text{card}(F)=\sum _{k=1}^n{a}_k.$$ The connection condition implies that if $a_k\ne k$, then $a_{a_k}=k$, for any $k\in \{1,2,\dots ,n\}$. Conversely, any function satisfying this condition corresponds to a family $\mathcal{F}$ verifying the hypothesis.

Therefore, the numbers $a_k$ form pairs of two distinct numbers; otherwise, if $a_i=a_j=a$, then $a$ is connected both to $i$ and to $j$, which would imply $i=j$. We deduce that $$s\le n+(n-1)+\cdots +1=\frac{n(n+1)}{2}.$$ Finally, observe that the maximum $\frac{n(n+1)}{2}$ is attained for any family $\mathcal{F}$ for which $a_{a_k}=k$ for all $k\in \{1,2,\dots ,n\}$; for example, the family ${\mathcal{F}}_0$ formed by $\{1\},\{1,2\},\dots ,\{1,2,\dots ,n\}$.