Saturday, March 31, 2007

2007 MAO.

Good job to all Bellevue people at MAO State! We placed 3rd in Sweepstakes! That's the highest we've ever gotten in my four years :).

Tuesday, March 27, 2007

Condensation Sensation. Topic: Calculus/S&S.

Theorem: (Cauchy Condensation Test) If $ \displaystyle \{a_n\}_{n = 0}^{\infty} $ is a monotonically decreasing sequence of positive reals and $ p $ is a positive integer, then

$ \displaystyle \sum_{n=0}^{\infty} a_n $ converges if and only if $ \displaystyle \sum_{n=0}^{\infty} p^n a_{p^n} $ converges.

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

Problem: Determine the convergence of $ \displaystyle \sum_{n=2}^{\infty} \frac{1}{(\ln{n})^k} $, where $ k $ is a positive real.

Solution: Well, let's apply the Cauchy condensation test. Then we know that

$ \displaystyle \sum_{n=2}^{\infty} \frac{1}{(\ln{n})^k} $

converges if and only if

$ \displaystyle \sum_{n=2}^{\infty} \frac{p^n}{(\ln{p^n})^k} = \sum_{n=2}^{\infty} \frac{p^n}{(n \ln{p})^k} = \frac{1}{(\ln{p})^k} \sum_{n=2}^{\infty} \frac{p^n}{n^k} $

does. But this clearly diverges due to the fact that the numerator is exponential and the denominator is a power function. QED.

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

Comment: This is a pretty powerful test for convergence, at least in the situations in which it can be applied. The non-calculus proof for the divergence of the harmonic series is very similar to the Cauchy condensation test; in fact, the condensation test would state that

$ \displaystyle \sum_{n=1}^{\infty} \frac{1}{n} $ converges iff $ \displaystyle \sum_{n=1}^{\infty} \frac{p^n}{p^n} $ converges,

which clearly shows that the harmonic series diverges.

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

Practice Problem: Determine the convergence of $ \displaystyle \sum_{n=2}^{\infty} \frac{1}{(\ln{n})^{\ln{n}}} $.

Monday, March 26, 2007

Hey Now. Topic: Inequalities. Level: AIME.

Problem: Let $ a, b, c $ be positive reals such that $ a+b+c = 3 $. Prove that $ \sqrt{a}+\sqrt{b}+\sqrt{c} \ge ab+bc+ca $.

Solution: We play around and guess that $ \sqrt{a} \ge \frac{ab+ac}{2} $ because that would be convenient. Indeed, replacing $ b+c $ with $ 3-a $, this is equivalent to

$ \sqrt{a} \ge \frac{a(3-a)}{2} \Leftrightarrow 4a \ge a^2(3-a)^2 \Leftrightarrow (a-1)^2(4-a) \ge 0 $,

which is clearly true for $ 0 < a < 3 $. So we get the three inequalities

$ \sqrt{a} \ge \frac{ab+ac}{2} $, $ \sqrt{b} \ge \frac{bc+ba}{2} $, $ \sqrt{c} \ge \frac{ca+cb}{2} $.

Adding them up, we have the desired $ \sqrt{a}+\sqrt{b}+\sqrt{c} \ge ab+bc+ca $. QED.

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

Comment: I found this solution to be pretty clever, as the initial "guess" is not trivially true. But the whole thing works out quite nicely with symmetry so it's all good. Inequality problems usually require several random ideas and inspiration before finding the crux step.

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

Practice Problem: Let $ a, b, c $ be positive reals such that $ abc = 1 $. Prove that $ (a+b)(b+c)(c+a) \ge 2(1+a+b+c) $.

Tuesday, March 20, 2007

This Integral Not-Diverges. Topic: Calculus/S&S.

Problem: Show that the integral $ \displaystyle \int_0^{\infty} \frac{\sin{x}}{x}dx $ converges.

Solution: Consider the intervals $ [2k \pi, (2k+2) \pi] $ for $ k = 0, 1, 2, \ldots $. We can rewrite the given integral as

$ \displaystyle \int_0^{\infty} \frac{\sin{x}}{x}dx = \sum_{k=1}^{\infty} \int_{2k \pi}^{(2k+2) \pi} \frac{\sin{x}}{x} dx+C $,

