## Tuesday, December 26, 2006

### 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).