# 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

## 2 Answers

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.

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.