where $ C $ is some unimportant constant. So how can we go about bounding the integral

$ \displaystyle \int_{2k \pi}^{(2k+2) \pi} \frac{\sin{x}}{x} dx $?

Well, first note that $ \sin{x} = - \sin{(x+\pi)} $ so we can say

$ \displaystyle \int_{2k \pi}^{(2k+2) \pi} \frac{\sin{x}}{x} dx = \int_{2k \pi}^{(2k+1)\pi} \left( \frac{\sin{x}}{x}+\frac{\sin{(x+\pi)}}{x+\pi} \right) dx = \int_{2k \pi}^{(2k+1)\pi} \left( \frac{\sin{x}}{x}-\frac{\sin{x}}{x+\pi}\right) dx $.

Then, putting the last expression under a common denominator, we get

$ \displaystyle \int_{2k \pi}^{(2k+1)\pi} \left( \frac{\sin{x}}{x}-\frac{\sin{x}}{x+\pi}\right) dx = \int_{2k \pi}^{(2k+1)\pi} \frac{\pi \sin{x}}{x(x+\pi)} dx $,

which we can easily bound with $ \sin{x} \le 1 $ and $ x \ge 2k \pi $. This gives us

$ \displaystyle \int_{2k \pi}^{(2k+1)\pi} \frac{\pi \sin{x}}{x(x+\pi)} dx < [(2k+1)\pi-2k \pi] \cdot \frac{\pi}{(2k \pi)(2k \pi + \pi)} = \frac{1}{2k(2k+1)} $.

Hence we know that

$ \displaystyle \int_0^{\infty} \frac{\sin{x}}{x}dx = \sum_{k=1}^{\infty} \int_{2k \pi}^{(2k+2) \pi} \frac{\sin{x}}{x} dx+C < \sum_{k=1}^{\infty} \frac{1}{2k(2k+1)}+C $

and this converges by a $ p $-series test. QED.

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

Comment: A pretty neat problem, though it is a standard convergence/divergence exercise. I'm sure there are many ways of doing this, but it's always nice to come up with a cool way of showing that a series converges or diverges. It's also interesting to note that the practice problem integral, which is only slightly different from this one, diverges.

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

Practice Problem: Show that the integral $ \displaystyle \int_0^{\infty} \frac{|\sin{x}|}{x}dx $ diverges.

Sunday, March 18, 2007

LaTeX In Comments.

The function to use LaTeX in comments has been added. Simply enclose your LaTeX code in [ tex ] and [ /tex ] tags (without spaces).

Saturday, March 17, 2007

Frogger. Topic: Combinatorics. Level: AIME.

