Problem

Source: Indian Postal Coaching 2007 set 6 p4

Tags: Coloring, combinatorics, Subsets



Let $A_1,A_2,...,A_n$ be $n$ finite subsets of a set $X, n \ge 2$, such that (i) $|A_i| \ge 2, 1 \le i \le n$, (ii) $ |A_i \cap A_j | \ne 1, j \le i < j \le n$. Prove that the elements of $A_1 \cup A_2 \cup ... \cup A_n$ may be colored with $2$ colors so that no $A_i$ is colored by the same color.