2001 OIM Problems/Problem 3

Problem

Let $S$ be a set of $n$ elements and $S_1, S_2, \cdots , S_k$ subsets of $S$ ($k \ge 2$), such that each of them has at least $r$ elements. Show that $i$ and $j$ exist, with $1 \le i < j \le k$ such that the number of common elements of $S_i$ and $S_j$ is greater than or equal to

\[r-\frac{nk}{4(k-1)}\]


~translated into English by Tomas Diaz. ~orders@tomasdiaz.com

Solution

This problem needs a solution. If you have a solution for it, please help us out by adding it.

See also