use probability method!

What is CTST-Is it China TST?

We shall choose our sets by greedy algorithm. Let $S=\{A_1,...,A_k\}$. Now choose sets $A_i$ one by one such that the size of their union increases by 3 each time. Keep choosing until no such set $A_i$ exists. WLOG $S_3=\{A_1,A_2,...,A_{a_3}\}$ is chosen for some $a_3\geq 0$, then $\bigcup S_3=X_3$, with $|X_3| =3a_3$. Since $S_3$ is maximal, for any other $A_i,i>a_3, |A_i\cap(X-X_3)|\leq 2$. Now choose sets $A_i$ one by one again such that the size of their union in $X-X_3$ increases by 2 each time. WLOG $S_2=\{A_{a_3+1},...,A_{a_3+a_2}\}$ is chosen, then $\bigcup S_2\cap (X-X_3)=X_2$, with $|X_2|=2a_2$. Again for any other $A_i,i>a_3+a_2,|A_i\cap(X-X_3-X_2)|\leq 1$. Similarly choose sets in $S_1=\{A_{a_3+a_2+1},...,A_{a_3+a_2+a_1}\}$ and $X-X_3-X_2=X_1$. Now note that $|X|=|X_3|+|X_2|+|X_1|=a_1+2a_2+3a_3$, $\bigcup S_3\cup\bigcup S_2\cup\bigcup S_1=X$ and $|S_3+S_2+S_1|=a_1+a_2+a_3=m$ is our chosen sets. So now it suffices to show $m\leq 3k/7$. Note that each element in $X_1$ has to appear at least 4 times, but $|A_i\cap X_1|\leq 1$ for $i>a_3+a_2$. Thus \[k\geq a_3+a_2+4a_1 ---(1) \]Each element in $X_2+X_1$ has to appear 4 times as well, but $|A_i\cap (X_2+X_1)|\leq 2$ for $i>a_3$. Thus \[k\geq a_3+4(2a_2+a_1)/2=a_3+4a_2+2a_1 ---(2) \]Each element in $X$ has to appear 4 times, thus \[k\geq 4(3a_3+2a_2+a_1)/3 ---(3) \]Now taking $20*(1)+12*(2)+27*(3)$, we have $59k\geq 140(a_1+a_2+a_3)\implies m\leq \frac{59k}{140}<\frac{3k}{7}$ as desired.

dear oneplusone, how did you think of this idea?

And mr. JungHoon can you tell us how to solve with probabilistic method? I'm blind in that part.

I'm struggling with this one and I don't know if anything of this has any sense. Take at random and independent any set with probability $p=3/7$. Let $N$ be the number of chosen sets. Then $E(N) = 3k/7$ so there is a family with at most $3k/7$ elements. We can assume that every element in $X$ is exactly in 4 sets among $A_1,...,A_k$.Then probability that any member of $X$ is not in chosen family is $q^4 \cdot p ^{N-4}$. So if we take union bound, we see it is less then 1, for $k\geq 9$. Is there any sense in my words?

Now I've found this partial solution: We are trying to find a family of ${4k\over 7}$ (I will prove for ${13\over 25}k$) such sets that no element in $X$ is in more then 3 set from that family. Let' s take any set independetly with probability $p$. Let's mark with $X$ a number of choosen sets and with $Y$ a number of elements that are ''bad'' i.e. elements which are in at least 4 sets among choosen sets. Note that $4n\leq 3k$. Then we have $$E(X-Y)=E(X)-E(Y) \geq kp-np^4 \geq kp (1-3p^3/4)$$Since a function $x \mapsto x(1-3x^3/4)$ achives maximum at $x=\sqrt[3]{1/3}$ we have $E(X-Y)\geq {\sqrt[3]{9}\over 4}k> {13\over 25}k$. So with the method of alteration we find constant ${\sqrt[3]{9}\over 4}$ which is about $0,051$ worse then ${4\over 7}$.

