Splitting set $S$ of size $n$ into two disjoint subsets

combinatoricsdiscrete mathematicselementary-set-theoryprobabilistic-methodprobability theory

Let $S$ be a set of size $n$. For any $N$ subsets of $S$ of size $m$, if
$$N<2^{m-1}\,,$$
then prove that there exists a way to split $S$ into two disjoint subsets $A$ and $B$ (with $A\cup B=S$) such that none of the smaller $N$ subsets are subsets of either $A$ or $B$.

I have been trying to do this question for hours, but have gotten nowhere closer to the solution. Any hints as to how to begin this would be appreciated.

Best Answer

Let $S_i$ for $i=1,2,\ldots,N$ denote the $N$ given subsets of $S$. Suppose that $X$ is a subset of $S$ uniformly randomly chosen from all the $2^n$ subsets of $S$. Define $Y(X):=S\setminus X$.

For a fixed value $i\in\{1,2,\ldots,N\}$, the probability that $S_i\subseteq X$ is $\dfrac{2^{n-m}}{2^n}=\dfrac{1}{2^{m}}$ (because $|S_i|=m$ and $X\setminus S_i$ is a random subset of $S\setminus S_i$). Similarly, the probability that $S_i\subseteq Y(X)$ is $\dfrac{1}{2^m}$. Therefore, the probability $p_i$ that $S_i\subseteq X$ or $S_i\subseteq Y(X)$ is $$p_i\leq \frac{1}{2^{m}}+\frac{1}{2^{m}}=\frac{1}{2^{m-1}}\,.$$ (For a positive integer $m$, $p_i=\dfrac1{2^{m-1}}$, but I just want to include the trivial case $m=0$. The OP has never said that $m$ has to be a positive integer.)

Since $N<2^{m-1}$, we obtain $$\sum_{i=1}^N\,p_i\leq \frac{N}{2^{m-1}}<1\,.$$ However, the probability that $S_i\subseteq X$ or $S_i\subseteq Y(X)$ for some $i\in\{1,2,\ldots,N\}$ is at most $\sum\limits_{i=1}^N\,p_i$ (due to subadditivity of probability measures). Consequently, the probability that $S_i\subseteq X$ or $S_i\subseteq Y(X)$ for no $i\in\{1,2,\ldots,N\}$ is at least $$1-\sum\limits_{i=1}^N\,p_i>0\,.$$ Ergo, there exists $A\subseteq S$ such that there are no $i\in \{1,2,\ldots,N\}$ for which $S_i\subseteq A$ or $S_i\subseteq Y(A)=:B$.

Related Question