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
    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"?2011-10-23
  • 0
    Yep. That's exactly what the question wants.2011-10-23

2 Answers 2