Romania — NMO Selection Tests for the Balkan and International Mathematical Olympiads

The required integer is $r = 200$. To prove it, we first show that, amongst every five 500-element subsets of $\{1, 2, \dots, 1000\}$, there are two sharing at least 200 elements, and then provide an example of five such every two of which share exactly 200 elements.

The first part is a special case of the lemma below.

Lemma. Let $n$ be an integer greater than 1, let $S_1, \dots, S_n$ be subsets of a finite set $S$ such that $|S_1| + \dots + |S_n| \ge |S|$, and let $N$ be one of the closest integers to
$$\sigma = \frac{|S_1| + \dots + |S_n|}{|S|} - \frac{1}{2}.$$
Then $|S_i \cap S_j| \ge \frac{N(2\sigma - N)}{n(n-1)} |S|$ for some distinct indices $i$ and $j$.

Proof of the lemma. Let $\chi_i : S \to \mathbb{Z}$ be the characteristic function of the set $S_i$: $\chi_i(x) = 1$ if $x \in S_i$, and $\chi_i(x) = 0$ otherwise; clearly, $\sum_{x \in S} \chi_i(x) = |S_i|$. Let further $\chi : S \to \mathbb{Z}$, $\chi = \chi_1 + \dots + \chi_n$, so $\chi(x)$ is precisely the number of $S_i$ containing $x$, and $\sum_{x \in S} \chi(x) = \sum_{i=1}^n |S_i|$.

Next, fix an element $x$ of $S$ and write
$$\begin{aligned} (\chi(x))^2 &= \left(\sum_{i=1}^{n} \chi_i(x)\right)^2 = \sum_{i=1}^{n} (\chi_i(x))^2 + 2 \sum_{1 \le i < j \le n} \chi_i(x)\chi_j(x) \\ &= \sum_{i=1}^{n} \chi_i(x) + 2 \sum_{1 \le i < j \le n} \chi_i(x)\chi_j(x) = \chi(x) + 2 \sum_{1 \le i < j \le n} \chi_i(x)\chi_j(x), \end{aligned}$$
to get $\sum_{1 \le i < j \le n} \chi_i(x)\chi_j(x) = \frac{1}{2}\chi(x)(\chi(x) - 1) = \frac{1}{2}(\chi(x) - k)(\chi(x) - k - 1) + k\left(\chi(x) - \frac{k+1}{2}\right)$, for any integer $k$. Since $\chi$ is integer-valued, the first summand in the last expression above is non-negative, so
$$\sum_{1 \le i < j \le n} \chi_i(x) \chi_j(x) \ge k \left( \chi(x) - \frac{k+1}{2} \right), \quad k \in \mathbb{Z}.$$
Consequently,
$$\begin{aligned} \sum_{1 \le i < j \le n} |S_i \cap S_j| &= \sum_{1 \le i < j \le n} \sum_{x \in S} \chi_i(x) \chi_j(x) = \sum_{x \in S} \sum_{1 \le i < j \le n} \chi_i(x) \chi_j(x) \\ &\ge \sum_{x \in S} k \left( \chi(x) - \frac{k+1}{2} \right) = k \left( \sigma - \frac{k}{2} \right) |S|, \quad k \in \mathbb{Z}. \end{aligned}$$
Since $k \mapsto k(\sigma - k/2)$, $k \in \mathbb{Z}$, achieves its maximum at $k = N$, the conclusion follows by considering an intersection $S_i \cap S_j$, $i < j$, of maximal cardinality.

Notice that equality in the last inequality above forces each element of $S$ to be covered by exactly $N$ or exactly $N \pm 1$ of the $S_i$. This remark turns out to be quite useful in constructing the desired example.

Finally, to provide an example of five 500-element subsets of $\{1, 2, \dots, 1000\}$ every two of which share exactly 200 elements, consider first the following five 5-element subsets of $\{1, 2, \dots, 10\}$:
$$\begin{aligned} A_1 &= \{1, 2, 3, 6, 8\}, & A_2 &= \{1, 2, 5, 7, 10\}, & A_3 &= \{1, 4, 5, 6, 9\}, \\ A_4 &= \{2, 3, 4, 7, 9\}, & A_5 &= \{3, 4, 5, 8, 10\}. \end{aligned}$$
Since every two $A$'s share exactly two elements, the sets $\bigcup_{k=0}^{99} (10k + A_i)$, $i = 1, 2, \dots, 5$, provide the desired example.