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