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

Sunday, December 24, 2006

Gimme That! Topic: Sets. Level: AIME/Olympiad.

Problem: (1996 Putnam - B1) Define a selfish set to be a set which has its own cardinality (number of elements) as an element. Find, with proof, the number of subsets of $ \{1, 2, \ldots, n\} $ which are minimal selfish sets, that is, selfish sets none of whose proper subsets is selfish.

Solution: We define $ S_n $ to be the desired number. Trying small cases, we get

$ S_1 = 1: \{1\} $

$ S_2 = 1: \{1\} $

$ S_3 = 2: \{1\}; \{2, 3\} $

$ S_4 = 3: \{1\}; \{2, 3\}; \{2, 4\} $

$ S_5 = 5 $ and $ S_6 = 8 $.

Well now we're tempted to say that $ S_n = F_n $, the $ n $th Fibonnaci number (with $ F_1 = F_2 = 1 $). To do so, we want to find a bijection between the minimal selfish subsets of $ T_n = \{1, 2, \ldots, n\} $ and the minimal selfish subsets of $ T_{n-1} = \{1, 2, \ldots, n-1\} $ and $ T_{n-2} = \{1, 2, \ldots, n-2\} $.

Clearly all the minimal selfish subsets of $ T_{n-1} $ are in $ T_n $ as well. The remaining minimal selfish subsets of $ T_n $ are those which contain the element $ n $. Consider the following bijection between the minimal selfish subsets of $ T_n $ containing $ n $ and the minimal selfish subsets of $ T_{n-2} $:

$ P = \{a_1, a_2, \ldots, a_k, n\} \leftrightarrow Q = \{a_1-1, a_2-1, \ldots, a_k-1\} $.

Clearly $ a_i > 1 $ because otherwise $ \{a_i\} $ would be a selfish subset. Also, $ a_k \le n-1 $. Hence the mapping works both ways; it remains to show that if one is a minimal selfish subset, so is the other. Since $ |P| = |Q|+1 $, we know that both are selfish or neither of them is. Furthermore, if $ P $ contains a selfish subset $ \{b_1, b_2, \ldots, b_k\} $, $ Q $ will contain the selfish subset $ \{b_1-1, b_2-1, \ldots, b_{k-1}-1\} $ and if $ Q $ contains the selfish subset $ \{c_1, c_2, \ldots, c_k\} $ then $ P $ will contain the selfish subset $ \{c_1+1, c_2+1, \ldots, c_k+1, n\} $. So the bijection works.

That means we have $ S_n = S_{n-1}+S_{n-2} $ so $ S_n = F_n $, as desired. QED.

--------------------

Comment: Decently hard for a B1, at the least the part that involved rigorously proving that the mapping is actually a bijection. It was pretty easy to figure out what the answer was, but as usual much more difficult to prove it.

--------------------

Practice Problem: (1996 Putnam - A1) Find the least number $ A $ such that for any two squares of combined area $ 1 $, a rectangle of area $ A $ exists such that the two squares can be packed in the rectangle (without interior overlap). You may assume that the sides of the squares are parallel to the sides of the rectangle.

Friday, December 22, 2006

Leftovers. Topic: Algebra/Polynomials. Level: AIME.

Problem: (Stanford Putnam Practice) Find the remainder when you divide $ x^{81}+x^{49}+x^{25}+x^9+x $ by $ x^3-x $.

Solution: Since they're both divisible by $ x $, we first divide that out, and just remember to multiply the remainder by $ x $ at the end. Let $ xP(x) $ be the first polynomial and $ xQ(x) $ be the second. we have

$ P(x) = g(x)Q(x)+r(x) $

for some polynomials $ g(x), r(x) $ with $ \deg(r) < deg(Q) = 2 $. We want to find $ r(x) $. Consider the two roots of $ Q(x) = x^2-1 = (x+1)(x-1) $. Plugging them into the equation, we obtain

$ P(1) = r(1) $ and $ P(-1) = r(-1) $.

Evaluating $ P $ at those two values, we find that

$ r(1) = 5 $ and $ r(-1) = 5 $.

