could you post your solution ,Harazi,?

My idea is very stupid and simple, but I bet someone can find a more direct and nice solution. Take a graph G in which you connect two non-disjoint subsets. Suppose G doesn't have triangles. We prove it has at least 51 vertices of degree t most 50. Otherwise, we can find 51 vertices of degree at least 51. Take A one of them. Then A must be connecte to a vertex of degree at least 51. Let it be B. Then it's trivial to show that we can find C such that C is joined to A and B, contradiction. Thus, we can find A_1,...,A-50 vertices of degree at most 50. Then A_1 is disjoint from at least 50 subsets, so it has at most $\frac{n}{51} $ elements. The same for A_2,...,A_50 and it's done.

In a different topic, someone asked why the following is true: harazi wrote: A_1 is disjoint from at least 50 subsets, so it has at most $\frac{n}{51}$ elements. In fact, the reason is simple: Since the vertex $A_{1}$ of the graph $G$ has degree at most 50, there are at most 50 subsets $A_{i}$ (with $i\neq 1$) which are not disjoint from $A_{1}$. Thus, the remaining at least 50 subsets $A_{i}$ (with $i\neq 1$) are disjoint from $A_{1}$. So the set $A_{1}$ is disjoint from at least 50 of the subsets $A_{i}$. Thus, $A_{1}$ is disjoint from the union of these 50 subsets. But, according to the problem, the union of 50 subsets $A_{i}$ has more than $\frac{50}{51}n$ elements. Hence, since the set $A_{1}$ is disjoint from this union, it has less than $n-\frac{50}{51}n=\frac{1}{51}n$ elements. By the way: nice problem, Harazi! Darij

My idea is slightly different. Define the graph $ G$ like Harazi's solution. Suppose that $ G$ is triangle-free. I will prove that all vertices in $ G$ are of degree at most $ 50$. If this is false, then there is a vertex $ v$ adjacent to at least $ 51$ other vertices: $ v_{1},v_{2},\dots,v_{51}$. Consider the sets represented by $ v_{2},v_{3},\dots,v_{51}$. The union of these sets has more than $ 50n/51$ elements. Hence, by the Pigeonhole Principle, one of them, say $ v_{51}$ has more than $ n/51$ elements. Consider $ v_{1},v_{2},\dots,v_{50}$. The union of them has more than $ 50n/51$ elements. Therefore, some vertex in $ v_{1},v_{2},\dots,v_{50}$ must be adjacent to $ v_{51}$; WLOG let it be $ v_{1}$. Thus, $ vv_{1}v_{51}$ is then a triangle, contradicting our assumption. The rest is actually the same. In fact, there are at least (not necessarily disjoint) $ 18$ triangles, if I'm not mistaken. Can you please check my argument? Suppose we have only at most $ 17$ triangles: $ a_{1}b_{1}c_{1}$, $ a_{2}b_{2}c_{2}$, ..., $ a_{k}b_{k}c_{k}$, where $ k\leq 17$. Hence, there are at least $ 101-3\cdot17 = 50$ vertices not in these triangles. Let's call these vertices "free vertices." Similar to the previous part, a free vertex $ v$ can have at most degree $ 50$ (otherwise, there must be another triangle). Therefore, at least $ 50$ vertices are not connected to $ v$ and thus, $ |v| < n/51$. This is true for all free vertices. Hence, the union of their corresponding sets has less than $ 50n/51$ elements, a contradiction.

