# Solution: 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$$.

The best solution was submitted by Kook, Yun Bum (국윤범, 수리과학과 2015학번). Congratulations!

Here is his solution of problem 2016-5.

Alternative solutions were submitted by 이준호 (2016학번, +2), 김경석 (연세대학교 의예과 2016학번, +2). An incorrect solution was received.

Note: There is a simpler solution.

GD Star Rating