Problem: (Stanford Putnam Practice) Let and let be subsets of satisfying for . Show that is asymptotically .
Solution: We will start by showing that the expression is at most asymptotically . Suppose it is asymptotically . Then . And on average, any element will be contained in of the . Consider the sets that contain the element . The remaining elements of each subset must all be different, so there must be at least elements in the original set. So is an upper bound. Now let’s show that we can obtain this upper bound.
Let be the closest integer to . Partition into subsets, approximately the intervals . Each part should contain about elements (because the argument is asymptotic, it doesn’t really matter). Label them by where is the th element of the th part. We want to choose sets of 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 sets:
Then, to create the next sets, we take the elements which lie along the same diagonal (supposing we had a copy of those sets), for instance,
In fact, if we repeat this process, we will get all sets of elements, none of which share more than a single element. Hence we know that the value is asymptotic to . 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).
Leave a Reply
You must be logged in to post a comment.