We improve the bound to $\frac{2}{5}k.$ First of all note that by deleting elements from $A_i$'s, we may assume that any element of $X$ belongs to exactly $4$ of the $A_i$'s. Pick the maximal number $t$ of sets $A_i$ with the property that any $4$ of them have empty intersection, WLOG any $4$ of $A_1,A_2,...,A_t$ have empty intersection. Call an element $x$ of $A_1\cup A_2\cup...\cup A_t$ special if it belongs to exactly $3$ sets among $A_1,...,A_t.$ Denote by $b_i$ the number of special elements in $A_i$ for any $1\le i\le t$ and by $a_j$ the number of special elements in $A_{j+t}$ for any $1\le j\le k-t.$ Claim1. $a_j\ge 1$ for all $j.$ Proof: If $a_j=0$, then any $4$ of the sets $A_1,A_2,...,A_t,A_{j+t}$ have empty intersection, contradicting the maximality of $t$! Note that any special element $x$ appears in $4$ of the $A_1,...,A_k$, three of which are among $A_1,...,A_t$, so there is some a unique $j_x$ such that $x\in A_{j_x+t}.$ Denote $c_x=a_{j_x}.$ Claim 2. $\sum_{x~\text{special}~\in A_i}\frac{1}{c_x}\le \frac{b_i+1}{2}$ for all $i=\overline{1,t}.$ Proof: We divide this into cases depending on the value of $b_i$. a) $ b_i=0$. In this case the inequality is vacuously true. b) $b_i=1$. This is easy: $\frac{1}{c_x}\le 1=\frac{b_i+1}{2}$ for the special element $x$ of $A_i.$ c) $b_i=2$. Let $x,y$ be the special elements of $A_i.$ If $j_x=j_y$, then $x,y\in A_{j_x}$, so $\frac{1}{c_x}+\frac{1}{c_y}=\frac{2}{c_x}\le 1<\frac{b_i+1}{2}.$ Otherwise, if $A_{j_x}\cup A_{j_y}$ contains no other special elements besides $x,y$, then any $4$ of $A_1,A_2,...,A_{i-1},A_{i+1},...,A_{t},A_{j_x},A_{j_y}$ have empty intersection, contradicting the maximality of $t$!. Thus $\max\{c_x,c_y\}\ge 2$, which is enough to give $\frac{1}{c_x}+\frac{1}{c_y}\le\frac{1}{1}+\frac{1}{2}=\frac{b_i+1}{2}.$ d) $b_i=3$. Let $x,y,z$ be the special elements of $A_i$. If WLOG $j_x=j_y$, then $x,y\in A_{j_x}$ yields $c_x=c_y\ge 2$, so $$\frac{1}{c_x}+\frac{1}{c_y}+\frac{1}{c_z}\le \frac{1}{2}+\frac{1}{2}+\frac{1}{1}=\frac{b_i+1}{2}.$$Otherwise, if $j_x,j_y,j_z$ are pairwise distinct, as in the proof of case c), by replacing $A_i$ with $A_{j_x}$ and $A_{j_y}$ etc., we obtain $\max\{c_x,c_y\}\ge 2$ and the cyclic inequalities. This implies that at least two of the numbers $c_x,c_y,c_z$ are at least $2$, hence $$\frac{1}{c_x}+\frac{1}{c_y}+\frac{1}{c_z}\le \frac{1}{2}+\frac{1}{2}+\frac{1}{1}=\frac{b_i+1}{2}.$$ Along with the observation that $b_i\le 3$ (since $|A_i|\le 3$ always), Claim 2 is proven. We are now ready to finish the problem. By summing all the inequalities in Claim 2, and observing that for a fixed special $x$, we have $3$ indices $1\le i\le t$ with $x\in A_i$, we get that $$\sum_{x~\text{special}}\frac{3}{c_x}=\sum_{i=1}^{t}\sum_{x~\text{special}~\in A_i}\frac{1}{c_x}\le\sum_{i=1}^{t}\frac{b_i+1}{2}\le 2t$$, where the last inequality follows from $b_i\le 3$. However note that for each $1\le j\le k-t$, $c_x=a_j$ for $a_j$ values of $x$, and so the LHS of the above inequality rewrites as $\sum_{j=1}^{k-t}\frac{3}{a_j}\cdot a_j=3(k-t).$ Overall, $3(k-t)\le 2t$, i.e. $k-t\le\frac{2}{5}k.$ Along with the next claim, this proves the problem: Claim 3. $A_{t+1}\cup...\cup A_k=X.$ Proof: If there is some $x\in X$ with $x\notin A_{t+1}\cup...\cup A_k$, then $x$ appears in $4$ of the sets $A_1,...,A_t$, contradicting the fact that any $4$ of them have empty intersection.

Quote: $b_i=2$. Let $x,y$ be the special elements of $A_i.$ If $j_x=j_y$, then $x,y\in A_{j_x}$, so $\frac{1}{c_x}+\frac{1}{c_y}=\frac{2}{c_x}\le 1<\frac{b_i+1}{2}.$ Otherwise, if $A_{j_x}\cup A_{j_y}$ contains no other special elements besides $x,y$, then any $4$ of $A_1,A_2,...,A_{i-1},A_{i+1},...,A_{t},A_{j_x},A_{j_y}$ have empty intersection, contradicting the maximality of $t$!. Thus $\max\{c_x,c_y\}\ge 2$, which is enough to give $\frac{1}{c_x}+\frac{1}{c_y}\le\frac{1}{1}+\frac{1}{2}=\frac{b_i+1}{2}.$] is the proof for$\frac{2}{5}k.$right?if $A_{j_x},A_{j_y},A_1,A_2$ have a commom element we can't put in $A_{j_x},A_{j_y}$.

Here's another proof for $\left\lfloor\frac{2k}{5}\right\rfloor$ Consider the family $\mathcal{F}=\{A_{a_1},A_{a_2},\ldots,A_{a_j}\}$ which represents the minimal covering set in the $\{A_i\}$. For each $i$, define the leaks of $A_{a_i}$ to be elements which only appear in the family in $A_{a_i}$. Every $i$ has at least one leak, or else we could remove $A_{a_i}$ from $\mathcal{F}$. Reindex the family such that $A_{a_i}$ has exactly one leak iff $i\le m$, for some $0\le m\le j$. Now, from the problem statement, we know that every element is present in $4$ elements of the family $\{A_i\}$. In particular, $\mathcal{G}=\{A_i\}\setminus \mathcal{F}$ has 3 elements which have $\ell$ for any leak $\ell$, since $\mathcal{F}$ only has one such element. Furthermore, note that no element of $\mathcal{G}$ has 2 leaks from sets with index $\le m$, otherwise it could replace the two $A_{a_i}$ it corresponds to, thus contradicting the minimality of $\mathcal{F}$. We can now bound the number of sets in $\mathcal{G}$. Of course, there are at least $3m$ elements, so if $m\ge \frac{j}{2}$, then we are already done, since that would imply $k=|G|+j\ge \frac{5}{2}j$. So, suppose $m<\frac{j}{2}$. Now, any set in $\mathcal{G}$ which contains a leak from an index $\le m$ contains at most 2 more leaks, both of which must come from indices $>m$. Hence, $$|\mathcal{G}|\ge 3m+\frac{\left(\sum_{i>m}3\left|A_{a_i}\right|\right)-6m}{3}\ge 3m+(2(j-m)-2m)=2j-m>\frac{3j}{2}$$and we are done once again.