The bounds are incredibly weak. This question was used at a UK selection camp, and I produced the following solution, which disregards $ A_{101}$ entirely. Let $ S_1 = A_1\cup A_2 \cup ... \cup A_{25}$ and $ S_2,S_3,S_4$ three more unions of 25 $ A_i$ such that all 100 are covered. Let $ T_{i,j} = X \backslash (S_i \cup S_j)$. The question tells us that $ |T_{i,j}| < \frac {|X|}{51}$, so the union of all $ T_{i,j}$ has size less than $ \frac {6|X|}{51}$, so there are lots of elements of $ X$ belonging to no $ T_{i,j}$. But each of these must be in at least three $ S_i$, and therefore be common to at least three $ A_i$, so there exist three $ A_i$ containing such a point, and thus with nonempty pairwise intersections. The weakness of the bounds actually leads to a similar argument involving only 64 $ A_i$. Joseph Myers then managed to show (using Freddie Manners', another UK student's, method) that with the strong condition of needing a common point to 3 different $ A_i$, that 59 $ A_i$ is the maximum number of $ A_i$ required for such a point to exist, and that this bound is sharp (there's a counterexample for 58).

Not sure if this is the same thing Consider a graph with sets as verticies and common elements as edges. Now since each element is contained in at most 2 sets each edge corresponds to a element. Now take 50 elements and the other 51. The other 51 must only have 1/51 *n of the edges and so must the 50 (or else just add one) amongst themselves yet the 50 has 50/51n. Thus at least 49/51n of the edges are connecting the sets now divide the 51 into 25 and 26 and the 50 into 25 and 25 and note that each of the 49/51n connect one of the 4 possible pairings but that means one of the pairings has 49/51n/4 =><= By this reasoning we need only 5/6n for this to work

Hi all. Sorry for digging this very old post back up, but I think there's one method that hasn't been covered by the above discussion, which is pretty simple (I think) but powerful enough to give the sharp bound mentioned by Ilthigore 2 posts up (3 years ago?!). I'm guessing that this is probably the method that Freddie Manners used as well. Consider an incidence matrix with columns labelled $A_1, A_2, \ldots, A_{101}$ and rows labelled $x_1, x_2, \ldots, x_n$, where the $x_j$ are the elements of set $X$. Mark a '1' in column $A_i$ and row $x_j$ if $x_j \in A_i$, and '0' otherwise. Assume on the contrary that there does not exist three distinct $A_i$ with all three pairwise intersections nonempty. Now we count the number of 50-tuples in the rows of the table which contain all '0's. So for example a row with 50 '0's count as 1 50-tuple, and a row with 51 '0's count as 51 50-tuples. On one hand, since each row contains at most two '1's, each row contains at least 99 '0's. Hence the number of 50-tuples is at least $\binom{99}{50}n$. On the other hand, for each choice of 50 $A_i$, their union contains at least $\frac{50}{51}n$ elements of $X$. Hence if we consider the columns corresponding to these 50 $A_i$, there are at most $\frac{1}{51}n$ rows whose intersection with the 50 columns consists of all '0's. Thus by summing over all choices of 50 $A_i$, the number of row '0' 50-tuples is less than $\frac{1}{51}\binom{101}{50}n$. Comparing these two bounds, we get \[\binom{99}{50} > \frac{1}{51}\binom{101}{50} \iff \frac{1}{51}\frac{101 \cdot 100}{(101 - 50) \cdot (100 - 50)} > 1\]. The last inequality is obviously false. In fact, it is still false if we replaced all occurences of 101 by 59. Hence our initial assumption was false and we are done.

@hello123: Please be more precise. I think you are confusing sets and elements, but I am not sure because your posting is too brief. @angyansheng: A little correction: angyansheng wrote: On the other hand, for each choice of 50 $A_i$, their union contains at least more than angyansheng wrote: $\frac{50}{51}n$ elements of $X$. Hence if we consider the columns corresponding to these 50 $A_i$, there are at most less than angyansheng wrote: $\frac{1}{51}n$ rows whose intersection with the 50 columns consists of all '0's. Thus by summing over all choices of 50 $A_i$, the number of row '0' 50-tuples is less than $\frac{1}{51}\binom{101}{50}n$. Comparing these two bounds, we get \[\binom{99}{50} > \frac{1}{51}\binom{101}{50} \iff \frac{1}{51}\frac{101 \cdot 100}{(101 - 50) \cdot (100 - 50)} > 1\]. The first $>$ should be an $<$.

i think this works

Valentin Vornicu wrote: Let $n\geq 2$ be a positive integer, and $X$ a set with $n$ elements. Let $A_{1},A_{2},\ldots,A_{101}$ be subsets of $X$ such that the union of any $50$ of them has more than $\frac{50}{51}n$ elements. Prove that among these $101$ subsets there exist $3$ subsets such that any two of them have a common element. Claim: Atleast $50$ sets have greater than $\frac{n}{51}$ elements. Proof: Trival by PHP. Obviously two of them have an intersection or else $51=101$, contradiction so some two them $A_X=B$ and $A_Y=C$ have an non empty intersection. So FTSOC assume that for all $A_i$ we must have the intersection of $B$ and $C$ empty then there are $101-2=99$ possibilities for $A_i$ and obviously atleast 50 of them (by PHP) have an empty intersection with $B$ and by by the claim each have $\frac{n}{51}$ elements a total of $n$ elements when we sum up or implying all the other sets are empty, contradiction.

It is known that $X$ is a set with $102$ elements. Suppose $A_1, A_2, ..., A_{101}$ is a set of subset of $X$ such that the sum of every $50$ of them has more than $100$ elements. Prove that there are $1 \le i <j <k \le 101$ such that $A_i \cap A_j$, $A_i \cap A_k $and $A_k \cap A_j$ are not empty. Indonesia 2014