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

$\endgroup$
  • $\begingroup$ 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"? $\endgroup$ – Chris Eagle Oct 23 '11 at 9:56
  • $\begingroup$ Yep. That's exactly what the question wants. $\endgroup$ – fantom Oct 23 '11 at 10:11
4
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.