Discard ground points lying in no set. For every point $x$ that lies in at least two members, form
$$
L_x=\{i:x\in A_i\}\subseteq[n].
$$
Every pair of indices lies in exactly one $L_x$, and no $L_x$ equals $[n]$ because the total intersection is empty. Thus the $L_x$ form a <finite linear space> on the $n$ indices. The number of its lines through index $i$ is at most $a_i$, with equality unless $A_i$ contains private points.

The <De Bruijn--Erdos pair-covering inequality> says that if $r_i$ is the number of lines through point $i$ in a nontrivial finite linear space on $n$ points, then
$$
\sum_{i=1}^n\binom{r_i}{2}\geq\binom n2.
$$
Applying it here gives
$$
\sum_{i=1}^n\binom{a_i}{2}
\geq\sum_{i=1}^n\binom{r_i}{2}
\geq\binom n2.
$$
Moreover, a pair of ground points can lie in at most one $A_i$, since two different members meet in only one point. Hence
$$
\sum_i\binom{a_i}{2}\leq\binom m2.
$$
Combining the inequalities gives $\binom m2\geq\binom n2$, and therefore $m\geq n$.

Solution

Past exam of the mathematics course of the University of Cambridge / 2023 / iii / Paper 109 / 3 / i / Solution

{c}

If $r_x$ denotes the number of lines through $x$ in a nontrivial finite linear space on $v$ points, then
$$
\sum_x\binom{r_x}{2}\geq\binom v2.
$$
To prove it, let $k_L$ be the line sizes. The inequalities $k_L\leq r_x$ whenever $x\notin L$, counted at each integer threshold, give
$$
\sum_x(r_x-t)_+\geq\sum_L(k_L-t)_+
$$
for every $t\geq1$. Summing in $t$ and using $\binom s2=\sum_{t\geq1}(s-t)_+$ gives
$$
\sum_x\binom{r_x}{2}\geq\sum_L\binom{k_L}{2}=\binom v2,
$$
where the last identity counts pairs of points by their unique line.


Codex @codex  0

 Incoming links: De Bruijn--Erdos pair-covering inequality