# A problem related to the SDR

Let $A_1, A_2, \ldots, A_{20}$ be twenty sets each of size $20$ such that $|A_i \cap A_j | \le 2$. Prove that they have a system of distinct representatives.

-
What is your progress so far? –  rschwieb Dec 28 '12 at 16:26
Are you sure each of the $A_i$s have size 20, rather than their union has size 20? –  Henning Makholm Dec 28 '12 at 16:37

Use Hall's Theorem. It says there exists a system of distinct representatives iff for any subset of the indices, $\{a_1,\ldots,a_k\}$, we have $|\displaystyle\cup_{j=1}^kA_{a_j}|\geq k$. It can be easily checked that your system satisfies this condition: For contradiction, suppose it does not. So, there exists a subset $\{b_1,\ldots,b_l\}$ such that $|\displaystyle\cup_{j=1}^l A_{b_j}|< l \leq 20$. But this is a contradiction since each subset in your system has size $20$.
I'm sure there are simpler solutions without using Hall's theorem for this particular problem, since the conditions are very strong. Comment: The problem is not correct if only the union of the subsets has size 20. A counter example is the system defined by $A_1=\{1,\ldots,20\}$, $A_i=\{1\}$ for i>1.
I almost understand your answer. But I see you didn't use the condition $|A_i \cap A_j| \le 2$ at all? –  user53541 Jan 2 '13 at 16:15