Determine the largest positive integer k for which the following statement is true: given k distinct subsets of the set {1,2,3,…,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,⋯,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 A1,⋯,Ak and E={(Ai,Aj)|Ai∩Aj=ϕ}. 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 (Ai,Aj) in the cycle, there is an unique element x such that x∉Ai and x∉Aj, 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 (Ai,Aj) 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 Ai={(j−1)(mod2n+1)+1|i≤j≤i+n−1} for 1≤i≤2n+1. Then Atn(mod2n+1)+1(0≤t≤2n) makes a cycle with length 2n+1.