1
$\begingroup$

Let $A =\{1, 2, 3,..., 100\}$. We partition $A$ into $10$ subsets $A_1,A_2,...A_{10}$ each of size $10$. A second partition into $10$ sets of size $10$ each is given by $B_1,B_2,...B_{10}$. Prove that we can rearrange the indices of the second partition so that $A_{i}\cap B_{i}\not=\varnothing$.

  • 0
    Yep. That's exactly what the questio$n$ wa$n$ts.2011-10-23

2 Answers 2

4

Do you know Hall's marriage theorem? http://en.wikipedia.org/wiki/Hall%27s_marriage_theorem

It is not hard to see that $k$ sets of size 10 each have to share elements with at least $k$ sets in the other partition, so the theorem applies.

ETA: The $k$ sets have a total of $10k$ elements, so you need at least $k$ sets in the other partition to cover all of these elements, since $k-1$ sets have two few elements.

0

Put $P_1=\{A_1,A_2,...,A_{10}\}$ and $P_2=\{B_1,B_2,...,B_{10}\}$

Take any $X \subset P_1$ and let $N(X)\subset P_2$ be the set of all neighbors of vertices in $X$. Say $|X|=k$ and $|N(X)| = l$. Then we have $\bigcup _{A\in X} A =\bigcup _{B\in N(X)} B $ since set on left and sets on right are disjoint we have $10k= \sum _{A\in X} |A| =\sum _{B\in N(X)} |B| =10l $ we have $k=l$ so $|X|\leq |N(X)|$ and so Hall condition is fulfilled and we are done.