Problem: (2007 AIMEI - #6) A frog is placed at the origin on the number line, and moves according to the following rule: in a given move, the frog advances to either the closest point with a greater integer coordinate that is a multiple of $ 3 $, or to the closest point with a greater integer coordinate that is a multiple of $ 13 $. A move sequence is a sequence of coordinates which correspond to valid moves, beginning with $ 0 $, and ending with $ 39 $. For example, $ 0, 3, 6, 13, 15, 26, 39 $ is a move sequence. How many move sequences are possible for the frog?

Solution: Let $ S_k $ be the number of possible move sequences starting from $ 0 $ and ending up at $ k $. Clearly it is only interesting when $ k $ is divisible by $ 3 $ or $ 13 $. So let's try to construct the sequence.

$ S_0 = 1 $ is our base case. There is only one way to get to the value $ 3 $ from $ 0 $, so $ S_3 = 1 $. Similarly, $ S_6 = 1 $, $ S_9 = 1 $, and $ S_{12} = 1 $. But how many ways can we get to $ 13 $? Well, if we start at any of the previously mentioned numbers there we can go straight to $ 13 $ from them (by using the next multiple of $ 13 $ move). So

$ S_{13} = S_0+S_3+S_6+S_9+S_{12} = 5 $.

Now how about $ S_{15} $? Well we can get there from either $ 12 $ or $ 13 $, so

$ S_{15} = S_{12}+S_{13} = 6 $.

Continuing, we have $ S_{18} = S_{21} = S_{24} = 6 $ because we can only get to these from the previous multiples of $ 3 $. Then

$ S_{26} = S_{13}+S_{15}+S_{18}+S_{21}+S_{24} = 29 $.

In this similar fashion, we obtain $ S_{27} = S_{30} = S_{33} = S_{36} = 35 $ and finally $ S_{39} = S_{26}+S_{27}+S_{30}+S_{33}+S_{36} = 169 $. QED.

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

Comment: This is a cool problem, though they could have made it harder to brute force (i.e. have the answer be $ 500+ $) to really weed out the people who did not actually know how to intelligently count it. It is based on a nice recursive concept known as "dynamic programming," which is one of the coolest computer science techniques ever. The idea is to use solutions of subproblems to construct the solution to a larger problem, like in this case using smaller values of $ S_k $ to calculate $ S_{39} $.

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

Practice Problem: (2007 AIMEI - #1) How many positive perfect squares less than $ 10^6 $ are multiples of $ 24 $?

Thursday, March 15, 2007

2007 AIME I Report.

So, overall, it appears that this AIME was not particularly difficult, but allowed people to make copious mistakes and drop their scores significantly. Cool... not. But anyway, some brief comments.

1. Decent NT, a good problem to start off with, though slightly more difficult than it usually is.
2. BIG paragraph, lots of text. Tripped up many people due to misreadings, but otherwise decent.
3. Easy? Just expand.
4. Stupid, more a test of your ability to think of what the test writers were thinking of than math.
5. Kind of lame, but easy enough to not be a problem. Just takes a little time.
6. Cool problem, dynamic programming comes in handy here.
7. Also pretty nice, good exercise in logs and summations.
8. Not bad either, I did not recognize the solution at first. In the end, it came down to the Euclidean Algorithm for polynomials basically.
9. Decent geometry, but quite a long problem.
10. What? The only reasonable way to do this was brute force counting. Anything else would have been too hard to come up with.
11. Too easy and well-known. Something similar but more difficult has shown up on the Putnam.
12. Eww... anything involving three different radicals should not be allowed.
13. Still not sure how to do this, but it seemed reasonable to most people.
14. Too easy to guess, but a cool problem nonetheless. Recurrences are a lot cooler than ugly geometry or counting.
15. Way beyond me, I do not like geometry problems as number 15.

So there we go! You can find the problems here if you so wish.

Monday, March 12, 2007

MORE Mu Alpha Theta Practice Tests.

You can reach any test by going to the URL “http://wangsblog.com/jeffrey/TestName.pdf” where TestName may be replaced by any of the following:

AlgebraII_St01
Alpha_Individual_St01
Answers_St01
Cipher_St01
Euclid_AlgGeo_St01
Gemini_St01
Geometry_Class_St01
Mu_ABCalculus_St01
Mu_BCCalculus_St01
Mu_Individual_St01
Open_NumTheory_St01
Open_Probability_St01
Open_SeqSer_St01
Theta_AlgGeom_St01
Theta_Individual_St01
Theta_Probability_St01
Trig_Class_St01

So, for example, if I wanted the Open Number Theory test I would go to “http://wangsblog.com/jeffrey/Open_NumTheory_St01.pdf”. Not all of these tests are around, but this should give you some idea of what to expect.

Sunday, March 11, 2007

Da Roots. Topic: Algebra/Complex Numbers Level: AIME.

Problem: (2007 Mock AIME 6 - #7) Let $ P_n(x) = 1+x+x^2+\cdots+x^n $ and $ Q_n(x) = P_1 \cdot P_2 \cdots P_n $ for all integers $ n \ge 1 $. How many more distinct complex roots does $ Q_{1004} $ have than $ Q_{1003} $?

Solution: Well, $ P_n(x) $ is familiar. Rewrite as

$ P_n(x) = \frac{x^{n+1}-1}{x-1} $,

i.e. the $ (n+1)-$th roots of unity except $ 1 $. Since $ Q_{1004} $ just contains a $ P_{1004} $ term that $ Q_{1003} $ doesn't have, we only need to think about that term in relation to the previous ones. So we want to find out how many of the $ 1004+1 = 1005 $th roots of unity are not $ k $-th roots of unity for any $ k < 1005 $. Well, recalling that any $ k $-th root of unity can be written as

$ e^{2 \pi i \frac{p}{k}} = \cos{\left(2 \pi \frac{p}{k}\right)}+i \sin{\left(2 \pi \frac{p}{k}\right)} $

for $ p = 0, 1, \ldots, k-1 $, it remains to find the number of $ p $ such that $ \frac{p}{1005} $ does not reduce. But this, of course, is simply $ \phi(1005) = 1005\left(1-\frac{1}{3}\right)\left(1-\frac{1}{5}\right)\left(1-\frac{1}{67}\right) = 2 \cdot 4 \cdot 66 = 528 $. QED.

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

Comment: Definitely one of my favorite problems on the test because it has a really nice and clean solution once you see it. And it wasn't too difficult to see either; combining a little knowledge of roots of unity with a little knowledge of the $ \phi $ function made it a good problem. Furthermore, it offers the nice generalization that

$ Q_n $ has $ \phi(n+1) $ more distinct roots than $ Q_{n-1} $.

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

Practice Problem: (2007 Mock AIME 6 - #8) A sequence of positive reals is defined by $ a_0 = x $, $ a_1 = y $, and $ a_n \cdot a_{n+2} = a_{n+1} $ for all integers $ n \ge 0 $. Given that $ a_{2007}+a_{2008} = 3 $ and $ a_{2007} \cdot a_{2008} = \frac{1}{3} $, find $ x^3+y^3 $.

Tuesday, March 6, 2007

Mu Alpha Theta Reviews.

I have added three review packets for people who want to review or learn new stuff for Mu Alpha Theta:

MAO Number Theory Review

MAO Calculus Review

MAO Sequences & Series Review

In my opinion, if you read these even semi-thoroughly, you will improve your score by a lot at the competition.

Monday, March 5, 2007

Criss Cross Applesauce. Topic: Geometry. Level: AIME.

Problem: (2007 Mock AIME 6 - #2) Draw in the diagonals of a regular octagon. What is the sum of all distinct angle measures, in degrees, formed by the intersections of the diagonals in the interior of the octagon?

Solution: Consider the circumscribed circle of the octagon. Each diagonal is a chord of this circle, and we know that the angle between two chords that intercept arcs of measure $ \alpha $ and $ \beta $ is $ \frac{\alpha+\beta}{2} $.

Now, any pair of diagonals can together intercept $ 2 $, $ 3 $, $ 4 $, $ 5 $, or $ 6 $ little arcs (between vertices of the octagon). $ 1 $ is not possible, because then on one side there is no little arc which means the intersection is not in the interior. This also means $ 7 $ is not possible (they come in supplement pairs - except $ 90^{\circ} $ of course). Since each little arc is $ 45^{\circ} $ and we have to account for the division by $ 2 $, the final sum is

$ 45 \cdot \frac{1}{2} \cdot (2+3+4+5+6) = 450 $.

QED.

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

Comment: This wasn't an extremely hard problem, but it needed some clever thinking. Most people overcounted, which is reasonable given that there are $ 20 $ diagonals in an octagon. Pretty hard to draw accurately. Using arcs on a circle proved to be much easier and less prone to careless mistakes.

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

Practice Problem: Let $R$ be a set of $13$ points in the plane, no three of which lie on the same line. At most how many ordered triples of points $(A,B,C)$ in $R$ exist such that $\angle ABC$ is obtuse?

Friday, March 2, 2007

More Mu Alpha Theta Practice... Do It!

You can reach any test by going to the URL “http://wangsblog.com/jeffrey/2002MAO/TestName.pdf” where TestName may be replaced by any of the following:

AdvAlgebra
AlphaIndividual
AlphaNumTheory
Answers (for all tests)
CalculusAB
Ciphering
EuclidAlgGeom
Gemini
GeometryClass
MuIndividual
MuNumTheory
MuProbability
OpenSeqSeries
ThetaAlgGeom
ThetaIndividual
ThetaNumTheory
ThetaProbability
TrigClass

So, for example, if I wanted the Mu Number Theory test I would go to “http://wangsblog.com/jeffrey/2002MAO/MuNumTheory.pdf”. Not all of these tests are around, but this should give you some idea of what to expect.