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.
Tell me more
×
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.
|
|
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. |
|||||||||
|
