RO-TST 1999 Problem 16

Let $X$ be a set with $n$ elements, and let $A_{1}$ , $A_{2}$ , ..., $A_{m}$ be subsets of $X$ such that:

1. $|A_{i}|=3$ for every $i\in\left\{1,2,...,m\right\}$ ;
2. $|A_{i}\cap A_{j}|\leq 1$ for all $i,j\in\left\{1,2,...,m\right\}$ such that $i \neq j$ .

Prove that there exists a subset $A$ of $X$ such that $A$ has at least $\left[\sqrt{2n}\right]$ elements, and for every $i\in\left\{1,2,...,m\right\}$ , the set $A$ does not contain $A_{i}$ .

Alternative formulation. Let $X$ be a finite set with $n$ elements and $A_{1},A_{2},\ldots, A_{m}$ be three-elements subsets of $X$ , such that $|A_{i}\cap A_{j}|\leq 1$ , for every $i\neq j$ . Prove that there exists $A\subseteq X$ with $|A|\geq \lfloor \sqrt{2n}\rfloor$ , such that none of $A_{i}$ 's is a subset of $A$ .