Take the 2-minute tour ×

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.

share|improve this question
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
add comment

1 Answer

up vote 2 down vote accepted

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.

share|improve this answer
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
That'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. –  afshi7n Jan 2 '13 at 17:27
I guess that is a counting, right? Could you tell me your way.. –  user53541 Jan 2 '13 at 18:21
Try to select a representative from each set, you will have enough elements in each set to avoid conflicts! –  afshi7n Jan 3 '13 at 20:00
add comment

Your Answer


