# Solution: 2017-04 More than a half

Prove (or disprove) that exactly one of the following is true for every subset $$A$$ of $$\{ (i,j): i,j\in\{1,2,\ldots,n\}, i\neq j\}$$.

(i) There exists a sequence of distinct integers $$i_1,i_2,\ldots,i_k\in \{1,2,\ldots,n\}$$ for some integer $$k>1$$ such that $$(i_1,i_2), (i_2,i_3),\ldots,(i_{k-1},i_k), (i_k,i_1)\in A$$.

(ii) There exists a collection of finite sets $$A_1,A_2,\ldots,A_n$$ such that for all distinct $$i,j\in\{1,2,\ldots,n\}$$, $$(i,j)\in A$$ if and only if $$\lvert A_i\cap A_j\rvert > \frac12 \lvert A_i\rvert$$ and $$\lvert A_i\cap A_j\rvert \le \frac12 \lvert A_j\rvert$$

The best solution was submitted by Jo, Tae Hyouk (조태혁, 수리과학과 2014학번). Congratulations!

Here is his solution of problem 2017-4.

Alternative solutions were submitted by 강한필 (2016학번, +3), 김태균 (수리과학과 2016학번, +3), 배형진 (마포고 3학년, +3), 오동우 (수리과학과 2015학번, +3), 위성군 (수리과학과 2015학번, +3), 장기정 (수리과학과 2014학번, +3), 최대범 (수리과학과 2016학번, +3), 최인혁 (물리학과 2015학번), Ivan Adrian Koswara (전산학부 2013학번, +3), 송교범 (고려대 수학과 2017학번, +2), 조정휘 (건국대학교 수학과 2014학번, +2), Huy Tung Nguyen (2016학번, +2).

GD Star Rating
1. CIH
2. S. Oum Post author