THE 68th NMO SELECTION TESTS FOR THE BALKAN AND INTERNATIONAL MATHEMATICAL OLYMPIADS

Let $U$ be the union of the $A_i$. It is sufficient to show that a maximal (relative to set-theoretic inclusion) subset $T$ of $U$ containing no $A_i$ satisfies the required cardinality condition.

By maximality, for each element $x$ of $U\setminus T$, there exists a 2-element subset $S$ of $T$ such that $S\cup \{x\}$ is an $A_i$.

If $x$ and $x^{\prime }$ are distinct elements of $U\setminus T$, and $S$ and $S^{\prime }$ are 2-element subsets of $T$ such that $S\cup \{x\}$ and $S^{\prime }\cup \{x^{\prime }\}$ are both amongst the $A_i$, then $S$ and $S^{\prime }$ are also distinct, since two distinct $A_i$'s share at most one element.

Therefore, choosing for each $x$ in $U\setminus T$ a 2-element subset $S$ of $T$ such that $S\cup \{x\}$ is an $A_i$ defines an injection of $U\setminus T$ into the collection of 2-element subsets of $T$. Consequently, $|U|-|T|=|U\setminus T|\le \left(\genfrac{}{}{0ex}{}{|T|}{2}\right)$, so $|T|\ge (-1+\sqrt{8|U|+1})/2$; if $|U|=2017$, then $|T|\ge 64$.