But since $ r $ has degree less than $ 2 $, the only possible $ r $ is the constant polynomial $ r(x) = 5 $. Then the remainder is $ xr(x) = 5x $. QED.

--------------------

Comment: This is a super important technique when it comes to polynomial division. Using the $ \deg(Q) $ roots of $ Q $ and the fact that $ deg(r) < deg(Q) $, we can hypothetically always determine $ r $ this way, without dividing. This usually comes up when $ Q $ has nice roots, so if it doesn't, look for a better way.

--------------------

Practice Problem: (Stanford Putnam Practice) How can the quadratic equation

$ \frac{(x-a)(x-b)}{(c-a)(c-b)}+\frac{(x-b)(x-c)}{(a-b)(a-c)}+\frac{(x-c)(x-a)}{(b-c)(b-a)} = 1 $

have three roots $ x = a, b, c $? [Reworded]

Wednesday, December 20, 2006

Strikethrough. Topic: Geometry/NT. Level: AIME.

Problem: (Stanford Putnam Practice) Let $ P_1, P_2, \ldots , P_{2007} $ be distinct points in the plane. Connect the points with the line segments $ P_1P_2, P_2P_3, \ldots, P_{2006}P_{2007}, P_{2007}P_1 $. Can one draw a line that passes through the interior of every one of these segments?

Solution: Playing around with pictures for a while, our intuition says that since $ 2007 $ is odd, this is impossible. Now let's try to prove it. Suppose there exists such a line $ l $. Then we know that the endpoints of each line segment lie on opposite sides of the line. So

$ P_1 $ and $ P_2 $ lie on opposite sides of $ l $;

$ P_2 $ and $ P_3 $ lie on opposite sides of $ l $;

$ \cdots $

$ P_{2007} $ and $ P_1 $ lie on opposite sides of $ l $.

But wait, by a simple induction we know that $ P_1, P_3, P_5, \ldots, P_{2007} $ lie on the same side. That gives us the contradiction we seek. Thus $ l $ does not exist, as desired. QED.

--------------------

Comment: Not a bad problem, though pretty simple after you realized that you could fix the line before the points. It's easy to see that this generalizes to any set of an odd number of points (try the sides of a triangle, for example), so we have proven in fact a decently strong result.

--------------------

Practice Problem: (Stanford Putnam Practice) Show that if every room in a house has an even number of doors, then the number of outside entrance doors must be even as well.

Tuesday, December 19, 2006

I Am The Greatest (Common Divisor)! Topic: Number Theory. Level: Olympiad.

Problem: (Stanford Putnam Practice) Suppose $ (a_i)_{i \ge 1} $ is a sequence of positive integers satisfying $ \gcd(a_i, a_j) = \gcd(i, j) $ for $ i \neq j $. Show that $ a_i = i $ for each $ i $.

Solution: Let $ n $ be an arbitrary positive integer. If we can show that $ a_n = n $ we will be done. We have

$ \gcd(a_n, a_{2n}) = \gcd(n, 2n) = n $

so $ n|a_n $. Then $ a_n = kn $ for some positive integer $ k $. Similarly, we know $ kn|a_{kn} $ so $ a_{kn} = ckn $ for some positive integer $ c $. Then, however,

$ \gcd(a_n, a_{kn}) = (kn, ckn) = kn $ and $ \gcd(n, kn) = n $

so we must have $ kn = n \Rightarrow k = 1 $. Thus $ a_n = n $. QED.

--------------------

Comment: At first, induction seemed the way to go, but after a while you realize that the induction step is, well, not very likely since $ a_1 = 1, a_2 = 2, \ldots, a_k = k $ puts very few restrictions on $ a_{k+1} $. So then you look to a better option, trying to find the strongest use of $ \gcd(i, j) $. It turns out that this happens when $ j $ is a multiple of $ i $, which is exactly how the above proof starts.

--------------------

Practice Problem: (Stanford Putnam Practice) Let $ p > 5 $ be a prime number. Show that $ p $ divides infinitely many of the numbers

$ 1, 11, 111, 1111, \ldots $.

