Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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
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|cite|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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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