Can we cover a set by a particular family of sets?

Question

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.

Answer 1

$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).