Let $A\_1,A\_2,\ldots,A\_m,B\_1,B\_2,\ldots, B\_m$ be (not necessarily distinct) subsets of $[n]=\{1,2,\ldots,n\}$. Suppose that each $i\in [n]$ appears in at least $k$ of these $2m$ sets. 


I want to find a family of $m$ sets $\{C\_i\}\_{1\le i\le m}$ to cover $[n]$ (that is $C\_1\cup\cdots\cup C\_m=[n]$), where $C\_i=A\_i$ or $C\_i=B\_i$ for each $1\le i\le m$.


How large $k$ (as a function of $n$) is sufficent for the existence of such a family $\{C\_i\}\_{1\le i\le m}$. I wonder whether $k>\log\_2(n)$ is sufficient.


Is it an 'old' problem? Are there any references?
Thanks in advance for any suggestions.



Can we cover a set by a particular family of sets?
$2^k>n$ is sufficuent. Choose $C\_i=A\_i$ or $C\_i=B\_i$ at random, with equal probabilities. The probability that we do not cover given element $s$ is at most $2^{-k}$, thus the expectation of the number of not covered elements is at most $n/2^{k}$, strictly less than 1. Therefore sometimes all elements are covered.


But if $n=2^{k}$, $m=k$, it is not always possible. Consider the vertices of a cube $\{0,1\}^k$ and all $2k$ facets ($A\_i$, $B\_i$ are parallel facets).


