Let $X$ be a non-empty and finite set, $A_1,...,A_k$ $k$ subsets of $X$, satisying: (1) $|A_i|\leq 3,i=1,2,...,k$ (2) Any element of $X$ is an element of at least $4$ sets among $A_1,....,A_k$. Show that one can select $[\frac{3k}{7}] $ sets from $A_1,...,A_k$ such that their union is $X$.
Problem
Source: CTST TST 3 Day 1 Q2
Tags: combinatorics, Probabilistic Method, China TST, China
29.03.2015 18:27
use probability method!
29.03.2015 19:09
What is CTST-Is it China TST?
30.03.2015 19:38
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.
06.04.2015 17:12
dear oneplusone, how did you think of this idea?
06.04.2015 17:18
And mr. JungHoon can you tell us how to solve with probabilistic method? I'm blind in that part.
04.11.2016 19:54
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?
24.12.2016 02:05
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}$.
14.03.2020 20:32
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.
01.09.2020 10:32
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}$.
17.09.2020 01:39
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.