Let $\left \{ \left ( A_{i},B_{i} \right ),1\leq i\leq h \right \}$ be a family of pairs of subsets of the set of integers such that $\left | A_{i} \right |=k$ for all $ i$ and $\left | B_{i} \right |=l$ for all $i$, $A_{i}\cap B_{i}=\emptyset$ and $(A_{i}\cap B_{j})\cup (A_{j}\cap B_{i})\neq \emptyset$ for all $i\neq j$ . Prove that $h< \frac{(k+l)^{k+l}}{(k^{k}l^{l})}$.

this is problem 7 of chapter one from alon and spencer The Probabilistic Method.

this is very near to the concepts of $(k,l)-system$ which is discussed there. I want to call an event which its probability will be $\frac{(k^{k}l^{l})}{(k+l)^{k+l}}$.this events must be disjoint.then I want to say that the number of these events are $h$.then from the rule of probability we have $h\frac{(k^{k}l^{l})}{(k+l)^{k+l}}<1$ and it is done.it was the basic method.

now I don't know what is that specific event that make every thing done.I have thought about taking red and blue balls from a box because of similarity to $\frac{k}{k+l}$ and $\frac{l}{k+l}$ which they happen $k$ and $l$ times with putting the ball in the box after taking it,but it seems not to work,so please help me,thank you very much.


1 Answer 1


I think that this answer is right so I wanted to share it with you.

with the probability $p$ I put elements for $A_{i}$ and with $1-p$ for $B_{i}$ and for $A_{i}$ we do it $k$ times and for $B_{i}$ we do it $l$ times,so it happens with the probability $p^{k}(1-p)^{l}$,and because $1 \leq i \leq h$ so by the rule of sum in probability we have $$ hp^{k}(1-p)^{l} < 1 $$ then $$ h < \frac{1}{p^{k}(1-p)^{l}}$$,now if we take $p=\frac{k}{k+l}$ we have the desired result.

  • $\begingroup$ Where does $h$ come in this experiment? $\endgroup$
    – Due_Date
    Mar 4, 2016 at 17:03

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .