Let $A_1,\ldots,A_m$ be three-element subsets of an $n$-element set $X$ such that $|A_i\cup A_j|\le1$ whenever $i\ne j$. Prove that there exists a subset $A$ of $X$ with $|A|\ge2\sqrt n$ such that it does not contain any of the $A_i$.
Source: Mongolia 1999 Grade 10 P5
Tags: combinatorics
Let $A_1,\ldots,A_m$ be three-element subsets of an $n$-element set $X$ such that $|A_i\cup A_j|\le1$ whenever $i\ne j$. Prove that there exists a subset $A$ of $X$ with $|A|\ge2\sqrt n$ such that it does not contain any of the $A_i$.