2019 Math Prize for Girls Olympiad #1

Let $A_1$, $A_2$, $\ldots\,$, $A_n$ be finite sets. Prove that \[ \Bigl| \bigcup_{1 \le i \le n} A_i \Bigr| \ge \frac{1}{2} \sum_{1 \le i \le n} \left| A_i \right| - \frac{1}{6} \sum_{1 \le i < j \le n} \left| A_i \cap A_j \right| \, . \]Recall that if $S$ is a finite set, then its cardinality $|S|$ is the number of elements of $S$.

Fix an element $x \in\bigcup_{1 \leq i \leq n} A_i$, and let $x$ be present in $k \ge 1$ of the $A_i$s. Note that it is counted $1$ time on the LHS and $\tfrac{1}{2}k - \tfrac{1}{6}\tbinom{k}{2}$ times on the RHS. So, the inequality we have to prove follows from 

$$1  \ge \frac{1}{2}k - \frac{1}{6}\binom{k}{2}$$
$$\iff 1  \ge \frac{6k-k(k-1)}{12}$$
$$\iff 12  \ge -k^2 + 7k$$
$$\iff k^2 - 7k + 12  \ge 0$$
$$\iff (k-3)(k-4) \ge 0,$$

which is clearly always true. $\square$


Popular posts from this blog

1995 IMO #2

2014 IMO SL #C2

2015 IMO SL #A1