A Family of Sets

We will solve the more general problem:

Proposition If $|A_i| = a$ and $|B_i| = b$ for all $1 \leq i \leq m$ , then $m \leq \binom{a+b}{a}.$ Let $S$ be the union of all $A_i$ and $B_i$ . Consider a random permutation $\pi$ of $S$ . Let $X_i$ be the event that all of the elements of $A_i$ appear before $B_i$ in $\pi$ . Observe that $\text{Prob}[X_i] = \frac{a! b!}{(a+b)!} = \frac{1}{\binom{a+b}{a}} .$ Furthermore, for $i \neq j$ , $X_i$ and $X_j$ are disjoint events because if $A_i$ appears before $B_i$ , then $A_j$ does not appear completely before $B_j$ since one element of $A_j$ appears in $B_i$ and one element of $B_j$ appears in $A_i$ . Hence, $\sum_{i = 1}^m \text{Prob}[X_i] \leq 1 \implies m \leq \binom{a+b}{a}$ as claimed.

To prove that this inequality is sharp, let $U$ be a set of $a+b$ elements, and define $\{A_i\}$ to be the set of all $a$ -element subsets of $U$ and $B_i = \overline{A_i}$ .

Now, to solve the problem, we just need to find the exponent of $5$ in $\binom{100}{30}$ . But this is just $\boxed{1}$ .