We will show a slightly stronger bound: Theorem 1. Let X be a set with n elements, and let $A_1$, $A_2$, ..., $A_m$ be subsets of X such that $\left|A_i\right|=3$ for every $i\in\left\{1;\;2;\;...;\;m\right\}$ and $\left|A_i\cap A_j\right|\leq 1$ for any two different i and j. A subset of X is called good if it does not contain any of the sets $A_1$, $A_2$, ..., $A_m$. Then, there exists a good subset of X whose number of elements is $\geq\left\lceil\sqrt{2n}-\frac12\right\rceil$. This theorem implies the problem, since we always have $\left\lceil\sqrt{2n}-\frac12\right\rceil\geq\left\lfloor\sqrt{2n}\right\rfloor$ (in fact, $\left\lceil\sqrt{2n}-\frac12\right\rceil=\left\lfloor\sqrt{2n}\right\rfloor$ if $0\leq\sqrt{2n}-\left\lfloor{\sqrt{2n}}\right\rfloor<\frac12$ and $\left\lceil\sqrt{2n}-\frac12\right\rceil=\left\lfloor\sqrt{2n}\right\rfloor+1$ if $\frac12\leq\sqrt{2n}-\left\lfloor{\sqrt{2n}}\right\rfloor<1$). Proof of Theorem 1. We will show that, if we have a good subset T of X with u elements and $u<\sqrt{2n}-\frac12$, then we can find an element r of X \ T such that $T\cup\left\{r\right\}$ is also a good subset of X. Once this will be proved, it will be possible to construct stepwise a good subset of X, starting with the empty set (which is trivially good) and adding a new element in each step, until we reach a good subset of X whose number of elements will be $\geq\sqrt{2n}-\frac12$. Since the number of elements of a set is always integer, it will thus follow that the number of elements of this good subset is $\geq\left\lceil\sqrt{2n}-\frac12\right\rceil$. But this will obviously prove Theorem 1. So it remains to show that, if we have a good subset T of X with u elements and $u<\sqrt{2n}-\frac12$, then we can find an element r of X \ T such that $T\cup\left\{r\right\}$ is also a good subset of X. Well, assume the contrary, i. e. assume that, for any element r of X \ T, the set $T\cup\left\{r\right\}$ is not a good subset of X. Then, it must contain one of the sets $A_1$, $A_2$, ..., $A_m$. Let $i_r$ be such that the set $T\cup\left\{r\right\}$ contains the set $A_{i_r}$. So all three elements of the set $A_{i_r}$ are in the set $T\cup\left\{r\right\}$. Obviously, one of these three elements must be r (else, the set T would already contain the set $A_{i_r}$, but this is impossible, since the set T is good). The other two elements must be from the set T. Hence, for any element r of X \ T, we can find a pair of two different elements of the set T such that r, together with these two elements, forms one of the sets $A_1$, $A_2$, ..., $A_m$ (namely, the set $A_{i_r}$). Moreover, for two different elements r and s of X \ T, we get different pairs of elements of T (in fact, if we would get the same pair of elements for r and s, then the sets $A_{i_r}$ and $A_{i_s}$ would satisfy $\left|A_{i_r}\cap A_{i_s}\right|\geq 2$, but this contradicts $\left|A_{i_r}\cap A_{i_s}\right|\leq 1$, which must be fulfilled since $i_r\neq i_s$, as the sets $A_{i_r}$ and $A_{i_s}$ are different because of different r and s). Thus, we have an injective transformation from the set X \ T to the set $\binom{T}{2}$ of pairs of two different elements of T. Hence, $\left|X\backslash T\right|\leq\left|\binom{T}{2}\right|$. Since $\left|X\backslash T\right|=\left|X\right|-\left|T\right|=n-u$ and $\left|\binom{T}{2}\right|=\binom{\left|T\right|}{2}=\binom{u}{2}=\frac{u\left(u-1\right)}{2}$, this becomes $n-u\leq\frac{u\left(u-1\right)}{2}$, what transforms into $u^2+u-2n\geq 0$. But since $u<\sqrt{2n}-\frac12$, we have $u^2+u-2n<\left(\sqrt{2n}-\frac12\right)^2+\left(\sqrt{2n}-\frac12\right)-2n=-\frac14<0$, so we get a contradiction. Thus, our assumption was wrong, and we can find an element r of X \ T such that $T\cup\left\{r\right\}$ is also a good subset of X. This, as explained above, yields the proof of Theorem 1, and thus the problem is solved. darij

