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 \)

GD Star Rating
loading...
2017-04 More than a half, 4.0 out of 5 based on 52 ratings