# 2016-5 Partition into 4 sets

Let $$A_1,A_2,\ldots,A_n$$ be subsets of $$\{1,2,\ldots,n\}$$ such that $$i\notin A_i$$ for all $$i$$. Prove that there exist four sets $$C_1,C_2,C_3,C_4$$ such that $$C_1\cup C_2\cup C_3\cup C_4=\{1,2,\ldots,n\}$$ and for all $$i$$ and $$j$$, if $$i\in C_j$$, then $$\lvert A_i\cap C_j\rvert \le \frac12 \lvert A_i\rvert$$.

GD Star Rating