Nice solution darij! I swear I have seen this problem somewhere before on the forum, but maybe it wasn't solved on there, can't find the link...

allen i've seen it too !

It's for, Iran TST 1998

let us try to construct such a set. for a pair of points in $A$ we consider as a 'bad' point the third(if there is one such) point that determines a block.(note that the third point if exists,for a pair, is uniquely determined). Thus if we have chosen $k$ points, then we have atmost $\frac{k(k-1)}{2}$ bad points. if however we have a maximal such set, then this set does not admit an extension to $k+1$ points which means, that apart from the $k$ points in the set $A$, all the points of the set $X\setminus A$ are 'bad' points. this gives a quadratic in $k$ and simplification of that gives the required bound.

looks like my solution is the same as darij's, and his has all the details that i have skipped.

I did exactly the same as sesahdri and darij, but my first idea was to consider a graph that has n vertices and m triangles such that every edge is contained in exactly one triangle. maybe i am to obbssesed with graphs, maybe there is something to it. LOL.. i first heard this problem like 6 months ago because it is from Italy TST 1999, then I heard it was part also of a Iranian TST, now Valentin posts it as Romanian TST's 1999! 3 TST's in one year! is this problem from 1998 IMO Shorlist?

I just wanna ask if there are any boundaries for $m$, because if $m>\binom{n}{3}$ then there will be too many triangles so I wonder what's the maximal value of $m$ for which this problem holds

I just wanna ask if there are any boundaries for $m$, because if $m>\binom{n}{3}$ then there will be too many triangles so I wonder what's the maximal value of m for which this problem holds ?

Loser wrote: I just wanna ask if there are any boundaries for $ m$, because if $ m > \binom{n}{3}$ then there will be too many triangles so I wonder what's the maximal value of $ m$ for which this problem holds This is being / has been discussed at http://www.mathlinks.ro/Forum/viewtopic.php?t=70146 (don't know if it was really answered there). darij

I have a solution for $\frac{2}{3}$ times te desired quantity. Let's first count the number of triples $(a,b,c)$ where $a$ and $b$ are elements of $X$ and $c$ is one of the $A_i$ such that $a$ and $b$ belong to $c$. The triples $(a,b,c)$ and $(b,a,c)$ are equivalent. The number of such triples is evidently $3m$. On the other hand we can get a lower bound on these triples. We know that each of the $\binom{n}{2}$ pairs can be in at most one of the $A_i$, therefore the number of triples is at most $\binom{n}{2}$. Hence $3m \leq \binom{n}{2} \leq \frac{n^2}{2}$. Now we can translate the problem into hypergraph theory. The set $X$ will be our set of vertices. The $A_i$ will be our edges of our three-uniform hypergraph. Of course if the number of edges is $< \frac{n}{3}$ then we can take our set $A$ to be the set of all $n$ vertices minus one from each edge, which would yield at least $\frac{2n}{3}$ vertices in our independent set whoch is for $n$ at least $2$ clearly more than $\frac{2\sqrt{2n}}{3}$. So we can assume $m \geq \frac{n}{3}$. Now we apply the Lemma and we are done. Lemma Let $H$ be a three-uniform hypergraph with $m\geq \frac{n}{3}$ edges and $n$ vertices. Then it contains an independent set of size at least \[\frac{2n\sqrt{n}}{3\sqrt{3}\sqrt{m}}\] edges. Proof

Our set $A$ will be this independent set which has size at least \[\frac{2n\sqrt{n}}{3\sqrt{3}\sqrt{m}} \geq \frac{2n\sqrt{n}}{3\sqrt{3}\sqrt{\frac{n^2}{6}}}=\frac{2\sqrt{2n}}{3}\] Note that if anyone improves the statement of this lemma the improvement would maybe enable my solution to reach the desired bound. The improvement of this lemma is discussed here http://www.artofproblemsolving.com/Forum/viewtopic.php?f=42&t=599714&p=3560533#p3560533