# Mathematical Food for Thought

Serves a Daily Special and an All-You-Can-Eat Course in Problem Solving. Courtesy of me, Jeffrey Wang.

• ## Meta

Pretty Sorta Equal To. Topic: Sets. Level: AIME/Olympiad. December 27th, 2006

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

### 2 Responses to “Pretty Sorta Equal To. Topic: Sets. Level: AIME/Olympiad.”

1. Xuan Says:

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