Sets $S_i$ such that $|S_i\cap S_j|\geq4$ Let $A=\{1,2,\ldots,1600\}$, and let $S_1,S_2,\ldots,S_{16000}$ be subsets of $A$ such that $|S_i|=80$ for all $i$. Show that for some $i\neq j$, we have $|S_i\cap S_j|\geq4$.
I want to suppose for contradiction that $|S_i\cap S_j|<4$ for all $i\neq j$. Then maybe the sets $S_i$'s need to be too "spread out" so that it's impossible to construct them when we have only $1600$ elements. But I don't know how to capture the "spreading out".
 A: Let $n=80$, so we have $200n$ subsets $S_i$ of $n$ elements each, out of a set $X$ of $20n$ elements. Have $a_k$ $($$0 \le k \le 200n$$)$ be the number of elements contained in exactly $k$ subsets. Then $$\mathcal{S}_0 = \sum_{k=0}^{200n} a_k = 20n$$ and $$\mathcal{S}_1 = \sum_{k=0}^{200n} ka_k = \sum_{1 \le i \le 200n} |S_i| = 200n^2.$$ Moreover, $$\mathcal{S}_2 = \sum_{k=0}^{200n} {{k(k-1)}\over2}a_k = \sum_{1 \le i < j \le 200n} |S_i \cap S_j|.$$
So for some $0 \le m \le 200n-1$ we solve the system $$a + bm = {{m(m-1)}\over2}, \text{ }a + b(m+1) = {{m(m+1)}\over2},$$ leading to $a = -{{m(m+1)}\over2}$, $b = m$. Then $$a + bk = -{{m(m+1)}\over2} + km \le {{k(k-1)}\over2}$$ for all $0 \le k \le 200n$, because equivalent to $(k-m)(k-(m+1)) \ge 0$ $($and with equality for $k \in \{m, m+1\}$$)$. Hence $$a\mathcal{S}_0 + b\mathcal{S}_1 \le \mathcal{S}_2.$$
Consider now the expression $N = a(20n) + b(200n^2)$, we want to maximize it. We have $$N = -{{m(m+1)}\over2}(20n) + m(200n^2) = 10nm(20n - (m+1)) \le 100n^2(10n - 1)$$ $($with equality for $m \in \{10n-1, 10n\}$$)$.
On the other hand, $\mathcal{S}_2$ has $100n(200n-1)$ terms, hence one of them is at least $$\left\lceil\frac{100n^2(10n-1)}{100n(200n-1)}\right\rceil = \left\lceil\frac{n(10n-1)}{200n-1}\right\rceil\geq \left\lceil\frac{10n^2-n}{200n}\right\rceil$$ $$= \left\lceil\frac{n}{20}-\frac{1}{200}\right\rceil = \left\lceil 4-\frac{1}{200}\right\rceil = 4.$$
A: I will provide a hint via a lemma.
Lemma: Let $X$ be a random variable. Then there is some point in the probability space where $X \ge E[X]$, and also some point in the probability space where $X \le E[X]$.
