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.
A problem related to the SDR
-
0What is your progress so far? – 2012-12-28
-
0Are you sure each of the $A_i$s have size 20, rather than their _union_ has size 20? – 2012-12-28
1 Answers
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.
-
0I almost understand your answer. But I see you didn't use the condition $|A_i \cap A_j| \le 2$ at all? – 2013-01-02
-
0That's right. The problem is still correct without that condition. I also have a simple way without using Hall's Theorem which proves it. Let me know if you want to know about that. – 2013-01-02
-
0I guess that is a counting, right? Could you tell me your way.. – 2013-01-02
-
0Try to select a representative from each set, you will have enough elements in each set to avoid conflicts! – 2013-01-03