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??
    wut about AMC 12?
    would the questions be any easier since this is the first year they're doing it this way?

  2. For the AMC 10 - 19 right, 4 blank will get you to the AIME. 20 right and you can guess all you want. Aim for 20.

    For the AMC 12 - 14 right, 11 blank will get you to the AIME. For every one more right, you can get 4 more wrong instead of leaving them blank. Aim for 15 or 16, and you should be set.

    The first 10 or so questions are supposed to be easier, so that should help scores stay relatively close to where they were previously.