[Reworded]

Sunday, December 17, 2006

Toast To Euclid. Topic: Number Theory. Level: AMC/AIME.

Introduction: (Euclid's Algorithm) Given two positive integers $ a, b $, we can determine $ \gcd(a,b) $ through the following algorithm. Let $ a = bq+r $, where $ q, r $ are positive integers such that $ 0 \le r < b $. If $ r = 0 $, then $ \gcd(a, b) = b $. Otherwise, let $ a = b $, $ b = r $, and repeat. For example, if we wanted to find $ \gcd(140, 98) $, we would do

$ 140 = 98 \cdot 1+42 $

$ 98 = 42 \cdot 2+14 $

$ 42 = 14 \cdot 3+0 $

so $ \gcd(140,98) = 14 $. A proof of this result is left to the reader.

--------------------

Problem: (Stanford Putnam Practice) Prove that consecutive Fibonacci numbers are always relatively prime.

Solution: Well, since we had a handy introduction to Euclid's Algorithm up there, let's try to use it. We want to calculate $ \gcd(F_{n+1}, F_n) $. Executing the algorithm, we get

$ F_{n+1} = F_n \cdot 1+F_{n-1} $

$ F_n = F_{n-1} \cdot 1+F_{n-2} $

$ F_{n-1} = F_{n-2} \cdot 1+F_{n-3} $.

Hmm, is there a pattern? I think so! We eventually get

$ F_3 = F_2 \cdot 1+F_1 $

$ F_2 = F_1 \cdot 2+0 $.

So $ \gcd(F_{n+1}, F_n) = F_1 = 1 $, as desired. QED.

--------------------

Comment: Euclid's Algorithm is an extremely powerful tool for computing greatest common divisors. It even comes in handy in computer science, where we can write a very simple recursive method to compute $ \gcd(a,b) $. For example

int gcd(int a, int b)
{
if(b > a) swap(a,b);
if(b == 0) return a;
a %= b;
return gcd(b, a);
}

Tuesday, December 12, 2006

Complexity. Topic: Complex Numbers/Polynomials. Level: AIME/Olympiad.

Problem: Let $ f(x) = x^{2004}+2x^{2003}+\cdots+2004x+2005 $. If $ z = \cos{\frac{\pi}{1003}}+i \sin{\frac{\pi}{1003}} $ and

$ N = f(z)f(z^2) \cdots f(z^{2005}) $,

find the remainder when $ N $ is divided $ 1000 $. [Reworded]

Solution: Well $ f $ is pretty ugly looking at the moment, let's fix that. We can write it as the sum of the following series:

$ 1+x+x^2+\cdots+x^{2004} = \frac{x^{2005}-1}{x-1} $

$ 1+x+x^2+\cdots+x^{2003} = \frac{x^{2004}-1}{x-1} $

$ \cdots $

$ 1+x = \frac{x^2-1}{x-1} $

$ 1 = \frac{x-1}{x-1} $,

since all of them are geometric series with common ratio $ x $. Summing these up, we have

$ f(x) = \frac{x^{2005}+x^{2004}+\cdots+x+1-2006}{x-1} $.

The top is again a geometric series with common ratio $ x $ (without that $ 2006 $ part) so we can write it ias

$ f(x) = \frac{\frac{x^{2006}-1}{x-1}-2006}{x-1} $.

But wait, if $ x = z^k $ then $ x^{2006} = (z^k)^{2006} = (z^{2006})^k = 1 $, so in fact we have

$ f(z^k) = \frac{2006}{1-z^k} $.

Then $ N = \frac{2006^{2005}}{(1-z)(1-z^2) \cdots (1-z^{2005}) $ so it remains the evaluate the denominator of that. Considering

$ g(x) = (x-z)(x-z^2) \cdots (x-z^{2005}) $

we are like whoa, $ g $ has the $ 2006 $th roots of unity for its roots except $ x = 1 $ and it has leading coefficient $ 1 $ so it must be

$ g(x) = x^{2005}+x^{2004}+\cdots+1 \Rightarrow g(1) = (1-z)(1-z^2) \cdots (1-z^{2005}) = 2006 $.

Hence

$ N = \frac{2006^{2005}}{g(1)} = 2006^{2004} $.

By Euler's Totient Theorem, $ N \equiv 6^4 \equiv 296 \pmod{1000} $. QED.

--------------------

Comment: It didn't take too much "insight" to reduce $ f $ to the nicer expression, more like just tedious evaluation of geometric series galore. Seeing the product in the denominator should have been pretty familiar (though I admit I forgot what it came out to at first) and a standard argument allowed you to evaluate it. Possibly the hardest part was Euler's Totient Theorem, which is invaluable to carry around for the AIME. Also knowing that $ \phi(1000) = 400 $.

--------------------

Practice Problem: Do there exist polynomials $ P(x) $ and $ Q(x) $ such that

$ (x^8-1)P(x)+(x^5-1)Q(x) = x-1 $?

If so, find them.

Sunday, December 10, 2006

Just... Right. Topic: Calculus/Inequalities. Level: AIME/Olympiad.

Problem: (Stanford Putnam Practice) Let $ f $ be continuous and monotonically increasing, with $ f(0) = 0 $ and $ f(1) = 1 $. Prove that

$ \displaystyle f(1/10)+f(2/10)+\cdots+f(9/10)+f^{-1}(1/10)+f^{-1}(2/10)+\cdots+f^{-1}(9/10) \le \frac{99}{10} $.

Solution: We can easily generalize this to

$ \displaystyle \sum_{k=1}^{n-1} [f(k/n)+f^{-1}(k/n)] \le \frac{n^2-1}{n} $,
so we will prove this instead. Consider the value of $ \displaystyle \int_0^1 [f(x)+f^{-1}(x)]dx $. This integrates across the area of the unit square with opposite vertices $ (0,0) $ and $ (1,1) $ so the integral is $ 1 $. Visualize this with a picture. Now we use a left-hand Riemann sum approximation on both $ f(x) $ and $ f^{-1}(x) $ with $ n-1 $ subdivisions from $ \frac{1}{n} $ to $ 1 $ to get

$ \displaystyle \int_0^{\frac{1}{n}} [f(x)+f^{-1}(x)]dx+\frac{1}{n}\sum_{k=1}^{n-1} [f(k/n)+f^{-1}(k/n)] \le \int_0^1 [f(x)+f^{-1}(x)]dx = 1 $.

Then it remains to show that

$ \displaystyle \int_0^{\frac{1}{n}} [f(x)+f^{-1}(x)]dx \ge \frac{1}{n^2} $.

But from the argument above we know covers at least the square with opposite vertices $ (0,0) $ and $ \left(\frac{1}{n},\frac{1}{n}\right) $, which has area $ \frac{1}{n^2} $. Again, draw a picture (it's the same as before except without the endpoint restriction). Hence we have shown that

$ \displaystyle \sum_{k=1}^{n-1} [f(k/n)+f^{-1}(k/n)] \le \frac{n^2-1}{n} $,

as desired. QED.

--------------------

Comment: This was a pretty interesting problem; it was pretty clear from the beginning that you were approximating some kind of interval and it looked a lot like Riemann sums so that seemed to be the method of choice. After that, a little knowledge about function inverses and a couple of nice pictures gave the rest of the solution.

--------------------

Practice Problem: (Stanford Putnam Practice) Let $ a_0 $ be an arbitrary positive integer and let

$ a_{n+1} = \frac{1}{a_n}+1 $ for $ n \ge 0 $.

Determine if $ \lim_{n \rightarrow \infty} a_n $ exists and if so, evaluate it. [Reworded]

Saturday, December 9, 2006

eek! Topic: Calculus/S&S. Level: AIME/Olympiad.

Problem: (Problem-Solving Through Problems - 5.4.15) Let $ f_0(x) = e^x $ and $ f_{(n+1)}(x) = xf^{\prime}(x) $ for $ n = 0, 1, 2, \ldots $. Show that

$ \displaystyle \sum_{n=0}^{\infty} \frac{f_n(1)}{n!} = e^e $.

Solution: Well, the LHS looks suspiciously like a Taylor series, so maybe we can find a function. A good choice is $ g(x) = e^{e^x} $. Notice that $ f_0(x) = g(\ln{x}) $. Testing a few derivatives, we hypothesize that

$ f_n(x) = g^{(n)}(\ln{x}) $.

By induction, we easily have

$ \frac{d}{dx}[g^{(n)}(\ln{x})] = g^{(n+1)}(\ln{x}) \cdot \frac{1}{x} $,

which exactly satisfies

$ g^{(n+1)}(\ln{x}) = x \frac{d}{dx}[g^{(n)}(\ln{x})] $

so we indeed have $ f_n(x) = g^{(n)}(\ln{x}) $. Then $ f_n(1) = g^{(n)}(0) $ and the Taylor series of $ g $ centered at zero is

$ \displaystyle \sum_{n=0}^{\infty} \frac{g^{(n)}(0)x^n}{n!} = \sum_{n=0}^{\infty} \frac{f_n(1)x^n}{n!} $.

Hence our desired sum is the above series evaluated at $ x = 1 $, which is simply

$ g(1) = e^{e^{1}} = e^e $.

QED.

--------------------

Comment: A neat problem resulting from Taylor series. They are useful in all sorts of ways, especially evaluating other series. If we can reduce a given series to the Taylor series of a function like we did in this problem, evaluating it becomes plugging in a point.

--------------------

Practice Problem: (Problem-Solving Through Problems - 5.4.17) Show that the functional equation

$ \displaystyle f\left(\frac{2x}{1+x^2}\right) = (1+x^2)f(x) $

is satisfied by

$ f(x) = 1+\frac{1}{3}x^2+\frac{1}{5}x^4+\frac{1}{7}x^6+\cdots $ with $ |x| < 1 $.

Wednesday, December 6, 2006

Digit To The Unit. Topic: Algebra. Level: AIME.

Problem: (2006-2007 Warm-Up 5 - #13) Determine the units digit in the decimal expansion of $ (20+\sqrt{397})^{2674} $.

Solution: Well, in its current form it is quite an ugly expression, with half of the terms involving a radical. Maybe we can simplify this, a.k.a. get rid of the radicals. Consider

$ (20+\sqrt{397})^{2674}+(20-\sqrt{397})^{2674} $.

Since we know $ 20-\sqrt{397} < 1 $, then $ (20-\sqrt{397})^{2674} \rightarrow 0 $ (it's really small). The above expression is an integer because all of the radical terms cancel out. So if we find the units digit of this, we simply subtract one away and get the units digit of our original number. But this number is just

$ 2(20^{2674}+\cdots+397^{1337}) $,

where every term in between is divisible by $ 20 $. That means they all have a units digit of zero, so we only need to look at the last term. Since powers of $ 7 $ repeat the sequence

$ 7, 9, 3, 1 \pmod{10} $,

we know $ 397^{1337} \equiv 7^{1337} \equiv 7 \pmod{10} $. So twice of this would give a units digit of $ 4 $. Subtracting one away as we mentioned above gives us a units digit of $ 3 $. QED.

--------------------

Comment: This is an excellent application of the binomial theorem and a good test of your intuition, which basically consisted of noticing $ 20^2 \approx 397 $. The power $ 2674 $ was an arbitrary even number; in fact, for smaller powers we notice the exact same thing:

$ (20+\sqrt{397})^2 \approx 1593.99 $.

--------------------

Practice Problem: Determine how many elements of the $ n $th row of Pascal's Triangle are odd.

Tuesday, December 5, 2006

2006 Math Is Cool Tests.

Practice Tests:

2006 Math Is Cool

NOTE: Thanks a lot to Jacob for scanning the tests and getting them to me (a long time ago)! Also, if you want to look at them, try to download them to your own computer; having to load them every time is no fun.

Monday, December 4, 2006

Yay! Putnam! Part 2. Topic: Sets. Level: AIME/Olympiad.

Problem: (2006 Putnam - B2) Prove that, for every set $ X = \{x_1, x_2, \ldots, x_n\} $ of $ n $ real numbers, there exists a non-empty subset $ S $ of $ X $ and an integer $ m $ such that

$ \displaystyle \left|m+\sum_{s \in S} s\right| \le \frac{1}{n+1} $.

Solution: Essentially, it's telling us to find a subset such that the sum of the elements has fractional part $ \le \frac{1}{n+1} $ or $ \ge \frac{n}{n+1} $. Consider the partial sums of $ X $, i.e.

$ t_1 = x_1 $

$ t_2 = x_1+x_2 $

$ \cdots $

$ t_n = x_1+x_2+\cdots+x_n $.

Now partition the interval $ [0,1) $ into $ n+1 $ intervals of length $ \frac{1}{n+1} $, like so:

$ \left[0, \frac{1}{n+1}\right]; \left(\frac{1}{n+1}, \frac{2}{n+1}\right); \left[\frac{2}{n+1}, \frac{3}{n+1}\right); \cdots ;\left[\frac{n-1}{n+1}, \frac{n}{n+1}\right); \left[\frac{n}{n+1}, 1) $.

Let $ \{t_i\} $ denote the fractional part of $ t_i $. Clearly if $ \{t_i\} \in \left[0, \frac{1}{n+1}\right] $ or $ \{t_i\} \in \left[\frac{n}{n+1}, 1\right) $, the problem is solved because we simply choose $ t_i $ and the closest integer to it. If, on the other hand, none of the $ \{t_i\} $ fall into these sets, they must all be in the intervals

$ \left(\frac{1}{n+1}, \frac{2}{n+1}\right); \left[\frac{2}{n+1}, \frac{3}{n+1}\right); \cdots ;\left[\frac{n-1}{n+1}, \frac{n}{n+1}\right) $.

Since there are exactly $ n-1 $ of these and we have $ n $ $ \{t_i\} $'s, by the Pigeonhole Principle we know two such $ \{t_i\} $ fall into the same interval, say $ \{t_j\} $ and $ \{t_k\} $ with $ j < k $. Then we choose the set $ S = \{x_{j+1}, x_{j+2}, \ldots, x_k\} $. The sum of the elements is

$ \displaystyle x_{j+1}+x_{j+2}+\cdots+x_k = t_k-t_j $,

which satisfies

$ |\{t_k\}-\{t_j\}| \le \frac{1}{n+1} $.

This however, means that

$ \{t_k-t_j\} \le \frac{1}{n+1} $ or $ \{t_k-t_j\} \ge \frac{n}{n+1} $,

meaning that the set $ S = \{x_{j+1}, x_{j+2}, \ldots, x_k\} $ satisfies the desired property by choosing the appropriate $ m $, which is the closest integer to the sum. QED.

--------------------

Comment: This was a pretty standard pre-olympiad level pigeonhole problem, though it had some interesting notation which I suspect threw some people off. Plus the fact that the property we are to prove is quite weak in that we only have to look at sets of consecutive elements. In any case, it was fun though a bit on the simple side.

--------------------

Practice Problem: (2006 Putnam - B5) For each continuous function $ f: [0,1] \rightarrow \mathbb{R} $, let $ I(f) = \int_0^1 x^2f(x)dx $ and $ J(f) = \int_0^1 x[f(x)]^2dx $. Find the maximum value of $ I(f)-J(f) $ over all such functions $ f $.

Sunday, December 3, 2006

Yay! Putnam! Topic: Algebra/Polynomials. Level: AIME.

Problem: (2006 Putnam - B1) Show that the curve $x^{3}+3xy+y^{3}=1$ contains only one set of three distinct points, $A$, $B$, and $C$, which are the vertices of an equilateral triangle, and find its area.

Solution: Well, this is a cubic in two variables, but let's remember the awesome technique of writing it as a polynomial in just one variable, say $ x $. Then

$ x^3+3xy+(y^3-1) = 0 $.

Well, testing out a bit (looking at the factorization of $ y^3-1 $), we get $ x = 1-y $ is always a solution, so factor it out to get

$ (x+y-1)[x^2+x(1-y)+(y^2+y+1)] = 0 $.

Looking at the second term, we're like let's hope it has not many solutions, so we take the discriminant and find

$ (1-y)^2-4(y^2+y+1) = -3y^2-6y-3 = -3(y+1)^2 $.

But this is always negative unless $ y = -1 $ so that means this is the only case in which this factor can be zero. This gives us the point $ (-1,-1) $ as a solution. Whoa, that means we have categorized the entire solution set:

(1) the line $ x+y = 1 $ and (2) the point $ (-1,-1) $.

If we have three vertices of an equilateral triangle, they most definitely can't be collinear, so one point must be $ (-1,-1) $. Suppose we choose two points on the line $ x+y = 1 $, say $ (x_0, 1-x_0) $ and $ (x_1, 1-x_1) $. Since they have to be equidistant from $ (-1, -1) $, we know one must be the reflection of the other over the line through $ (-1, -1) $ perpendicular to $ x+y = 1 $, which is $ x = y $. So if the first point is $ (x_0, 1-x_0) $ then the other is $ (1-x_0, x_0) $.

Now setting the squares of the side lengths equal to each other, we know

$ 2(2x_0-1)^2 = (x_0+1)^2+(2-x_0)^2 $

$ 2x_0^2-2x_0-1 = 0 $ so $ x_0 = \frac{1}{2} \pm \frac{\sqrt{3}}{2} $.

This gives the $ x $-coordinate of both the other two vertices of the triangle, so the only one is the equilateral triangle with vertices

$ (-1, -1); \left(\frac{1}{2}+\frac{\sqrt{3}}{2}, \frac{1}{2}-\frac{\sqrt{3}}{2}\right); \left(\frac{1}{2}-\frac{\sqrt{3}}{2}, \frac{1}{2}+\frac{\sqrt{3}}{2}\right) $.

The side length is $ \sqrt{6} $, so the area is $ \frac{6\sqrt{3}}{4} = \frac{3\sqrt{3}}{2} $. QED.

--------------------

Comment: Slightly difficult if your algebraic intuition wasn't working well, but after you realized the factorization it wasn't hard to convince yourself that a line and a point can have the vertices of at most one equilateral triangle. A solid B1 problem on the Putnam, quite a bit more difficult than the A1, imo.

--------------------

Practice Problem: (2006 Putnam - A1) Find the volume of the region of points $ (x,y,z) $ such that

$ (x^2+y^2+z^2+8)^2 \le 36(x^2+y^2) $.

Saturday, December 2, 2006

Seriously? No, Seriesly. Topic: Calculus/S&S. Level: AIME/Olympiad.

Problem: (Problem-Solving Through Problems - 6.9.11) Sum the series

$ 1+\frac{1}{3}-\frac{1}{5}-\frac{1}{7}+\frac{1}{9}+\frac{1}{11}-\frac{1}{13}-\cdots $.

Solution: Consider the function

$ f(x) = x+\frac{x^3}{3}-\frac{x^5}{5}-\frac{x^7}{7}+\frac{x^9}{9}+\frac{x^{11}}{11}-\cdots $,

where $ f(1) $ is the series in question. We will derive a closed form for $ f $ whenever $ |x| \le 1 $, since this guarantees convergence (alternating series test works here). Taking the derivative, we get

$ f^{\prime}(x) = (1+x^2)-(x^4+x^6)+(x^8+x^{10})-\cdots $,

which is clearly a geometric series with first term $ 1+x^2 $ and common ratio $ -x^4 $. Hence we can write $ f^{\prime} $ as

$ f^{\prime}(x) = \frac{1+x^2}{1+x^4} $.

Now we want to integrate so solve for $ f $, but this requires some partial fraction decomposition (ew!). I'll leave out the details, just notice that

$ \frac{1+x^2}{1+x^4} = \frac{1}{1+(x\sqrt{2}+1)^2}+\frac{1}{1+(x\sqrt{2}-1)^2} $,

so integrating we get

$ \displaystyle f(x) = \int_0^x \left(\frac{1}{1+(t\sqrt{2}+1)^2}+\frac{1}{1+(t\sqrt{2}-1)^2}\right)dt = \frac{1}{\sqrt{2}}\left(\arctan{(x\sqrt{2}+1)}+\arctan{(x\sqrt{2}-1)}\right) $.

Now it remains to plug in $ x = 1 $ to get

$ f(1) = \frac{1}{\sqrt{2}}\left(\arctan{(\sqrt{2}+1)}+\arctan{(\sqrt{2}-1)}\right) $.

Oh, no! What now? Well, we see that $ \frac{1}{\sqrt{2}+1} = \sqrt{2}-1 $, i.e. the arguments are reciprocals. But we know that $ \arctan{(z)} = \frac{\pi}{2}-\arctan{\left(\frac{1}{z}\right)} $ (think about a right triangle and the tangent from each of the angles). So

$ \frac{1}{\sqrt{2}}\left(\arctan{(\sqrt{2}+1)}+\arctan{(\sqrt{2}-1)}\right) = \frac{\pi}{2\sqrt{2}} \approx 1.11072 $.

QED.

--------------------

Comment: This technique is really neat for evaluating weird harmonic, alternating infinite series. Of course it doesn't always work, but I suspect that there are many problems that you can convert into something of this type and solve by differentiating and integrating.

--------------------

Practice Problem: (Problem-Solving Through Problems - 6.9.6) Suppose that $ f:[0,1] \rightarrow \mathbb{R} $ has a continuous second derivative, that $ f(0) = 0 = f(1) $, and that $ f(x) > 0 $ for all $ x $ in $ (0,1) $. Show that

$ \displaystyle \int_0^1 \left|\frac{f^{\prime\prime}(x)}{f(x)}\right|dx > 4 $.

Friday, December 1, 2006

Integra-what? Topic: Calculus/S&S.

Problem: Write $ I = \displaystyle \sum_{l_1=1}^{\infty} \sum_{l_2=1}^{\infty} \frac{(-1)^{l_1-1}}{l_1l_2(l_1+l_2)} $ as an integral.

Solution: We first notice that

$ \displaystyle \frac{(-1)^{l_1-1}}{l_1l_2(l_1+l_2)} = \frac{1}{l_1l_2} \int_0^1 (-x)^{l_1-1}x^{l_2} dx $.

So our summation becomes

$ \displaystyle I = \sum_{l_1=1}^{\infty} \sum_{l_2=1}^{\infty} \frac{1}{l_1l_2} \int_0^1 (-x)^{l_1-1}x^{l_2} dx $.

But we can switch the order of the integral with the two sums because $ \int (f+g) = \int f+\int g $. Hence we obtain

$ \displaystyle I = \int_0^1 \sum_{l_1=1}^{\infty} \left(\frac{(-x)^{l_1-1}}{l_1}\sum_{l_2=1}^{\infty} \frac{x^{l_2}}{l_2} \right) $.

We remember, however, that the Taylor series expansion of $ \displaystyle \ln{(1-x)} = -\sum_{n=1}^{\infty} \frac{x^n}{n} $, so substituting we have

$ \displaystyle I = -\int_0^1 \ln{(1-x)}\sum_{l_1=1}^{\infty} \frac{(-x)^{l_1-1}}{l_1} $.

Similarly, $ \displaystyle \ln{(1+x)} = -\sum_{n=1}^{\infty} \frac{(-x)^n}{n} $, so we replace one more time to get

$ \displaystyle I = -\int_0^1 \frac{1}{x} \ln{(1-x)} \ln{(1+x)} dx $.

QED.

--------------------

Comment: Transforming sums into integrals and vice versa are powerful techniques for evaluating these expressions. The numerical value turns out to be $ I = \frac{5}{8} \zeta(3) $, but we'll save that for another time...

--------------------

Practice Problem: (1978 Putnam - B2) Evaluate

$ \displaystyle \sum_{m=1}^{\infty} \sum_{n=1}^{\infty} \frac{1}{m^2n+n^2m+2mn} $.