Pretty Sorta Equal To. Topic: Sets. Level: AIME/Olympiad.

Problem: (Stanford Putnam Practice) Let $ S = \{1, 2, \ldots n\} $ and let $ S_1, S_2, \ldots, S_n $ be subsets of $ S $ satisfying $ |S_i \cap S_j| $ for $ i \neq j $. Show that $ \max(|S_1|+|S_2|+\cdots+|S_n|) $ is asymptotically $ n \sqrt{n} $.

Solution: We will start by showing that the expression is at most asymptotically $ n\sqrt{n} $. Suppose it is asymptotically $ nk $. Then $ |S_i| \sim k $. And on average, any element will be contained in $ k $ of the $ S_i $. Consider the $ k $ sets that contain the element $ 1 $. The remaining $ k-1 $ elements of each subset must all be different, so there must be at least $ k(k-1)+1 $ elements in the original set. So $ k(k-1)+1 \sim n \Rightarrow k \sim \sqrt{n} $ is an upper bound. Now let's show that we can obtain this upper bound.

Let $ m $ be the closest integer to $ \sqrt{n} $. Partition $ S $ into $ m $ subsets, approximately the intervals $ (1, m); (m+1, 2m); \ldots ; (n-m+1, n) $. Each part should contain about $ m $ elements (because the argument is asymptotic, it doesn't really matter). Label them by $ a_{11}, a_{12}, \ldots, a_{1m}, a_{21}, a_{22}, \ldots, a_{mm} $ where $ a_{ij} $ is the $ j $th element of the $ i $th part. We want to choose $ n $ sets of $ m $ elements satisfying the conditions of the problem; we claim that we can do this by choosing one element from each interval for each set.

First, construct $ m $ sets:

$ \{a_{11}, a_{21}, a_{31}, \ldots, a_{m1}\} $

$ \{a_{12}, a_{22}, a_{32}, \ldots, a_{m2}\} $

$ \cdots $

$ \{a_{1m}, a_{2m}, a_{3m}, \ldots, a_{mm}\} $.

Then, to create the next $ m $ sets, we take the elements which lie along the same diagonal (supposing we had a copy of those sets), for instance,

$ \{a_{11}, a_{22}, a_{33}, \ldots a_{mm}\} $

$ \{a_{21}, a_{32}, a_{43}, \ldots a_{m(m-1)}, a_{1m}\} $

$ \{a_{31}, a_{42}, a_{53}, \ldots, a_{1(m-1)}, a_{2m}\} $

$ \cdots $

$ \{a_{m1}, a_{12}, a_{23}, \ldots, a_{(m-1)m}\} $.

In fact, if we repeat this process, we will get all $ n $ sets of $ m $ elements, none of which share more than a single element. Hence we know that the value is asymptotic to $ nm \sim n\sqrt{n} $. QED.

--------------------

Comment: The above proof is very "fuzzy." It lacks a lot of the rigor needed to actually prove the result, but it gives the basic idea, which is all I was aiming for. A solid proof of the result would probably be very long and tedious (unless some other elegant method is used, or perhaps some other strong known results).