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

1. Hey, this has nothing to do with ur question .. but how many AMC ques to I have to answer to get in? or pass.?
was it 17.. but they changed it ... so how many more? like 19??
2. 