Picking set not containing any specified subset Let $A$ be a subset of size $n$, and let $A_1,\ldots,A_m$ be $3$-element subsets of $A$, any two of which share no more than one element. Prove that there exists $B\subseteq A$ of size at least $\lfloor\sqrt{2n}\rfloor$ that doesn't contain any $A_i$. I try to choose $B$ greedily, by first setting $B=A$, and then throwing out elements so that $B$ doesn't contain any $A_i$. If we throw out one element from each of the $A_i$, we'll surely get a desirable set, with $n-m$ elements. But the required bound doesn't depend on $m$.

A greedy algorithm works here. Keep adding elements to $B$ any way you like until you can't continue.

Therefore let $B$ be a subset of $A$ that meets the requirements and is maximal for inclusion. Let $p$ be the number of elements in $B$.

Since $B$ is maximal for inclusion, every one of the $n-p$ elements of $A - B$ belongs to some $A_i$ that already has two elements in $B$. Since two $A_i$'s of this kind can never have the same intersection with $B$, there are at most $\binom{p}{2}$ such $A_i$'s, proving that $\binom{p}{2} \geq n -p$. This inequality is equivalent to $p(p+1) \geq 2n$. Thus $$p + 1 > \sqrt{p(p+1)} \geq \sqrt{2n}.$$ This proves that $p \geq \lfloor \sqrt{2n} \rfloor$.