Find the biggest natural number $m$ that has the following property: among any five 500-element subsets of $\{ 1,2,\dots, 1000\}$ there exist two sets, whose intersection contains at least $m$ numbers.
Problem
Source: Polish MO Finals 2015
Tags: contests, set theory
28.07.2016 05:31
The answer is $m=200$. Construction: Let $S_i = \{ 100 (i-1)+1, 100(i-1)+2, .. 100i \}$ for $1\le i\le 10$. The following sets achieve $m=200$: $A_1 = S_1\cup S_2\cup S_3 \cup S_4 \cup S_5$. $A_2 = S_1\cup S_2 \cup S_6 \cup S_7 \cup S_8$. $A_3 = S_3 \cup S_4 \cup S_6 \cup S_7 \cup S_9$. $A_4 = S_1 \cup S_3 \cup S_8 \cup S_9 \cup S_{10}$. $A_5 = S_2 \cup S_5 \cup S_6 \cup S_9 \cup S_{10}$. Now, we show $m=200$ is the minimum. Consider any five sets $A_1,A_2,A_3,A_4,A_5$. The sum $\displaystyle\sum_{i<j} |A_i\cap A_j|$ is clearly equal, by double-counting, to the sum $\binom{x_1}{2}+\binom{x_2}{2}+...+\binom{x_{1000}}{2}$, where for each $i$, $x_i$ denotes the number of sets $A_j$ containing $i$. By discrete convexity of $f(x)=\binom{x}{2}$, since $x_1+x_2+..+x_{1000}=2500$ and the $x_i$ are all integers, this sum is at least $500\binom{3}{2}+500\binom{2}{2} = 2000$. Therefore by Pigeonhole since there are $\binom{5}{2}$ terms in the sum $\displaystyle\sum_{i<j} |A_i\cap A_j|$, some $|A_i \cap A_j|$ is at least $\dfrac{2000}{10}=200$, so $m\ge 200$ as desired.