Determine the largest positive integer $k$ for which the following statement is true: given $k$ distinct subsets of the set $\{1, 2, 3, \dots , 2023\}$, each with $1011$ elements, it is possible partition the subsets into two collections so that any two subsets in one same collection have some element in common.
Problem
Source: Brazil National Olympiad Junior 2022 #6
Tags: combinatorics
22.11.2022 13:19
Let's generalize the statement: $k$ distinct subsets of the set $\{1, 2, \cdots, 2n+1\}$, each with $n$ elements. I will prove that the maximum value of $k$ is $2n$. Let's think about of a graph $G=(V,E)$ such that $V$ is the $k$ subsets $A_1, \cdots, A_k$ and $E=\{(A_i,A_j)|A_i\cap A_j = \phi\}$. Then, we can partition the subsets into two collections which satisfy the condition if and only if $G$ is a bipartite graph. If $G$ is not a bipartite graph, $G$ should contain an odd cycle. For each edge $(A_i, A_j)$ in the cycle, there is an unique element $x$ such that $x\not\in A_i$ and $x\not\in A_j$, write the value $x$ on the edge. There would be several integers from $1$ to $2n+1$ on the cycle. If there is an element $z$ which does not appear on the cycle, we can say that for each edge $(A_i, A_j)$ in the cycle, only one of them contains $z$. However, it contradicts since the cycle has odd length. Therefore, all elements from $1$ to $2n+1$ should appear on the cycle, which means the length of cycle is greater than $2n$, also means that the number of subsets $k>2n$. For $k>2n$, pick $2n+1$ subsets such that $A_i=\{(j-1)(\mathrm{mod} 2n+1)+1|i\leq j\leq i+n-1\}$ for $1\leq i\leq 2n+1$. Then $A_{tn(\mathrm{mod} 2n+1)+1}(0\leq t\leq 2n)$ makes a cycle with length $2n+1$.