Let $A_1, \ldots, A_k$ be subsets of $\{1, \ldots, n\}$ such that $|A_i| = m$ for each $i = 1,\ldots,k$ and $k>100n$. Prove that there exists two distinct sets $A_i, A_j$ such that $|A_i\cap A_j| \geq \frac{m^2}{10n}.$
I found this problem in the book Introduction to Theoretical Computer Science by Boaz Barak.
Here's my attempt: Suppose for contradiction that every pair of subsets satisfies $|A_i\cap A_j| < \frac{m^2}{10n}$. Then $$\sum_{1\leq i < j \leq k}|A_i\cap A_j| < {k\choose 2}\frac{m^2}{10n}.$$ It's also known from the principle of inclusion-exclusion that $$\left|\bigcup_{i=1}^k A_i\right| \geq \sum_{i=1}^k|A_i| - \sum_{1\leq i < j \leq k}|A_i\cap A_j|.$$ Then $$n\geq \left|\bigcup_{i=1}^k A_i\right| \geq \sum_{i=1}^k|A_i| - \sum_{1\leq i < j \leq k}|A_i\cap A_j| \geq km - {k\choose 2}\frac{m^2}{10n}$$ $$n^2 + {k\choose 2}\frac{m^2}{10n}\geq km.$$ I'm not sure how to proceed from here since it's pretty clear that the left side is bigger than the right side for large $n, m, k$ since it has a higher degree. Thanks in advance for any help.
Your approach doesn't seem to work because your lower bound for $\sum |A_i \cap A_j|$ is not sharp enough.
Let $a_i$ be number of sets $A_j$ that $i$ belongs to. Hence, we have $$\sum_{i=1}^n a_i= \sum_{i=1}^k|A_i|=mk \; \text{and} \; \sum_{i=1}^n \binom{a_i}{2} = \sum_{1 \le i<j \le k} |A_i \cap A_j|$$ We have the inequality $$\sum_{i=1}^n \binom{a_i}{2} = \frac 12 \left[ \sum_{i=1}^n a_i^2-mk\right] \ge \frac 12 \left[ \frac 1n \left(\sum_{i=1}^na_i\right)^2-mk\right]= \frac{mk}{2} \left( \frac{mk}{n}-1\right).$$ Therefore, $$ \binom{k}{2}|A_i \cap A_j|_{\max} \ge \frac{mk}{2}\left(\frac{mk}{n}-1\right).$$ We find $$|A_i\cap A_j|_{\max} \ge \frac{m}{k-1}\left(\frac{mk}{n}-1\right)> \frac{m^2}{n}-\frac{m}{k-1} \ge \frac{m^2}{n}-\frac{m}{100n}.$$