# Probabilistic Method – 1

Q.1. Let $A_1, \ldots, A_n$ and $B_1, \ldots, B_n$ be distinct subsets of $\mathbb{N}$, such that:

• $\forall i$, $A_i \cap B_i = \phi$.
• $\forall$ distinct $i,j$ $(A_i \cap B_j) \cup (A_j \cap B_i) \neq \phi$.

Prove that, for every real $0 \leq p \leq 1$, $\sum_i {p^{|A_i|} (1-p)^{|B_i|}} \leq 1$.

Solution. Let us create a random subset $R$ by sampling each element of $\mathbb{N}$ with probability $p$.

Let $E_i$ denote the event that $R$ contains all elements of $A_i$ and none of $B_i$. $Pr [E_i] = p^{|A_i|} (1-p)^{|B_i|}$.

Now, the events $E_i$ are pairwise disjoint.

Therefore, $\sum_i {p^{|A_i|} (1-p)^{|B_i|}} = Pr[$ some $E_i$ occurs$] \leq 1$.

$--$

Q.2. Let $A_1, \ldots, A_n$ and $B_1, \ldots, B_n$ be distinct subsets of $\mathbb{N}$ such that:-

• $\forall i,$ $A_i \cap B_i = \phi$.
• $\forall$ distinct $i, j$, $A_i \cap B_j \neq \phi$.
• $\forall i,$ $|A_i| =r, |B_i| = s$.

Prove that $n \leq$ ${r+s} \choose {r}$.

Solution.

Consider a random permutation of the universe $X$ consisting of all elements in the sets $A_i, B_i$.

Let $E_i$ denote the event that all elements of $A_i$ occur before every element of $B_i$ in the permutation.

$Pr [ E_i] =$ ${ {r+s} \choose {r}}^{-1}$.

Now, the events $E_i$ are pairwise disjoint.

Therefore, $n. {{r+s} \choose {r}}^{-1} \leq 1$.

$--$