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