# Partition problem of set

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

-
 This is obviously impossible. For example, suppose $A_1=\{1,2,3,4,5,6,7,8,9,10\}$ and $B_i$ contains $i$. Did you mean to say "Prove that we can rearrange the indices of the second partition so that $A_i \cap B_i$ is not empty"? – Chris Eagle Oct 23 '11 at 9:56 Yep. That's exactly what the question wants. – fantom Oct 23 '11 at 10:11

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.

-
Thanks alot Phira, because I am not good at Combinatorial,then I'll try it. – fantom Oct 23 '11 at 9:50
Can you make thing a little bit clear? Sorry, i did not see any connection. – fantom Oct 23 '11 at 10:27
Maybe you can first answer my question? – Phira Oct 23 '11 at 10:27
I did read it from wikipedia, but in the problem, why does A has to admit the SDR? And suppose that $A_{i}$ are man, $B_{i}$ are woman, then the theorem just say the union of k $B_{i}$ contains at least k element. So, how can we understand the intersection between $A_{i}$ and $B_{i}$ ? – fantom Oct 23 '11 at 10:33
@fantom You should really tell us where these questions are coming from. What has come before those questions? In any case, the union of $k$ sets contains $10k$ elements not $k$. – Phira Oct 23 '11 at 10:35
show 1 more comment