Saturday, July 7, 2007

What's Your Function? Topic: Algebra. Level: AMC/AIME.

Problem: Given two positive reals $ \alpha $ and $ \beta $, show that there is a continuous function $ f $ that satisfies $ f(x) = f(x+\alpha)+f(x+\beta) $.

Solution: There are several special cases that are interesting to look at before we make a guess as to what type of function $ f $ will be. First we consider the case $ \alpha = \beta = 1 $. This immediately gives

$ f(x) = 2f(x+1) $.

It should not be too difficult to guess that $ f(x) = 2^{-x} $ is a solution to this, as well as any constant multiple of it. Now try $ \alpha = -1 $ and $ \beta = -2 $, resulting in

$ f(x) = f(x-1)+f(x-2) $.

Looks a lot like Fibonacci, right? In fact, one possible function is just $ f(x) = \phi^x $. That's pretty convenient.

Notice how both of these illuminating examples are exponential functions, which leads us to guess that our function will be exponential as well. So, following this track, we set

$ f(x) = a^x $

so we simply need to solve

$ a^x = a^{x+\alpha}+a^{x+\beta} $

$ a^x = a^x\left(a^{\alpha}+a^{\beta}\right) $.

Unfortunately, the equation $ a^{\alpha}+a^{\beta} = 1 $ does not always have a solution (take $ \alpha = 1 $ and $ \beta = -1 $ for example). But that's ok and I'll worry about it some other time. In any case we have found a function for whenever the equation $ a^{\alpha}+a^{\beta} = 1 $ has a solution in the reals.

Friday, June 29, 2007

Addition At Its Finest. Topic: Calculus/S&S.

Problem: Evaluate $ \displaystyle \sum_{n=1}^{\infty} \frac{x^n}{n(n+1)} $ where $ x $ is a real number with $ |x| < 1 $.

Solution: Looking at that all too common denominator, we do a partial fraction decomposition in hopes of telescoping series. The summation becomes

$ \displaystyle \sum_{n=1}^{\infty} \left(\frac{x^n}{n}-\frac{x^n}{n+1}\right) $.

Common Taylor series knowledge tells us that

$ \displaystyle \ln{(1-x)} = -\left(x+\frac{x^2}{2}+\frac{x^3}{3}+\cdots\right) = -\sum_{n=1}^{\infty} \frac{x^n}{n} $,

which convenient fits the first part of the summation. As for the second part, we get

$ \displaystyle \sum_{n=1}^{\infty} \frac{x^n}{n+1} = \frac{1}{x} \sum_{n=1}^{\infty} \frac{x^{n+1}}{n+1} = \frac{-\ln{(1-x)}-x}{x} $

from the same Taylor series. Combining the results, our answer is then

$ \displaystyle \sum_{n=1}^{\infty} \frac{x^n}{n(n+1)} = 1-\ln{(1-x)}+\frac{\ln{(1-x)}}{x} $.

QED.

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

Comment: Even though the trick at the beginning didn't actually get much to telescope, the idea certainly made it easier to recognize the Taylor series. Algebraic manipulations are nifty to carry around and can be applied in problems wherever you go.

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

Practice Problem: Show that $ \displaystyle \int_0^{\frac{\pi}{2}} \ln{(\tan{x})} = 0 $.

Monday, June 18, 2007

The Smaller The Better. Topic: Calculus.

Problem: Given a complicated function $ f: \mathbb{R}^n \rightarrow \mathbb{R} $, find an approximate local minimum.

Solution: The adjective complicated is only placed so that we assume there is no easy way to solve $ \bigtriangledown f = 0 $ to immediately give the solution. We seek an algorithm that will lead us to a local minimum (hopefully a global minimum as well).

We start at an arbitrary point $ X_0 = (x_1, x_2, \ldots, x_n) $. Consider the following process (for $ k = 0, 1, 2, \ldots $), known as gradient descent:

1. Calculate (approximately) $ \bigtriangledown f(X_k) $.

2. Set $ X_{k+1} = X_k - \gamma_k \bigtriangledown f(X_k) $, where $ \gamma_k $ is a constant that can be determined by a linesearch.

It is well-known that the direction of the gradient is the direction of maximum increase and the direction opposite the gradient is the direction of maximum decrease. Hence this algorithm is based on the idea that we always move in the direction that will decrease $ f $ the most. Sounds pretty good, right? Well, unfortunately gradient descent converges very slowly so it is only really useful for smaller optimization problems. Fortunately, there exist other algorithms but obviously they are more complex, such as the nonlinear conjugate gradient method or Newton's method, the latter of which involves the computation of the inverse of the Hessian matrix, which is a pain.

Wednesday, June 6, 2007

Colorful! Topic: Calculus.

Theorem: (Green's Theorem) Let $ R $ be a simply connected plane region whose boundary is a simple, closed, piecewise smooth curve $ C $ oriented counterclockwise. If $ f(x, y) $ and $ g(x, y) $ are continuous and have continuous first partial derivatives on some open set containing $ R $, then

$ \displaystyle \oint_C f(x, y) dx + g(x, y) dy = \int_R \int \left(\frac{\partial g}{\partial x}-\frac{\partial f}{\partial y}\right) dA $.

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

Problem: Evaluate $ \displaystyle \oint_C x^2y dx + (y+xy^2) dy $, where $ C $ is the boundary of the region enclosed by $ y = x^2 $ and $ x = y^2 $.

Solution: First, verify that this region satisfies all of the requirements for Green's Theorem - indeed, it does. So we may apply the theorem with $ f(x, y) = x^2y $ and $ g(x, y) = y+xy^2 $. From these, we have $ \frac{\partial g}{\partial x} = y^2 $ and $ \frac{\partial f}{\partial y} = x^2 $. Then we obtain

$ \displaystyle \oint_C x^2y dx + (y+xy^2) dy = \int_R \int (y^2-x^2) dA $.
But clearly this integral over the region $ R $ can be represented as $ \displaystyle \int_0^1 \int_{x^2}^{\sqrt{x}} (y^2-x^2) dy dx $, so it remains a matter of calculation to get the answer. First, we evaluate the inner integral to get

$ \displaystyle \int_0^1 \int_{x^2}^{\sqrt{x}} (y^2-x^2) dy dx = \int_0^1 \left[\frac{y^3}{3}-x^2y\right]_{x^2}^{\sqrt{x}} dx = \int_0^1 \left(\frac{x^{3/2}}{3}-x^{5/2}-\frac{x^6}{3}+x^4\right)dx $.

Then finally we have

$ \displaystyle \int_0^1 \left(\frac{x^{3/2}}{3}-x^{5/2}-\frac{x^6}{3}+x^4\right)dx = \left[\frac{2x^{5/2}}{15}-\frac{2x^{7/2}}{7}-\frac{x^7}{21}+\frac{x^5}{5}\right]_0^1 = \frac{2}{15}-\frac{2}{7}-\frac{1}{21}+\frac{1}{5} = 0 $.

QED.

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

Comment: To me, Green's Theorem is a very interesting result. It's not at all obvious that a line integral along the boundary of a region is equivalent to an integral of some partial derivatives in the region itself. A simplified proof of the result can be obtained by proving that

$ \displaystyle \oint_C f(x, y) dx = -\int_R \int \frac{\partial f}{\partial y} dA $ and $ \displaystyle \oint_C g(x, y) dy = \int_R \int \frac{\partial g}{\partial x} dA $.

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

Practice Problem: Let $ R $ be a plane region with area $ A $ whose boundary is a piecewise smooth simple closed curve $ C $. Show that the centroid $ (\overline{x}, \overline{y}) $ of $ R $ is given by

$ \displaystyle \overline{x} = \frac{1}{2A} \oint_C x^2 dy $ and $ \displaystyle \overline{y} = -\frac{1}{2A} \oint_C y^2 dx $.

Monday, June 4, 2007

More Integrals... *whine*. Topic: Calculus.

Definition: (Jacobian) If $ T $ is the transformation from the $ uv $-plane to the $ xy $-plane defined by the equations $ x = x(u, v) $ and $ y = y(u, v) $, then the Jacobian of $ T $ is denoted by $ J(u, v) $ or by $ \partial(x, y)/\partial(u, v) $ and is defined by

$ J(u, v) = \frac{\partial(x, y)}{\partial(u, v)} = \frac{\partial x}{\partial u} \cdot \frac{\partial y}{\partial v} - \frac{\partial y}{\partial u} \cdot \frac{\partial x}{\partial v} $,

i.e. the determinant of the matrix of the partial derivatives (also known as the Jacobian matrix). Naturally, this can be generalized to more variables.

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

Theorem: If the transformation $ x = x(u, v) $, $ y = y(u, v) $ maps the region $ S $ in the $ uv $-plane into the region $ R $ in the $ xy $-plane, and if the Jacobian $ \partial(x, y)/\partial(u, v) $ is nonzero and does not change sign on $ S $, then (with appropriate restrictions on the transformation and the regions) it follows that

$ \displaystyle \int_R \int f(x, y) dA_{xy} = \int_S \int f(x(u, v), y(u, v)) \left|\frac{\partial(x, y)}{\partial(u, v)} \right| dA_{uv} $.

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

Problem: Evaluate $ \displaystyle \int_R \int e^{(y-x)/(y+x)} dA $, where $ R $ is the region in the first quadrant enclosed by the trapezoid with vertices $ (0, 1); (1, 0); (0, 4); (4, 0) $.

Solution: The bounding lines can be written as $ x = 0 $, $ y = 0 $, $ y = -x+1 $, and $ y = -x+4 $. Now consider the transformation $ u = y+x $ and $ v = y-x $. In the $ uv $-plane, the bounding lines of the new region $ S $ can now be written as $ u = 1 $, $ u = 4 $, $ v = u $, and $ v = -u $.

We can write $ x $ and $ y $ as functions of $ u $ and $ v $: simply $ x = \frac{u-v}{2} $ and $ y = \frac{u+v}{2} $. So the Jacobian $ \displaystyle \frac{\partial(x, y)}{\partial(u, v)} = \frac{\partial x}{\partial u} \cdot \frac{\partial y}{\partial v} - \frac{\partial y}{\partial u} \cdot \frac{\partial x}{\partial v} = \frac{1}{2} \cdot \frac{1}{2} - \frac{1}{2} \cdot \left(-\frac{1}{2} \right) = \frac{1}{2} $.

Then our original integral becomes $ \displaystyle \int_R \int e^{(y-x)/(y+x)} dA = \frac{1}{2} \int_S \int e^{v/u} dA $. And this is equivalent to

$ \displaystyle \frac{1}{2} \int_S \int e^{v/u} dA = \frac{1}{2} \int_1^4 \int_{-u}^u e^{v/u} dv du = \frac{1}{2} \int_1^4 \big[ u e^{v/u} \big]_{v=-u}^u du = \frac{1}{2} \int_1^4 u\left(e-\frac{1}{e}\right) du = \frac{15}{4}\left(e-\frac{1}{e}\right) $.

QED.

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

Comment: Note that the above theorem is probably very important in multivariable calculus, as it is the equivalent to $ u $-substitution in one variable, which we all know is the ultimate integration technique. It functions in the same way, giving you a lot more flexibility on the function you are integrating and the region you are integrating on.

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

Practice Problem: Evaluate $ \displaystyle \int_R \int (x^2-y^2) dA $, where $ R $ is the rectangular region enclosed by the lines $ y = -x $, $ y = 1-x $, $ y = x $, $ y = x+2 $.

Monday, May 28, 2007

One By One, We're Making It Fun. Topic: Calculus/S&S.

Theorem: (Stolz-Cesaro) Let $ \{a_n\} $ and $ \{b_n\} $ be sequences of real numbers such that $ \{b_n\} $ is positive, strictly increasing, and unbounded. If the limit

$ \displaystyle \lim_{n \rightarrow \infty} \frac{a_{n+1}-a_n}{b_{n+1}-b_n} = L $

exists, then the following limit also exists and we have

$ \displaystyle \lim_{n \rightarrow \infty} \frac{a_n}{b_n} = L $.

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

Theorem: (Summation by Parts) If $ \{f_k\} $ and $ \{g_k\} $ are two sequences, then

$ \displaystyle \sum_{k=m}^n f_k(g_{k+1}-g_k) = [f_{n+1}g_{n+1}-f_mg_m]-\sum_{k=m}^n g_{k+1}(f_{k+1}-f_k) $.

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

Problem: Let $ \{a_n\} $ be a sequence of real numbers such that $ \displaystyle \sum_{k=0}^{\infty} a_k $ converges. Show that $ \displaystyle \lim_{n \rightarrow \infty} \frac{1}{n+1} \sum_{k=0}^n k \cdot a_k = 0 $.

Solution: Define the sequence $ \{b_n\} $ by $ \displaystyle b_n = \sum_{k=0}^n a_k $ and let $ \displaystyle \lim_{n \rightarrow \infty} b_n = L $. Then, by summation by parts with $ \{f_n\} = \{n\} $ and $ \{g_n\} = \{b_n\} $, we have

$ \displaystyle \sum_{k=0}^n k \cdot a_k = \sum_{k=0}^n k \cdot (b_{k+1}-b_k) = (n+1)b_{n+1}-\sum_{k=0}^n b_{k+1} $.

The summation we wish to take the limit of is then

$ \displaystyle \frac{1}{n+1} \sum_{k=0}^n k \cdot a_k = b_{n+1}-\frac{1}{n+1} \sum_{k=0}^n b_{k+1} $.

But since, by Stolz-Cesaro,

$ \displaystyle \lim_{n \rightarrow \infty} \frac{1}{n+1} \sum_{k=0}^n b_{k+1} = \lim_{n \rightarrow \infty} b_{n+1} = L $,

we obtain

$ \displaystyle \lim_{n \rightarrow \infty} \frac{1}{n+1} \sum_{k=0}^n k \cdot a_k = \lim_{n \rightarrow \infty} \left(b_n-\frac{1}{n+1} \sum_{k=0}^n b_{k+1}\right) = L-L = 0 $.

QED.

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

Comment: Summation by parts is a very useful technique to change sums around so that they are easier to evaluate. If you hadn't noticed, it is the discrete analogue of integration by parts and is in fact very similar. Stolz-Cesaro is powerful as well and seems like a discrete analogue to L'Hopital (but I'm not sure about this one). Applying well-known calculus ideas to discrete things can often turn into neat results.

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

Practice Problem: If $ \{a_n\} $ is a decreasing sequence such that $ \displaystyle \lim_{n \rightarrow \infty} a_n = 0 $, show that

$ \displaystyle \sum_{k=1}^{\infty} a_k \cdot \sin{(kx)} $

converges for all $ x $.

Saturday, May 12, 2007

Bigger Means Better. Topic: Algebra/Inequalities/Sets. Level: Olympiad.

Definition: A set $ S $ is said to be convex if, for any $ X, Y \in S $ and $ \lambda \in [0,1] $, we have $ \lambda X+(1-\lambda)Y \in S $.

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

Definition: Let $ f: D \rightarrow \mathbb{R} $ be a real-valued function defined on a convex set $ D $. We say that $ f $ is convex if, for all $ X, Y \in D $ and $ \lambda \in [0, 1] $, we have

$ \lambda f(X) + (1-\lambda) f(Y) \ge f(\lambda X+(1-\lambda)Y) $.

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

Theorem: (Jensen's Inequality) Let $ f $ be a real-valued, convex function defined on a convex set $ D $. Given $ x_1, x_2, \ldots, x_n \in D $ and nonnegative reals $ w_1, w_2, \ldots, w_n $ such that $ w_1+w_2+\cdots+w_n = 1 $, we have

$ w_1f(x_1)+w_2f(x_2)+\cdots+w_nf(x_n) \ge f(w_1x_1+w_2x_2+\cdots+w_nx_n) $

or, more concisely,

$ \displaystyle \sum_{i=1}^n w_if(x_i) \ge f\left(\sum_{i=1}^n w_ix_i\right) $.

Proof: We proceed by induction on $ n $.

Base Case - $ n = 1 $, we have $ f(x_1) \ge f(x_1) $ which is trivially true. $ n = 2 $, we have $ \lambda_1 f(x_1)+\lambda_2 f(x_2) \ge f(\lambda_1 x_1+\lambda_2 x_2) $ with $ \lambda_1+\lambda_2 = 1$ which is true by the definition of convexity.

Induction Step - Suppose $ \displaystyle \sum_{i=1}^k w_if(x_i) \ge f\left(\sum_{i=1}^k w_ix_i\right) $. We wish to show

$ \displaystyle \sum_{i=1}^{k+1} u_if(x_i) \ge f\left(\sum_{i=1}^{k+1} u_ix_i\right) $

for nonnegative reals $ u_1, u_2, \ldots, u_{k+1} $ that sum to $ 1 $. Well,

$ \displaystyle f\left(\sum_{i=1}^{k+1} u_ix_i\right) \le u_{k+1}f(x_{k+1})+(1-u_{k+1})f\left(\frac{1}{1-u_{k+1}} \sum_{i=1}^k u_ix_i\right) $

by the definition of convexity. But since $ \displaystyle \frac{1}{1-u_{k+1}} \sum_{i=1}^k u_i = \sum_{i=1}^k \frac{u_i}{1-u_{k+1}} = 1 $, by our inductive hypothesis (the $ k $ term case) we must have

$ \displaystyle f\left(\frac{1}{1-u_{k+1}} \sum_{i=1}^k u_ix_i\right) \le \sum_{i=1}^k \frac{u_i}{1-u_{k+1}} f(x_i) $.

Combining this into the above inequality, we obtain

$ \displaystyle f\left(\sum_{i=1}^{k+1} u_ix_i\right) \le u_{k+1}f(x_{k+1})+(1-u_{k+1})\sum_{i=1}^k \frac{u_i}{1-u_{k+1}} f(x_i) = \sum_{i=1}^{k+1} u_if(x_i) $

as desired, completing the induction. QED.

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

Definition: The convex hull of a set $ S $ is defined to be the smallest convex set containing $ S $. It is the set of all points that can be written as $ \displaystyle \sum_{i=1}^n a_ix_i $, where $ n $ is a natural number, $ a_1, a_2, \ldots, a_n $ are nonnegative reals that sum to $ 1 $, and $ x_1, x_2, \ldots, x_n \in S $.

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

Definition: A vertex of a set $ D $ is a point $ v \in D $ such that for all $ x \in D $ not equal to $ v $ and $ \lambda > 1 $ we have $ \lambda v+(1-\lambda)x \not\in D $.

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

Theorem: Let $ V_D = \{v_1, v_2, \ldots, v_k\} $ be the set of vertices of a compact convex set $ D $. The convex hull of $ V_D $ is $ D $.

Example: The set of vertices of a convex polygon is, in fact, its vertices as traditionally defined in geometry. Any point inside the polygon can be written as a convex combination of its vertices.

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

Theorem: If $ f $ is a real-valued, convex function defined on a compact convex set $ D $, then $ \displaystyle \max_{x \in D} f(x) = \max_{x \in V_D} f(x) $, where $ V_D $ is the set of vertices of $ D $.

Proof: We will show that $ \displaystyle f(x) \le \max_{x \in V_D} f(x) $ for all $ x \in D $.

Let $ \displaystyle x = \sum_{i=1}^k \lambda_i v_i $ where $ \lambda_1, \lambda_2, \ldots, \lambda_k $ are nonnegative reals that sum to $ 1 $ and $ V_D = \{v_1, v_2, \ldots, v_k\} $. This is possible by the preceding theorem. Then by Jensen's Inequality we get

$ \displaystyle \sum_{i=1}^k \lambda_i f(v_i) \ge f\left(\sum_{i=1}^k \lambda_i v_i\right) = f(x) $.

And since $ \displaystyle \max_{x \in V_D} f(x) \ge \sum_{i=1}^k \lambda_i f(v_i) $, we have $ \displaystyle \max_{x \in V_D} f(x) \ge f(x) $ for all $ x \in D $. Furthermore, since $ V_D $ is a subset of $ D $, we know that this maximum is attained, thus

$ \displaystyle \max_{x \in D} f(x) = \max_{x \in V_D} f(x) $

as desired. QED.

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

Comment: This is a very useful result, as it allows us to limit our search for the maximum of a function to its set of vertices, which is usually a considerably smaller set, though it may still be infinite (think sphere). In any case, this works well for constrained optimization problems in which the domain is limited to a polygon, the easiest application of this theorem.

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

Practice Problem: Let $ x $ and $ y $ be real numbers satisfying $ |2x-y| \le 3 $ and $ |y-3x| \le 1 $. Find the maximum value of $ f(x, y) = (x-y)^2 $.

Tuesday, May 8, 2007

A Square of Divisors. Topic: Number Theory. Level: AIME/Olympiad.

Problem: (1999 Canada - #3) Determine all positive integers $ n > 1 $ with the property that $n = (d(n))^2$. Here $d(n)$ denotes the number of positive divisors of $n$.

Solution: So, testing some small numbers yields $ n = 9 $ as a solution. We claim that this is the only such solution.

Clearly, since $ n $ is a square, we can use a variant of the usual prime decomposition and say that $ n = p_1^{2e_1} p_2^{2e_2} \cdots p_k^{2e_k} $.

Furthermore, again since $ n $ is a square, we know

$ d(n) = (2e_1+1)(2e_2+1) \cdots (2e_k+1) $

is odd, so $ n = (d(n))^2 $ must be odd as well, i.e. $ 2 $ is not one of the $ p_i $. Then we use the equation given to us to get

$ p_1^{2e_1} p_2^{2e_2} \cdots p_k^{2e_k} = (2e_1+1)^2(2e_2+1)^2 \cdots (2e_k+1)^2 $

$ p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k} = (2e_1+1)(2e_2+1) \cdots (2e_k+1) $.

Note, however, that by Bernoulli's Inequality (overkill, I know) we have for $ i = 1, 2, \ldots, k $

$ (1+(p_i-1))^{e_i} \ge 1+(p_i-1)e_i \ge 2e_i+1 $

with equality iff $ p_i = 3 $ and $ e_i = 1 $. So

$ p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k} \ge (2e_1+1)(2e_2+1) \cdots (2e_k+1) $.

Since we want equality, we must have $ p_i = 3 $ and $ e_i = 1 $ for all $ i $. But since the primes are supposed to be distinct we can have exactly one prime so that $ n = 3^2 = 9 $ is the only solution. QED.

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

Comment: Another one of those problems that you kind of look at the result and you're like huh, that's interesting. But anyway, just throwing in some weak inequalities led to a pretty straightforward solution. As long as you know how to find the number of divisors of a positive integer it isn't too much of a stretch to figure the rest out, though it make take some time to get in the right direction since the problem is quite open-ended.

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

Practice Problem: (1999 Canada - #4) Suppose $a_1,a_2,\cdots,a_8$ are eight distinct integers from $\{1,2,\ldots,16,17\}$. Show that there is an integer $k > 0$ such that the equation $a_i - a_j = k$ has at least three different solutions. Also, find a specific set of $7$ distinct integers from $\{1,2,\ldots,16,17\}$ such that the equation $a_i - a_j = k$ does not have three distinct solutions for any $k > 0$.

Saturday, May 5, 2007

Ready For AP Calculus? Topic: Calculus/S&S. Level: AIME/Olympiad.

Problem: Evaluate $ \displaystyle \sum_{n=1}^{\infty} \frac{1}{n^2 \cdot 2^n} $.

Solution: Let $ \displaystyle f(x) = \sum_{n=1}^{\infty} \frac{x^n}{n^2} $. Then $ \displaystyle f^{\prime}(x) = \sum_{n=1}^{\infty} \frac{x^{n-1}}{n} = -\frac{\ln{(1-x)}}{x} $, a well-known Taylor series. So we want to integrate this:

$ \displaystyle \int \frac{\ln{(1-x)}}{x}dx = \ln{x} \ln{(1-x)}-\int \frac{\ln{x}}{x-1}dx $

by parts using $ u = \ln{(1-x)} $ and $ dv = dx/x $. Substituting $ t = 1-x $ in the last integral, we have

$ \displaystyle \int \frac{\ln{(1-x)}}{x}dx = \ln{x} \ln{(1-x)}-\int \frac{\ln{(1-t)}}{t}dt $.

So $ -f(x) = \ln{x} \ln{(1-x)}+f(t)+C = \ln{x} \ln{(1-x)}+f(1-x)+C $. Thus

$ f(x)+f(1-x) = C-\ln{x} \ln{(1-x)} $

for some constant $ C $. Using our knowledge that $ f(0) = 0 $, $ \displaystyle f(1) = \frac{\pi^2}{6} $, and $ \displaystyle \lim_{x \rightarrow 1} \ln{x} \ln{(1-x)}= 0 $ by L'Hopital twice, we see that

$ f(0)+f(1) = C \Rightarrow C = \frac{\pi^2}{6} $

Then setting $ x = \frac{1}{2} $ we obtain $ \displaystyle 2f\left(\frac{1}{2}\right) = \frac{\pi^2}{6}-\ln{\frac{1}{2}} \ln{\frac{1}{2}} $ and $ \displaystyle \sum_{n=1}^{\infty} \frac{1}{n^2 \cdot 2^n} = f\left(\frac{1}{2}\right) = \frac{\pi^2}{12}-\frac{\ln^2{(2)}}{2} $. QED.

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

Comment: This was a pretty tough problem that required you to compound a lot of calculus knowledge all into a single problem - series, integration by parts, limits. Recognizing all the steps was the first part; following through with the right computations was another. Still, there weren't really any super clever tricks, mostly just standard substitutions and approaches applied in a somewhat non-standard way. Makes for a very nice problem.

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

Practice Problem #1: Show that $ \displaystyle \lim_{x \rightarrow 1} \ln{x} \ln{(1-x)} = 0 $.

Practice Problem #2: Evaluate $ \displaystyle \sum_{n=1}^{\infty} \frac{x^n}{n} $. Can you also find $ \displaystyle \sum_{n=1}^{\infty} \frac{x^n}{n^3} $?

Saturday, April 28, 2007

Just A "Natural" Thing. Topic: Algebra. Level: AIME/Olympiad.

Problem: Factor $ 7^{6(2k-1)}-7^{5(2k-1)}+7^{4(2k-1)}-7^{3(2k-1)}+7^{2(2k-1)}-7^{2k-1}+1 $.

Solution: Consider the polynomial $ x^7+1 $. We have

$ x^7+1 = (x+1)(x^6-x^5+x^4-x^3+x^2-1) $,

so we want to factor the second term when $ x = 7^{2k-1} $. Call it $ P(x) $ so that $ P(x) = \frac{x^7+1}{x+1} $. Consider the relation

$ (x+1)^7-(x^7+1) = 7x^6+21x^5+35x^4+35x^3+21x^2+7x $.

Since $ -1 $ is a root of the LHS, we factor it out of the RHS as well to get

$ (x+1)^7-(x^7+1) = 7x(x+1)(x^4+2x^3+3x^2+2x+1) = 7x(x+1)(x^2+x+1)^2 $.

Dividing through by $ x+1 $ and rearranging, we obtain the nice expression

$ P(x) = (x+1)^6-7x(x^2+x+1)^2 $.

Letting $ x = 7^{2k-1} $, this becomes

$ P(7^{2k-1}) = (7^{3(2k-1)}+3 \cdot 7^{2(2k-1)}+3 \cdot 7^{2k-1}+1)^2-7^{2k}(7^{2(2k-1)}+7^{2k-1}+1)^2 $

which is conveniently enough a difference of two squares. And we'll leave it as this because the factors are not particularly nice or anything. QED.

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

Comment: This "natural" factorization was basically the one crucial step to solving the USAMO #5 this year and most people did not see it, unsurprisingly. Taking the difference $ (x+1)^7-(x^7+1) $ was the trickiest/cleverest part, and there were definitely a limited number of approaches to this factorization. Oh well, at least it seems sort of cool after you know about it.

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

Practice Problem: (2007 USAMO - #5) Prove that for every nonnegative integer n, the number $7^{7^{n}}+1$ is the product of at least $2n+3$ (not necessarily distinct) primes.

Monday, April 23, 2007

Wednesday, April 18, 2007

Something To Think About. Topic: Probability. Level: AMC/AIME.

Problem: A coin is repeatedly flipped. What is the expected number of flips to get two heads in a row? $ n $ heads in a row?

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

I will be out of town for the next four days, so have fun with the problem!

Sunday, April 15, 2007

Sense Of Poise And Rationality. Topic: Algebra. Level: AIME/Olympiad.

Problem: (1993 Canada National Olympiad - #2) Show that $ x $ is rational if and only if three distinct terms that form a geometric progression can be chosen from the sequence $ x, x+1, x+2, x+3, \ldots $.

Solution: We will prove the "if" statement first, i.e. $ x $ is rational implies we can find the geometric progression. Let $ x = \frac{p}{q} $. The terms of the sequence are then

$ \frac{p}{q} $, $ \frac{p+q}{q} $, $ \frac{p+2q}{q} $, $ \frac{p+3q}{q}, \ldots $.

We simply choose the terms

$ \frac{p}{q} $, $ \frac{p+pq}{q} $, $ \frac{p+(2p+pq)q}{q} $ which are the same as $ \frac{p}{q} $, $ \frac{p(1+q)}{q} $, $ \frac{p(1+q)^2}{q} $,

clearly a geometric progression.

Now for the other direction, assume $ x+a, x+b, x+c $ are a geometric progression with $ a < b < c $ positive integers. Then

$ \frac{x+a}{x+b} = \frac{x+b}{x+c} \Rightarrow x^2+(a+c)x+ac = x^2+2bx+b^2 \Rightarrow (a+c)x+ac = 2bx+b^2 $.

Solving for $ x $ yields $ x = \frac{b^2-ac}{a+c-2b} $ which is clearly rational, as desired. QED.

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

Comment: An interesting "definition" of a rational number, pretty neat in fact. Though it may not seem so at first, the "if" direction was actually considerably harder than the "only if" direction because the approach was not as straightforward. The "only if" proof required simple algebra, while the "if" proof needed a little creative picking and choosing. Another approach for the "if" direction is to set $ x = \frac{p}{q} $ and try to find corresponding $ a, b, c $ but that makes it a little more difficult than necessary.

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

Practice Problem: (1993 Canada National Olympiad - #3) In triangle $ ABC $, medians to the sides $ \overline{AB} $ and $ \overline{AC} $ are perpendicular. Show that $ \cot{B}+\cot{C} \ge \frac{2}{3} $.

Thursday, April 12, 2007

Fishy Triangular Number. Topic: Inequalities. Level: AIME.

Problem: (2001 Poland Finals - #1) Prove the following inequality:

$ x_1+2x_2+3x_3+\cdots+nx_n \le \frac{n(n-1)}{2}+x_1+x_2^2+x_3^3+\cdots+x_n^n $

where $ x_i $ are positive reals.

Solution: Like the title says, that triangular number looks really fishy... let's write it as $ 1+2+\cdots+(n-1) $ and pair up the terms on the RHS.

$ \frac{n(n-1)}{2}+x_1+x_2^2+x_3^3+\cdots+x_n^n = x_1+(x_2^2+1)+(x_3^3+2)+\cdots+(x_n^n+n-1) $.

We claim that $ x_i^i+i-1 \ge ix_i $ for $ i = 1, 2, \ldots, n $. We'll use our good friend AM-GM to show this; in fact, it is quite simple.

$ \frac{x_i+1+1+\cdots+1 \text{(i-1 times)}}{i} \ge \sqrt[i]{x_i^i} = x_i $ so $ x_i^i+i-1 \ge ix_i $

as desired. Sum them up to get our inequality. QED.

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

Comment: Just a clever little application of AM-GM; apparantly not a strong inequality at all, and the only equality case is $ x_i = 1 $ for all $ i $. Nevertheless, slightly on the tricky side which makes it sufficiently satisfying to solve.

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

Practice Problem: (2006 Poland Finals - #1) Solve in reals:

$ a^2 = b^3+c^3 $
$ b^2 = c^3+d^3 $
$ c^2 = d^3+e^3 $
$ d^2 = e^3+a^3 $
$ e^2 = a^3+b^3 $.

Tuesday, April 10, 2007

2007 Bellevue BATH.

The 2007 Bellevue BATH will be taking place on May 19, 2007. It will be the best competition of the year! :) The information sheet can be found here. Sign up today!

Monday, April 9, 2007

Get A Tan. Topic: Trigonometry. Level: AMC.

Problem: (2007 MAO State - Gemini) Let $ x $ be in degrees and $ 0^{\circ} < x < 45^{\circ} $. Solve for $ x $: $ \tan{(4x)} = \frac{\cos{x}-\sin{x}}{\cos{x}+\sin{x}} $.

Solution: Here's a nice tangent identity that is not very well-known, but rather cool. Start with the regular tangent angle addition identity,

$ \tan{(x+y)} = \frac{\tan{x}+\tan{y}}{1-\tan{x} \cdot \tan{y}} $.

Letting $ x = 45^{\circ} $ and $ y = -\theta $, we obtain

$ \tan{(45^{\circ}-\theta)} = \frac{1-\tan{\theta}}{1+\tan{\theta}} = \frac{\cos{\theta}-\sin{\theta}}{\cos{\theta}+\sin{\theta}} $.

Well, look at that. It's the same expression as the RHS of the equation we want to solve. Substituting accordingly, it remains to solve

$ \tan{(4x)} = \tan{(45^{\circ}-x)} \Rightarrow 4x = 45^{\circ}-x \Rightarrow x = 9^{\circ} $.

QED.

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

Comment: This identity is a nice one to keep around because it can turn up unexpectedly. Especially when you see that exact form and you're like "whoa this is such a nice form there must be an identity for it." So there.

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

Practice Problem: (2007 MAO State - Gemini) One hundred positive integers, not necessarily distinct, have a sum of $ 331 $. What is the largest possible product these numbers can attain?

Sunday, April 1, 2007

Sumsine. Topic: Trigonometry/Geometry. Level: AMC.

Problem: (2007 MAO State - Gemini) Find the sum of the sines of the angles of a triangle whose perimeter is five times as large as its circumradius.

Solution: At first, this problem seems very strange because we do not expect a nice relationship between the perimeter and the circumradius to offer much, but take another look. Sines, circumradius... Law of Sines! In fact, we get

$ \frac{a}{\sin{A}} = \frac{b}{\sin{B}} = \frac{c}{\sin{C}} = 2R $

so we can rewrite $ \sin{A}+\sin{B}+\sin{C} $ as

$ \sin{A}+\sin{B}+\sin{C} = \frac{a}{2R}+\frac{b}{2R}+\frac{c}{2R} = \frac{a+b+c}{2R} = \frac{5R}{2R} = \frac{5}{2} $.

QED.

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

Comment: Admittedly, MAO does not exactly have a plethora of cool problems, but this one was not bad. It wasn't too difficult, but it required some clever use of well-known identities to pull it off. Given that half of the problems were computationally intensive (think AIME I but worse), this was a nice relief in the middle of the contest.

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

Practice Problem: (2007 MAO State - Gemini) The zeros of $ f(x) = 7x^3-4x^2+K $ form an arithmetic sequence. Let $ K = \frac{m}{n} $, where $ m $ and $ n $ are relatively prime positive integers. Find the value of $ m+n $.

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.

Tuesday, February 27, 2007

Recurrences Are Cool. Topic: Probability/S&S. Level: AIME.

Problem: Let $ p_k $ be the probability of choosing a positive integer $ n $ from the interval $ [2^{k-1}, 2^k-1] $ such that the binary representation of $ n $ does not contain three consecutive $ 1 $'s. Evaluate the infinite summation $ p_1+p_2+\cdots $.

Solution: First, let $ S_k $ be the number of positive integers $ n $ in the interval $ [2^{k-1}, 2^k-1] $ that do not contain three consecutive $ 1 $'s in their binary representations - note that it is equivalent to the number of binary strings of length $ k $ starting with a $ 1 $ that satisfy that property. By testing, we have $ S_1 = 1 $, $ S_2 = 2 $, $ S_3 = 3 $, $ S_4 = 6 $, $ S_5 = 11 $, $ S_6 = 20 $. You can construct a certain type of table to make these calculations easier. We notice that the recurrence $ S_{k+3} = S_{k+2}+S_{k+1}+S_k $ seems to hold, so we want to try and prove this.

We categorize the strings of length $ k+3 $ based on the last occurence of $ 0 $. It must either be in the last, second to last, or third to last spots. If it is in the last spot, the string is $ \text{blah}0 $ where $ \text{blah} $ has length $ k+2 $ so there are $ S_{k+2} $ of those. Similarly, the other possibilities are $ \text{blah}01 $ or $ \text{blah}001 $, where the $ \text{blah} $'s have length $ k+1 $ and $ k $, respectively, giving the recurrence. Now it remains to sum it.

We want to evaluate $ \displaystyle \sum_{k=1}^{\infty} p_k = \sum_{k=1}^{\infty} \frac{S_k}{2^{k-1}} $ since there are $ 2^{k-1} $ binary strings of length $ k $ that begin with $ 1 $.

Luckily, we know a cool way to evaluate recurrences over a geometric sequence. Let $ \displaystyle S = \sum_{k=1}^{\infty} \frac{S_k}{2^{k-1}} $. Then

$ \displaystyle 2S = 2S_1+\sum_{k=1}^{\infty} \frac{S_{k+1}}{2^{k-1}} $

$ \displaystyle 4S = 4S_1+2S_2+\sum_{k=1}^{\infty} \frac{S_{k+2}}{2^{k-1}} $

$ \displaystyle 8S = 8S_1+4S_2+2S_3+\sum_{k=1}^{\infty} \frac{S_{k+3}}{2^{k-1}} $.

Notice, now that if we take $ S = 8S-4S-2S-S $ a lot of terms cancel due to the recurrence. In fact, all of the summations do! So

$ \displaystyle S = (8S_1+4S_2+2S_3)-(4S_1+2S_2)-2S_1+ \sum_{k=1}^{\infty} \frac{S_{k+3}-S_{k+2}-S_{k+1}-S_k}{2^{k-1}} $

$ S = 2S_1+2S_2+2S_3 = 12 $.

QED.

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

Comment: Both parts of this problem are pretty classical. The first, finding a recurrence for a string satisfying a certain property, and the second, evaluating an infinite summation of the terms of a sequence divided by a geometric series. These two techniques are very useful, however, in approaching many problems. It would not be fun to solve a problem and get to the last step only to find that you do not know how to evaluate the summation to get the final answer.

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

Practice Problem: Evaluate $ \displaystyle \sum_{k=1}^{\infty} \frac{F_k}{n^k} $, where $ n > 1 $ is a positive integer and $ F_k $ is the Fibonacci sequence (i.e. $ F_0 = F_1 = 1 $ and $ F_{k+1} = F_k+F_{k-1} $ for all positive integers $ k $).

Friday, February 23, 2007

2007 Mock AIME 6.

The 2007 Mock AIME 6 is underway! The test can be found here and more information can be found at the AoPS Forum.

Thursday, February 22, 2007

Pythagorean x3. Topic: Geometry/NT. Level: AMC.

Problem: (2007 AMC12B - #23) How many non-congruent right triangles with positive integer leg lengths have areas that are numerically equal to $ 3 $ times their perimeters?

Solution: Well, basically, you should know the Pythagorean triple generating formula, i.e. $ a = k(u^2-v^2) $, $ b = 2kuv $, $ c = k(u^2+v^2) $. Substitute accordingly and we have to solve the diophantine equation

$ \frac{1}{2} \cdot k(u^2-v^2) \cdot 2kuv = 3 \cdot (k(u^2-v^2)+2kuv+k(u^2+v^2)) $

which conveniently simplifies to

$ kv(u-v) = 6 $.

Obviously then $ k = 1, 2, 3, 6 $ so look at these cases:

$ k = 1 $: We can take $ v = 1, 2, 3, 6 $ to get the triples $ (14, 48, 50); (20, 21, 29); (16, 30, 34); (13, 84, 85) $.

$ k = 2 $: We can take $ v = 1, 3 $ to get the triples $ (16, 30, 34); (14, 48, 50) $ both of which are already counted.

$ k = 3 $: We can take $ v = 1, 2 $ to get the triples $ (18, 24, 30); (15, 24, 39) $.

$ k = 6 $: We can take $ v = 1 $ to get the triple $ (18, 24, 30) $, which is already counted.

So we have $ 4+2 = 6 $ triangles. QED.

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

Comment: Not too hard if you knew the generating formula for Pythagorean triples. It was a little annoying having to check for repeated triples, but at least there weren't that many.

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

Practice Problem: (2007 AMC 12B - #24) How many pairs of positive integers $ (a, b) $ are there such that $ \text{gcd}(a, b) = 1 $ and

$ \frac{a}{b}+\frac{14b}{9a} $

is an integer?

Sunday, February 18, 2007

Mu Alpha Practice Tests.

There are so many, so I'm not going to bother putting links to them all. 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:

ABTest
Algebra34
AlphaIndividual
Answers (for all tests)
BCTest
Cipher2003_16ques
Cipher2003Alpha17
Cipher2003Mu15
Cipher2003Theta17
CirclesAreaVolume
Gemini
GeometryClass
LimDeriv2003
MuIndividual
MuS&S
NumberTheory
ProbAlpha
ProbilityTheta
S&SAlpha
TheNumber_e
ThetaIndividual
ThetaLogsExps
TrigClassTest

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

Currently...

Writing a Mock AIME. Stay tuned!

Friday, February 16, 2007

Common Law. Topic: Geometry/Trigonometry. Level: AIME.

Problem: (2003 AIME1 - #12) In convex quadrilateral $ ABCD $, $ \angle A = \angle C $, $ AB = CD = 180 $, and $ AD \neq BC $. The perimeter of $ ABCD $ is $ 640 $. Find $ \lfloor 1000 \cos{\angle A} \rfloor $.

Solution: Well, let's say that $ BC = x $ and $ AD = y $. We know $ x+y+180+180 = 640 \Rightarrow x+y = 280 $. Consider the two triangles $ ABD $ and $ CBD $. Using the Law of Cosines on $ \angle A $ and $ \angle C $, which we know are equal (let them both equal $ \theta $), we have

$ BD^2 = AB^2+AD^2-2 \cdot AB \cdot AD \cos{\theta} $

$ BD^2 = CB^2+CD^2-2 \cdot CB \cdot CD \cos{\theta} $.

Substituting $ AB = CD = 180 $ and $ BC = x $, $ AD = y $, it becomes

$ BD^2 = 180^2+y^2-360y \cos{\theta} $

$ BD^2 = x^2+180^2-360x \cos{\theta} $.

Equating the two,

$ 180^2+y^2-360y \cos{\theta} = x^2+180^2-360x \cos{\theta} \Rightarrow x^2-y^2 = 360(x-y)\cos{\theta} $.

Recall that $ x+y = 280 $, so

$ x^2-y^2 = (x+y)(x-y) = 280(x-y) = 360(x-y)\cos{\theta} $.

Finally, since $ x \neq y \Rightarrow x-y \neq 0 $, we divide through to get

$ \cos{\theta} = \frac{280}{360} = \frac{7}{9} \Rightarrow \lfloor 1000 \cos{\theta} \rfloor = 777 $.

QED.

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

Comment: This is a demonstration of the power of something as simple as the Law of Cosines. Never underestimate what a little experimentation can do for you on the AIME; play around with equations. If at first you do not see an approach, look at the question itself for hints. Since you have to find the cosine, it should immediately trigger the Law of Cosines because it relates sides and angles. Then apply the Law of Cosines to the important angles (the ones you know something about), in this case $ \angle A $ and $ \angle C $, from which the result falls quite nicely.

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

Practice Problem: (2003 AIMEI - #6) The sum of the areas of all triangles whose vertices are also vertices of a $ 1\times 1 \times 1 $ cube is $m+\sqrt{n}+\sqrt{p}$, where $m$, $n$, and $p$ are integers. Find $m+n+p$.

Tuesday, February 13, 2007

Lots of Fn. Topic: Algebra/S&S. Level: AIME.

Problem: Let $ F_n $ be the Fibonnaci sequence that begins with $ F_1 = 1 $, $ F_2 = 1 $, etc. Show that

$ F_{2n} = F_{n+1}^2-F_{n-1}^2 $.

Solution: We will use induction (as expected). First, rewrite the equality as

$ F_{2n} = F_{n+1}^2-(F_{n+1}-F_n)^2 = F_n(2F_{n+1}-F_n) $.

The base case is easy, since we have $ F_4 = 3 = 2^2-1^2 = F_3^2-F_1^2 $. Now we will show that it is true for $ n = k+1 $ assuming it is true for $ n \le k $. We have

$ F_{2k+2} = F_{2k+1}+F_{2k} = 3F_{2k}-F_{2k-2} $.

Now we apply the inductive hypothesis to get

$ F_{2k+2} = 3F_k(2F_{k+1}-F_k)-F_{k-1}(2F_k-F_{k-1}) $,

which we can simplify with the substitution $ F_{k-1} = F_{k+1}-F_k $ to get

$ F_{2k+2} = 3F_k(2F_{k+1}-F_k)-(F_{k+1}-F_k)(3F_k-F_{k+1}) = 2F_kF_{k+1}+F_{k+1}^2 $

and finally from $ F_k = F_{k+2}-F_{k+1} $ we get

$ F_{2k+2} = F_{k+1}(2F_{k+2}-F_k) $

as desired. QED.

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

Comment: Not a particularly insightful problem, but admittedly a pretty neat identity. Standard substitution/induction method, which you should all be familiar with right now since I use it all the time here. Maybe there's some cool combinatorics argument that I can't see...

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

Practice Problem: Show $ F_{2n} = F_n^2+F_{n-1}^2 $ through a combinatorics argument, where $ F_0 = 1 $, $ F_1 = 1 $, etc. is the Fibonnaci sequence.

[Hint: $ F_n $ is the number of ways to tile a $ 2 \times n $ board with $ 1 \times 2 $ tiles.]

Sunday, February 11, 2007

Return Of The Triangle. Topic: Geometry/Inequalities/Trigonometry. Level: AIME.

Problem: (1961 IMO - #2) Let $ a, b, c $ be the sides of a triangle, and $ T $ its area. Prove:

$ a^2+b^2+c^2 \ge 4T\sqrt{3} $.

In what case does equality hold?

Solution: We begin with the trivial inequality, $ (a-b)^2 \ge 0 $, which has equality at $ a = b $. Rearrange to get

$ a^2+b^2 \ge 2ab $.

Let $ \theta $ be the angle between the sides with lengths $ a, b $. Since $ 2 \ge \cos{\theta}+\sqrt{3}\sin{\theta} $ (can be proved by combining RHS) with equality at $ \theta = \frac{\pi}{3} $, we know

$ a^2+b^2 \ge ab(\cos{\theta}+\sqrt{3}\sin{\theta}) $

$ 2(a^2+b^2) \ge 2ab(\cos{\theta}+\sqrt{3}\sin{\theta}) $

$ a^2+b^2+(a^2+b^2-2ab\cos{\theta}) \ge 2\sqrt{3} \cdot ab\sin{\theta} $.

Recalling the Law of Cosines, we know $ c^2 = a^2+b^2-2ab\cos{\theta} $. Also, $ T = \frac{1}{2}ab\sin{\theta} $, so substituting we obtain

$ a^2+b^2+c^2 \ge 4T\sqrt{3} $

as desired. Equality holds when $ a = b $ and $ \theta = \frac{\pi}{3} $, which means the triangle must be equilateral. QED.

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

Comment: There are lots of ways to prove this, but this is one of the more elementary ones, requiring only basic knowledge of inequalities and trigonometry. Which is always good because I don't know any geometry. We see that this inequality is in general pretty weak, with equality only when the triangle is equilateral - there is a stronger version that states

$ a^2+b^2+c^2 \ge 4T\sqrt{3}+(a-b)^2+(b-c)^2+(c-a)^2 $.

See if you can prove that...

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

Practice Problem: Let $ a, b, c $ be the sides of a triangle, and $ T $ its area. Prove:

$ a^2+b^2+c^2 \ge 4T\sqrt{3}+(a-b)^2+(b-c)^2+(c-a)^2 $.

Friday, February 9, 2007

Don't You Wish You Remembered Those Trig Identities. Topic: Trigonometry. Level: AMC/AIME.

Problem: (1962 IMO - #4) Solve the equation $ \cos^2{(x)}+\cos^2{(2x)}+\cos^2{(3x)} = 1 $.

Solution: Subtract the $ \cos^2{(3x)} $ from both sides, and replace the LHS by $ \sin^2{(3x)} $, so we now have

$ \cos^2{(x)}+\cos^2{(2x)} = \sin^2{(3x)} $.

Recalling the sine angle addition identity, we write

$ \sin{(3x)} = \sin{(2x+x)} = \sin{(2x)}\cos{(x)}+\sin{(x)}\cos{(2x)} $.

So our equation is

$ \cos^2{(x)}+\cos^2{(2x)} = [\sin{(2x)}\cos{(x)}+\sin{(x)}\cos{(2x)}]^2 $.

Expanding, collecting terms, and simplifying using $ 1-\sin^2{(2x)} = \cos^2{(2x)} $ and $ 1-\sin^2{(x)} = \cos^2{(x)} $, we get

$ 2\cos^2{(x)} \cos^2{(2x)} = 2\sin{(x)}\cos{(x)}\sin{(2x)}\cos{(2x)} $.

Divide by $ 2 $, rearrange, and factor:

$ \cos{(x)}\cos{(2x)}[\cos{(x)}\cos{(2x)}-\sin{(x)}\sin{(2x)}] = 0 $.

Substitute using the double-angle identities $ \cos{(2x)} = 1-2\sin^2{(x)} $ and $ \sin{(2x)} = 2\sin{(x)}\cos{(x)} $ to finally find

$ \cos^2{(x)} \cos{(2x)} [1-4\sin^2{(x)}] = 0 $.

Solving yields

$ x = \frac{\pi}{2}+k\pi \mbox{ ; } \frac{\pi}{4}+\frac{k \pi}{2} \mbox{ ; } \frac{\pi}{6}+k\pi \mbox{ ; } \frac{5 \pi}{6}+k \pi $

for all integers $ k $. QED.

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

Comment: Pretty standard and slightly ugly manipulation of trig identities, but overall not too bad. Considering you get like an hour or more to do this, I don't feel too bad about it. Other solutions taking into account symmetry or using DeMoivre's and stuff are also out there, but this seemed much more straightforward and easier to develop.

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

Practice Problem: (2007 AMC 12A - #24) For each integer $ n > 1 $, let $ F(n) $ be the number of solutions of the equation $ \sin{(x)} = \sin{(nx)} $ on the interval $ [0, \pi] $. What is $ \displaystyle \sum_{n=2}^{2007} F(n) $?

Wednesday, February 7, 2007

Spacy. Topic: S&S/Sets. Level: AMC.

Problem: (2007 AMC 12A - #25) Call a set of integers spacy if it contains no more than one out of any three consecutive integers. How many subsets of $ \{1, 2, 3, \ldots, 12\} $, including the empty set, are spacy?

Solution: We will solve this problem with a recursion on $ S_n $, which we will define as the number of spacy subsets of $ \{1, 2, 3, \ldots, n\} $. We can easily calculate

$ S_0 = 1 $, $ S_1 = 2 $, $ S_2 = 3 $, and $ S_3 = 4 $.

Now we will think about how to evaluate $ S_n $ in terms of previous terms. Obviously, we can keep all the subsets in $ S_{n-1} $. These will account for any space subsets that don't contain the element $ n $. Now we just need to count the ones that do contain the element $ n $.

If a spacy subset contains $ n $, it cannot have $ n-1 $ or $ n-2 $. So take all the spacy subsets of $ \{1, 2, \ldots, n-3\} $ and add the element $ n $ to them to get all the spacy subsets that contain $ n $. Since these are both of the cases, we obtain

$ S_n = S_{n-1}+S_{n-3} $.

Some calculations yield $ S_{12} = 129 $. QED.

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

Comment: In all honesty, a pretty standard recursion problem, which is probably better off on an easy olympiad-style contest because it's too easy to guess on the AMC. After just calculating a few terms, it wasn't hard to see the recursion and assume its validity. A more interesting problem would be to find the closed form for that recursion (eww?). Maybe generating functions will save the day.

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

Practice Problem: Can you find a closed form for $ S_n $?

Tuesday, February 6, 2007

Sunday, February 4, 2007

Mean. Topic: Algebra/Probability & Combinatorics/Calculus. Level: Olympiad.

Problem: (1983 Canada - #5) Show that the geometric mean of a set $ S $ of positive numbers equals the geometric mean of the geometric means of all non-empty subsets of $ S $. [Reworded]

Solution: Let $ S = \{a_1, a_2, \ldots, a_n\} $, so the geometric mean is $ (a_1a_2 \cdots a_n)^{\frac{1}{n}} $. We will show that the geometric mean of the geometric means of all non-empty subsets of $ S $ is equivalent to this. It suffices to show it is true for an arbitrary $ a_i $. Consider dividing the subsets of $ S $ that contain $ a_i $ into groups based on the number of elements it contains. We will count how many of them there are:

$ 1 $-element subsets containing $ a_i $ - clearly just the set $ \{a_i\} $. There is only $ 1 $;

$ 2 $-element subsets containing $ a_i $ - the set $ \{a_i, a_j\} $ for any $ j \neq i $. There are $ (n-1)C1 $ of these;

$ 3 $-element subsets containing $ a_i $ - there are $ (n-1)C2 $ of these.

It's pretty clear that if we want a $ k $-element subset containing $ a_i $ we are free to choose the other $ k-1 $ elements from the remaining $ n-1 $ elements of $ S $. If we take the geometric mean of these subsets, however, we find that

$ 1 $-element subsets give a full power of $ a_i $;

$ 2 $-element subsets give a $ \frac{1}{2} $ power of $ a_i $;

$ 3 $-element subsets give a $ \frac{1}{3} $ power of $ a_i $;

and so on. So when we multiply these all together, we get an exponent of

$ \displaystyle 1+(n-1)C1 \cdot \frac{1}{2}+(n-1)C2 \cdot \frac{1}{3}+ \cdots +(n-1)C(n-1) \cdot \frac{1}{n} = \sum_{k=1}^n \frac{1}{k} \cdot (n-1)C(k-1) $.

It remains to evaluate this sum, but we can do that through generating functions. Since $ \displaystyle (1+x)^{n-1} = \sum_{k=1}^n (n-1)C(k-1) \cdot x^{k-1} $, we integrate both sides to get

$ \displaystyle \frac{(1+x)^n}{n} = C+\sum_{k=1}^n \frac{1}{k}(n-1)C(k-1) \cdot x^k $.

Using $ x = 0 $, we obtain $ C = \frac{1}{n} $, so $ \displaystyle \frac{(1+x)^n-1}{n} = \sum_{k=1}^n \frac{1}{k}(n-1)C(k-1) \cdot x^k $.

Finally, by the substitution $ x = 1 $, we get the desired summation:

$ \displaystyle \sum_{k=1}^n \frac{1}{n} \cdot (n-1)C(k-1) = \frac{2^n-1}{n} $.

So prior to the last geometric mean, we have $ (a_i)^{\frac{2^n-1}{n}} $, but we know that there are $ 2^n-1 $ non-empty subsets of $ S $, which means the last geometric mean is a power of $ \frac{1}{2^n-1} $, and we have

$ \left(a_i^{\frac{2^n-1}{n}}\right)^{\frac{1}{2^n-1}} = (a_i)^{\frac{1}{n}} $,

the same power as the original geometric mean we computed. QED.

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

Comment: A very nice problem because it branched together several aspects of mathematics all into a single problem, which is always cool. There is probably a non-calculus method of evaluating that sum, but basically any time you see a sum like that you can use generating functions and then apply derivatives/integrals to make it what you want. Apparantly a symmetry argument can also be made, but that's probably just the lazy way to do this problem...

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

Practice Problem: (1983 Canada - #4) Given an arbitrary prime $ p $, show that we can find infinitely many positive integers $ n $ such that $ 2^n-n $ is a multiple of $ p $.

Saturday, February 3, 2007

2007 Northwest Math Championships.

Good job Bellevue today at the 2007 NWMC! We did amazing!

3rd Place 9/10 Team

1st Place 11/12 Team

Tuesday, January 30, 2007

Even, Odd, Even, Odd... Topic: Algebra/S&S. Level: AMC/AIME.

Problem: Show that the sequence $ \lfloor \sqrt{2} \rfloor, \lfloor 2\sqrt{2} \rfloor, \lfloor 3\sqrt{2} \rfloor, \ldots $ contains an infinte number of both even and odd integers. Furthermore, show that there can be at most two consecutive integers of the same parity.

Solution: Suppose their exists a finite number of either even or odd integers. Then we definitely have three integers of the same parity in a row. But since $ 1 < \sqrt{2} < 2 $, they must each differ by $ 2 $. Hence

$ \lfloor k\sqrt{2}\rfloor+2 = \lfloor (k+1)\sqrt{2} \rfloor $

$ \lfloor (k+1)\sqrt{2}\rfloor+2 = \lfloor (k+2)\sqrt{2} \rfloor $.

Adding the equalities together, we get

$ \lfloor k\sqrt{2} \rfloor+4 = \lfloor (k+2)\sqrt{2}\rfloor $.

By the standard floor function inequalities, however, we know that $ x-1 < \lfloor x \rfloor < x $ when $ x $ is not an integer. Hence

$ \lfloor k\sqrt{2}\rfloor+4 > k\sqrt{2}+3 > k\sqrt{2}+2\sqrt{2} > \lfloor (k+2)\sqrt{2} \rfloor $,

a contradiction. Hence we have proved both of the desired results. QED.

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

Comment: An interesting result which can be simply generalized to any irrational $ 1 < \alpha < 2 $ and probably any positive irrational $ \alpha $ at all (see if you can prove this). It wasn't hard to reason out that because $ \sqrt{2} < 1.5 $ we really cannot have three integers of the same parity in a row in that sequence. Adding a touch of rigor to the proof turned out to be quite easy as well.

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

Practice Problem: Prove or disprove that, given a positive irrational $ \alpha > 0 $, the sequence $ \lfloor \alpha \rfloor, \lfloor 2\alpha \rfloor, \lfloor 3\alpha \rfloor, \ldots $ contains an infinite number of both even and odd integers.

Sunday, January 28, 2007

Distasteful Distance. Topic: Sequences & Series. Level: AIME.

Problem: (1997 Putnam - B1) Let $ \{x\} $ denote the distance between the real number $ x $ and the nearest integer. For each positive integer $ n $, evaluate

$ \displaystyle F_n = \sum_{m=1}^{6n-1} \min(\{\frac{m}{6n}\}, \{\frac{m}{3n}\}) $.

Solution: Well since $ \frac{m}{6n} $ lies in the interval $ (0, 1) $, we can just characterize $ \min(\{x\}, \{2x\}) $ for all $ x \in (0, 1) $. We split it up into three intervals:

If $ 0 < x \le \frac{1}{3} $, we have $ \{x\} \le \{2x\} $ because $ 2x \ge x $ and $ 1-2x \ge x $.

If $ \frac{1}{3} < x \le \frac{2}{3} $, we have $ \{2x\} \le \{x\} $ because $ x \ge |1-2x| $ and $ 1-x \ge |1-2x| $.

If $ \frac{2}{3} < x < 1 $, we again have $ \{x\} \le \{2x\} $ because $ 2x-1 \ge 1-x $ and $ 2-2x \ge 1-x $.

This translates to $ 1 \le m \le 2n $, $ 2n+1 \le m \le 4n $, and $ 4n+1 \le m \le 6n-1 $, so we sum the intervals separately (note that we split the middle interval again into two parts to avoid absolute values):

$ \displaystyle \sum_{m=1}^{2n} \frac{m}{6n} = \frac{1}{6n} \cdot \frac{2n(2n+1)}{2} = \frac{2n+1}{6} $

$ \displaystyle \sum_{m=2n+1}^{3n} \left(1-\frac{m}{3n}\right) = \sum_{m=0}^{n-1} \frac{m}{3n} = \frac{1}{3n} \cdot \frac{(n-1)n}{2} = \frac{n-1}{6} $

$ \displaystyle \sum_{m=3n+1}^{4n} \left(\frac{m}{3n}-1\right) = \sum_{m=1}^n \frac{m}{3n} = \frac{1}{3n} \cdot \frac{n(n+1)}{2} = \frac{n+1}{6} $

$ \displaystyle \sum_{m=4n+1}^{6n-1} \left(1-\frac{m}{6n}\right) = \sum_{m=1}^{2n-1} \frac{m}{6n} = \frac{1}{6n} \cdot \frac{(2n-1)2n}{2} = \frac{2n-1}{6} $.

Summing them together we have

$ F_n = \frac{2n+1}{6}+\frac{n-1}{6}+\frac{n+1}{6}+\frac{2n-1}{6} = n $.

QED.

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

Comment: A pretty neat, although contrived, summation to just get simply to $ n $. The key was splitting the summation up; without doing that, it's really not possible to evaluate the sum in easy ways (like summing the first $ k $ positive integers multiple times). Figuring out how the function $ \{x\} $ worked helped a lot in determining the behavior of $ \min(\{x}, \{2x\}) $.

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

Practice Problem: Evaluate the sum

$ \displaystyle \sum_{i=1}^{\infty} \lfloor \frac{n+2^{i-1}}{2^i} \rfloor = \lfloor \frac{n+1}{2} \rfloor+\lfloor \frac{n+2}{4} \rfloor+\lfloor \frac{n+4}{8} \rfloor+\cdots $.

Saturday, January 27, 2007

Vector Magic. Topic: Geometry. Level: AIME.

Problem: (1997 Putnam - A1) A rectangle, $ HOMF $, has sides $ HO = 11 $ and $ OM = 5 $. A triangle $ ABC $ has $ H $ as the intersection of its altitudes, $ O $ the center of its circumscribed circle, $ M $ the midpoint of $ BC $, and $ F $ the foot of the altitude from $ A $. What is the length of $ BC $?

Solution: Since everyone loves algebra and hates geometry, let's use the standard algebrization of a triangle problem: vectors. Set $ O $ to be the origin, $ H $ to $ (-11, 0) $, from which we automatically obtain $ M = (0, -5) $ and $ F = (-11, -5) $. Let $ a, b, c $ be the vectors from $ O $ to points $ A, B, C $, respectively.

We know $ |a| = |b| = |c| $ and $ a+b+c = H $ from here, so we'll use these results. Also, $ b+c = 2M $ by the definition of a midpoint. Using these three equations, we can solve for $ a, b, c $.

$ a+b+c = (-11, 0) $ and $ b+c = (0, -10) $ implies that $ a = (-11, 10) $.

Also, the $ x $-coordinates of $ b $ and $ c $ are the same value with opposite signs. So if $ |a| = |b| $, where $ a = (-11, 10) $ and $ b = (-x, -5) $, we must have

$ 11^2+10^2 = x^2+5^2 \Rightarrow x^2 = 196 \Rightarrow x = 14 $.

So $ BC = |b-c| = |(-28,0)| = 28 $. QED.

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

Comment: There are various other synthetic ways to approach this problem, but using vectors seems to make life really easy as we know lots of relationships about the circumcenter, orthocenter, and midpoints. See if you can convince me that there is a simpler way to do it without vectors.

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

Practice Problem: "Prove" that the vector representation of the orthocenter $ H $ has to be symmetric in $ a, b, c $ (i.e. explain why you know $ H = a(b+c) $ is wrong).

Wednesday, January 24, 2007

Log Rolling. Topic: Inequalities. Level: AIME.

Problem: Given reals $ a, b, c \ge 2 $, show that $ \log_{a+b}(c)+\log_{b+c}(a)+\log_{c+a}(b) \ge \frac{3}{2} $.

Solution: Recall the change-of-base identity for logs. We can rewrite the LHS as

$ \frac{\log{c}}{\log{(a+b)}}+\frac{\log{a}}{\log{(b+c)}}+\frac{\log{b}}{\log{(c+a)}} $.

Note, however that $ (a-1)(b-1) \ge 1 \Rightarrow ab \ge a+b \Rightarrow \log{a}+\log{b} = \log{(ab)} \ge \log{(a+b)} $, so it remains to show that

$ \frac{\log{c}}{\log{a}+\log{b}}+\frac{\log{a}}{\log{b}+\log{c}}+\frac{\log{b}}{\log{c}+\log{a}} \ge \frac{3}{2} $,

which is true by Nesbitt's Inequality. QED.

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

Comment: A good exercise in using log identities and properties to achieve a relatively simple result. Once we made the change-of-base substitution, seeing the $ \frac{3}{2} $ should clue you in to Nesbitt's. That led to the inequality $ \log{a}+\log{b} \ge \log{(a+b)} $, which was easily proven given the conditions of the problem.

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

Practice Problem: Given reals $ a, b, c \ge 2 $, find the best constant $ k $ such that

$ \log_{a+b+c}(a)+\log_{a+b+c}(b)+\log_{a+b+c}(c) \ge k $.

Sunday, January 21, 2007

Who Loves Algebra? Topic: Algebra. Level: AIME/Olympiad.

Problem: (1999 Putnam - A3) Consider the power series expansion $ \displaystyle \frac{1}{1-2x-x^2} = \sum_{n=0}^{\infty} a_nx^n $. Prove that, for each integer $ n \ge 0 $, there is an integer $ m $ such that $ a_n^2+a_{n+1}^2 = a_m $.

Solution: Playing around with the expansion for a bit (using geometric series or otherwise), we find that $ a_0 = 1 $, $ a_1 = 2 $, $ a_2 = 5 $ so $ a_0^2+a_1^2 = a_2 $. Realizing that the calculation gets uglier and uglier, we decide to go for the general case right now. Now we need to find a good expansion. Try partial fractions.

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

Now, to simplify our lives, we let $ \alpha = \sqrt{2}+1 $. Note that $ \frac{1}{\alpha} = \sqrt{2}-1 $, so this may turn out to be a key substitution. We get

$ \displaystyle \frac{1}{2\sqrt{2}}\left(\frac{1}{\sqrt{2}-1-x}+\frac{1}{\sqrt{2}+1+x}\right) = \frac{1}{2\sqrt{2}}\left(\frac{\alpha}{1-\alpha x}+\frac{1}{\alpha} \cdot \frac{1}{1+\frac{x}{\alpha}}\right) $.

Expanding both fractions using a geometric series, we obtain

$ \frac{1}{2\sqrt{2}}\displaystyle \sum_{n=0}^{\infty} x^n \cdot \left(\alpha^{n+1}+\frac{(-1)^n}{\alpha^{n+1}}\right) $,

a remarkably simple expression given what we had up there. It remains to show that $ a_n^2+a_{n+1}^2 $ also has the form of one of those. So, plugging the appropriate values, we see that

$ \displaystyle \frac{1}{8}\left[\left(\alpha^{n+1}+\frac{(-1)^n}{\alpha^{n+1}}\right)^2+\left(\alpha^{n+2}+\frac{(-1)^{n+1}}{\alpha^{n+2}}\right)^2\right] = \frac{1}{8} \left(\alpha^{2n+4}+\alpha^{2n+2}+\frac{1}{\alpha^{2n+2}}+\frac{1}{\alpha^{2n+4}}\right) $

because the middle terms in the squaring cancel out nicely (and the $ \frac{1}{8} $ came from the squaring of the constant $ \frac{1}{2\sqrt{2}} $). So, recalling that when $ n = 0 $, we had $ a_n^2+a_{n+1}^2 = a_{2n+2} $, we want to make that last expression look like $ a_{2n+2} $. A clever factorization yields

$ \displaystyle \frac{1}{8} \left[ \alpha^{2n+3}\left(\alpha+\frac{1}{\alpha}\right)+\frac{1}{\alpha^{2n+3}} \left(\alpha+\frac{1}{\alpha}\right) \right] = \frac{\alpha+\frac{1}{\alpha}}{8} \left( \alpha^{2n+3}+\frac{1}{\alpha^{2n+3}} \right) $.

Note, however, that $ \alpha+\frac{1}{\alpha} = (\sqrt{2}+1)+(\sqrt{2}-1) = 2\sqrt{2} $, so the result is

$ \frac{1}{2\sqrt{2}} \left( \alpha^{2n+3}+\frac{(-1)^{2n+2}}{\alpha^{2n+3}} \right) = a_{2n+2} $

by the expansion we found earlier. QED.

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

Comment: That looked like a lot of work, and it was. The hardest parts were definitely (1) finding out that using the partial fraction decomposition was the best way to go, (2) making the substitution that allowed things to cancel nicely, and (3) keeping track of my work. This is a pretty cool result, which you can usually expect from Putnam problems that have large amounts of algebraic manipulation (you'd hope so, anyway). But in the end, we are left with a satisfactory feeling, so it's all good.

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

Practice Problem: (1999 Putnam - B2) Let $ P(x) $ be a polynomial of degree $ n $ such that $ P(x) = Q(x)P^{\prime\prime}(x) $, where $ Q(x) $ is a quadratic polynomial and $ P^{\prime\prime}(x) $ is the second derivative of $ P(x) $. Show that if $ P(x) $ has at least two distinct roots then it must have $ n $ distinct roots.

Friday, January 19, 2007

Triangularly Speaking. Topic: Algebra/Geometry. Level: AIME.

Problem: Suppose the roots of the cubic polynomial $ P(x) = x^3-2rx^2+sx+t $ are the sides of a triangle (assume they are all positive reals and satisfy the triangle inequality). What is the area of the triangle in terms of the coefficients?

Solution: Well, let's think about the formulas for the area of a triangle given its side lengths. The only one that comes to mind that uses only side lengths is Heron's formula. Why don't we try that?

$ A = \sqrt{s(s-a)(s-b)(s-c)} $,

where $ a, b, c $ are the side lengths and $ s = \frac{a+b+c}{2} $. From $ P(x) $, by Vieta's, we know that $ r_1+r_2+r_3 = 2r $, where $ r_i $ are the roots of the polynomial. So $ s $ in this case is $ r $. How do we get the rest, though? We could expand and use Newton sums, but that sounds like a pain. Note that

$ (s-a)(s-b)(s-c) $ looks a lot like $ (x-a)(x-b)(x-c) $.

But wait, that's just a polynomial with roots $ a, b, c $! So if we write $ P(x) = (x-r_1)(x-r_2)(x-r_3) $, we have $ (s-a)(s-b)(s-c) = (s-r_1)(s-r_2)(s-r_3) = P(s) = P(r) $. Thus we can say that the area of the triangle is

$ \sqrt{s(s-a)(s-b)(s-c)} = \sqrt{rP(r)} $,

which can clearly be evaluated in terms of the coefficients. QED.

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

Comment: This is probably one of the neatest tricks that Vieta's can help you with, as well as a cool link between algebra and geometry. Before I thought of this problem, I had never realized the now-clear relationship between Heron's formula and a cubic polynomial with sides as the roots. A nice discovery.

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

Practice Problem: (2007 Mock AMC 12 - #24) The lengths of the sides of a triangle are the roots of the equation $ 7x^3+35x = 28x^2+13 $. If the square of the area of the triangle is $ \displaystyle \frac{p}{q} $, where $ p $ and $ q $ are relatively prime positive integers, what is $ p+q $?

Wednesday, January 17, 2007

Ugly! Topic: Algebra. Level: AIME.

Problem: (2001 Putnam - B2) Find all pairs of real numbers $ (x,y) $ satisfying the system of equations

$ \displaystyle \frac{1}{x}+\frac{1}{2y} = (x^2+3y^2)(3x^2+y^2) $ and $ \displaystyle \frac{1}{x}-\frac{1}{2y} = 2(y^4-x^4) $.

Solution: Add and subtract the two equations to get two new equations

$ \frac{2}{x} = x^4+10x^2y^2+5y^4 $ and $ \frac{1}{y} = y^4+10y^2x^2+5x^4 $,

which look curiously similar. Anyway, multiply through by $ x $ and $ y $, respectively, to find

$ 2 = x^5+10x^3y^2+5xy^4 $ and $ 1 = y^5+10x^2y^3+5x^4y $.

Hmm, $ 1, 5, 10, \ldots $. Those look suspiciously like binomial coefficients. Add and subtract these two equations as well, resulting in

$ 3 = x^5+5x^4y+10x^3y^2+10x^2y^3+5xy^4+y^5 = (x+y)^5 $

$ 1 = x^5-5x^4y+10x^3y^2-10x^2y^3+5xy^4-y^5 = (x-y)^5 $.

Well, taking the fifth roots and solving the easy linear system, we have determined that the only solution is $ \displaystyle (x,y) = \left(\frac{\sqrt[5]{3}+1}{2} \mbox{ }, \frac{\sqrt[5]{3}-1}{2}\right) $. QED.

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

Comment: Nice how these two ugly equations reduce to two simple equations through a process of no more than three steps. Of course, working it out required a lot more than that unless you just luckily stumbled upon the answer. This is a good exercise is recognizing familiar factorizations (the binomial theorem, Sophie Germain identity, and $ a^3+b^3+c^3-3abc $ come to mind), which can often result in a clean solution to a problem.

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

Practice Problem: (2001 Putnam - A3) For each integer $ m $, consider the polynomial

$ P_m(x) = x^4-(2m+4)x^2+(m-2)^2 $.

For what values of $ m $ is $ P_m(x) $ the product of two nonconstant polynomials with integer coefficients?

Monday, January 15, 2007

What Can Integrals Do For You? Topic: Calculus.

Problem: Evaluate $ \displaystyle \int_{-1}^0 \sqrt{\frac{1+x}{1-x}} dx $.

Solution: Well, it looks not cool right now, so lets multiply through by $ \displaystyle \sqrt{\frac{1+x}{1+x}} $. We get $ \displaystyle \int_{-1}^0 \frac{1+x}{\sqrt{1-x^2}} dx $.

That's nice; split up the integral into two parts, from which we obtain

$ \displaystyle \int_{-1}^0 \frac{1}{\sqrt{1-x^2}} dx + \int_{-1}^0 \frac{x}{\sqrt{1-x^2}}dx = \left[\arcsin{x}-\sqrt{1-x^2}\right]_{-1}^0 = \frac{\pi}{2}-1 $.

QED.

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

Comment: Not the toughest of integrals, but if you tried various substitutions like I did first, you probably found yourself with worse ones. Funny how a simple thing like this solves it.

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

Practice Problem: Let $ f(x) $ be a differentiable and increasing function such that $ f(0) = 0 $. Prove that $ \displaystyle \int_0^1 f(x) f^{\prime}(x)dx \ge \frac{1}{2}\left(\int_0^1 f(x) dx \right)^2 $.

Sunday, January 14, 2007

Whoa... Topic: Geometry/Inequalities. Level: AIME/Olympiad.

Problem: (2000 Putnam - A5) Three distinct points with integer coordinates lie in the plane on a circle of radius $ r > 0 $. Show that two of these points are separated by a distance of at least $ r^{1/3} $.

Solution: I will admit that this is not my solution. But it's just so amazingly awesome it deserves to be here.

Let the triangle formed by the segments between the three points have side lengths $ a, b, c $. By a well-known formula, the area of the this triangle is $ \frac{abc}{4r} $.

On the other hand, by Pick's Formula, we know the area is $ I+\frac{B}{2}-1 \ge \frac{3}{2}-1 = \frac{1}{2} $. So

$ \frac{abc}{4r} \ge \frac{1}{2} \Rightarrow abc \ge 2r $.

But by AM-GM, we have $ \max\{a, b, c\} \ge (abc)^{1/3} \ge (2r)^{1/3} > r^{1/3} $. QED.

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

Comment: This is a really neat solution because it uses some well-known formulas to prove a very interesting result. Finding it would probably be considerably more difficult than reading it (as with many proofs), but the conciseness of the proof is almost too good to be true.

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

Practice Problem: (2000 Putnam - A4) Show that the improper integral $ \displaystyle \lim_{B \rightarrow \infty} \int_0^B \sin{(x)} \sin{(x^2)} dx $ converges.

Thursday, January 11, 2007

Guess What? Topic: Probability/Sets. Level: AIME/Olympiad.

Problem: (2002 Putnam - B4) An integer $ n $, unknown to you, has been randomly chosen in the interval $ [1, 2002] $ with uniform probability. Your objective is to select $ n $ in an odd number of guesses. After each incorrect guess, you are informed whether $ n $ is higher or lower, and you must guess an integer on your next turn among the numbers that are still feasibly correct. Show that you have a strategy so that the chance of winning is greater than $ 2/3 $.

Solution: We first prove that, in the interval $ [1, 3k] $, we can guess with a strategy that allows us to get the desired number in an even number of guesses with $ \frac{2}{3} $ probability. This is easy by induction.

Base case: $ [1,3] $. Pick $ 2 $. If $ n = 2 $, it's an odd number, but if $ n \neq 2 $, we can get it in the subsequent guess. So there is a $ \frac{2}{3} $ chance.

Induction step: Suppose it's true for the interval $ [1,3k] $. We want to show it is true for the interval $ [1,3k+3] $. Start by choosing $ 3k+2 $. If $ n = 3k+2 $, it's an odd number of guesses, but if $ n = 3k+3 $, it's even. Then guess $ 3k+1 $ (if we find that $ n < 3k+2 $) on the second guess. So if $ n = 3k+1, 3k+3 $, we can get it in an even number of guess. If we find that $ n < 3k+1 $, it's just choosing from the interval $ [1,3k] $ in an even number of guesses, so by the inductive hypothesis this is $ \frac{2}{3} $. Hence the probabability in the interval $ [1, 3k+3] $ is

$ P(n=3k+3)+P(n=3k+1)+P(n<3k+1) \cdot P(\text{even # of guesses}) = \frac{1}{3k+3}+\frac{1}{3k+3}+\frac{3k}{3k+3} \cdot \frac{2}{3} = \frac{2}{3} $

completing the induction.

So now we have the interval $ [1, 2002] $. Choose $ 2002 $. If $ n = 2002 $, we're done in an odd number of guesses. Otherwise, we want to guess $ n $ which is in $ [1,2001] = [1,3 \cdot 667] $ in an even number of guesses. By the lemma above, the probability of this is $ \frac{2}{3} $.

Therefore, the total probability is $ P(n = 2002)+P(n<2002) \cdot P(\text{even # of guesses}) = \frac{1}{2002}+\frac{2001}{2002} \cdot \frac{2}{3} = \frac{1335}{2002} > \frac{2}{3} $, as desired. QED.

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

Comment: This was a pretty neat problem. The way I figured out the solution was by an interesting recursion that find the best strategy for $ [1,m] $ based on optimizing the best strategies for $ [1,k] $ with $ k < m $ in trying to get an even and odd number of guesses. The pattern revealed the first lemma, which lead directly to the solution. It seems like some of the later problems on the test were a little easier than the earlier problems.

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

Practice Problem: (2002 Putnam - A3) Let $ n \ge 2 $ be an integer and $ T_n $ be the number of non-empty subsets $ S $ of $ \{1, 2, \ldots, n\} $ with the property that the average of the elements of $ S $ is an integer. Prove that $ T_n-n $ is always even.

2007 Mock AMC 12.

Here's my mock AMC 12; if you want to take it and submit answers, please do so via private message at the Art of Problem Solving Forums. The test can be found here.

Monday, January 8, 2007

A Bit Familiar. Topic: Algebra/NT. Level: Olympiad.

Problem: (2002 Putnam - A5) Define a sequence by $ a_0 = 1 $, together with the rules $ a_{2n+1} = a_n $ and $ a_{2n+2} = a_n+a_{n+1} $ for each integer $ n \ge 0 $. Prove that every positive rational appears in the set

$ \left\{\frac{a_{n-1}}{a_n}: n \ge 1 \right} = \left{\frac{1}{1}, \frac{1}{2}, \frac{2}{1}, \frac{1}{3}, \frac{3}{2}, \cdots \right\} $.

Solution: Consider the sequence $ \displaystyle b_n = \frac{a_{n-1}}{a_n} $. We know $ b_1 = 1 $ and we want to find a recursion for $ b $. We can see that

$ \displaystyle b_{2n+1} = \frac{a_{2n}}{a_{2n+1}} = \frac{a_{n-1}+a_n}{a_n} = 1+b_n $ (1)

$ \displaystyle b_{2n+2} = \frac{a_{2n+1}}{a_{2n+2}} = \frac{a_n}{a_n+a_{n+1}} = \frac{1}{1+\frac{1}{b_{n+1}}} = 1-\frac{1}{1+b_{n+1}} $ (2) .

We will now prove the result by strong induction on the denominator of $ \frac{p}{q} $. We know that for $ q = 1 $, the term $ \frac{1}{1} $ appears, so by applying (1) inductively we know $ \frac{p}{1} $ appears for all $ p $.

So suppose that all fractions of the form $ \frac{p}{q} $ with $ q < k $ appear in the set. We wish to show that all fractions $ \frac{p}{q} $ with $ q = k $ appear. We see that

$ \displaystyle \frac{1}{k-1} \rightarrow \frac{1}{k} $ by (2).

In fact, since we know $ \frac{m}{k-m} $ is in the set for $ 0 < m < k $ already, we get

$ \displaystyle \frac{m}{k-m} \rightarrow \frac{m}{k} $ by (2).

Hence we have found that $ \frac{1}{k}, \frac{2}{k}, \cdots, \frac{k-1}{k} $ are all in the set. But then, by applying (1) inductively on each of the fractions, we know that

$ \frac{m}{k}+r = \frac{m+kr}{k} $

is in the set, for $ m = 1, 2, \ldots, k-1 $ and $ r = 1, 2, \ldots $, which easily gives us $ \frac{s}{k} $ is in the set for any $ s \not\equiv 0 \pmod{k} $, but those are all integers, which are covered in the first base case. Hence we have shown that all positive rationals with denominator $ k $ are in the set, completing the induction. QED.

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

Comment: Not too hard for an A5 on the Putnam, especially if you've seen types of problems like this before. The crux step was probably getting the recursions for the $ b $ sequence, which then allowed you to discover how the rationals are produced. As noted above, it seemed a bit familiar, and a very similar problem showed up on my blog before and a similar proof was given. This one was a little more complicated, but the main ideas are the same.

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

Practice Problem: Can you modify the sequence in the problem to generate all negative rationals as well?

Sunday, January 7, 2007

Big. Topic: Algebra/Inequalities. Level: AIME.

Problem: (2002 Putnam - B3) Show that, for all integers $ n > 1 $,

$ \displaystyle \frac{1}{e}-\left(1-\frac{1}{n}\right)^n < \frac{1}{ne} $. [Reworded]

Solution: First of all, this is only one of two inequalities in the problem, but it's the cooler half... yeah. We will rewrite the inequality as

$ \displaystyle 1-\frac{1}{n} < e \left(1-\frac{1}{n}\right)^n $.

Using the fact that $ \displaystyle \lim_{n \rightarrow \infty} \left(1+\frac{1}{n}\right)^n = e $ from below, we know

$ \displaystyle e > \left(1+\frac{1}{n}\right)^n $

so

$ \displaystyle e \left(1-\frac{1}{n}\right)^n > \left(1+\frac{1}{n}\right)^n \left(1-\frac{1}{n}\right)^n = \left(1-\frac{1}{n^2}\right)^n > 1-\frac{1}{n} $,

where the last step follows from the binomial expansion or the Bernoulli Inequality. And we're done. QED.

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

Comment: Basically, all you really needed was to estimate $ e $ somehow, so the limit form came in handy. The other inequality was showing that the LHS is $ > \frac{1}{2ne} $, but the only solution that I know to that one is taking the $ \log $ and expanding using the Taylor series, which isn't as cool.

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

Practice Problem: The left inequality not shown here can also be written as

$ \displaystyle e < \left(1+\frac{1}{n}+\frac{1}{2n(n-1)}\right)^n $.

Can you show this?

Thursday, January 4, 2007

Spinning Away... Topic: Complex Numbers. Level: AIME/Olympiad.

Problem: (2004 Putnam - B4) Let $ n $ be a positive integer, $ n \ge 2 $, and put $ \theta = 2 \pi /n $. Define points $ P_k = (k,0) $ in the $ xy $- plane, for $ k = 1, 2, \ldots, n $. Let $ R_k $ be the map that rotates the plane counterclockwise by the angle $ \theta $ about the point $ P_k $. Let $ R $ denote the map obtained by applying, in order, $ R_1 $, then $ R_2 $, $ \ldots $, then $ R_n $. For any arbitrary point $ (x,y) $, find, and simplify, the coordinates of $ R(x,y) $.

Solution: Hmm, rotations, and lots of them. That's a big hint to use complex numbers! Recall that the rotation of a point $ z_1 $ around a point $ z_2 $ counterclockwise by an angle of $ \alpha $ is $ z_2+(z_1-z_2)e^{i \alpha} $. Let's use this formula over and over again.

Start with the point $ x+yi $, but write it as $ r e^{i \phi} $, which is much more convenient notation for rotating. Then, if we rotate around $ P_1 = 1 $, we get

$ re^{i \phi} \rightarrow 1+(re^{i \phi}-1)e^{i \theta} = 1-e^{i \theta}+re^{i(\phi+\theta)} $.

Continuing this, rotating around $ P_2 = 2, P_3 = 3, \ldots, P_n = n $, we find that the points are

$ 2-(e^{i \theta}+e^{i 2\theta})+re^{i(\phi+2\theta)} $, $ 3-(e^{i \theta}+e^{i 2\theta}+e^{i 3\theta})+re^{i(\phi+3\theta)} $, $ \ldots $.

An easy induction gives us the final position as

$ \displaystyle n - \sum_{k=1}^n e^{i k \theta} + re^{i(\phi+n\theta)} $.

However, we know that $ e^{i k \theta} $ for $ k = 1, 2, \ldots, n $ are the roots of the polynomial $ x^n-1 = 0 $, so their sum is zero. Also, $ n\theta = 2 \pi $ so $ re^{i(\phi+n\theta)} = re^{i\phi} $. Thus the result is

$ n+r^{i \phi} = (n,0)+(x,y) = (x+n, y) $.

QED.

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

Comment: This is a really neat application of the power of complex numbers in rotation problems. Basically, rotating in the plane means use complex numbers to reduce everything to algebra (which is infinitely better than geometry...). Not bad at all for a B4. Note another solution that I found to be quite interesting. Take a regular $ n $-gon of side length $ 1 $ and top edge with vertices $ (0, 0) $ and $ (1, 0) $. The map $ R $ corresponds to a "rolling" of the $ n $-gon along the $ x $-axis. Since that translates the $ n $-gon $ n $ units in the positive $ x $ direction, it can be argued that it does the same for all points in the plane.

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

Practice Problem: Given three points $ A, B, C $, let $ \theta_1, \theta_2, \theta_3 $ be the smallest angles that $ A $ must be rotated to lie on line $ BC $, $ B $ must be rotated to lie on line $ AC $, and $ C $ must be rotated to lie on $ AB $, respectively. Find the maximum value of $ \theta_1+\theta_2+\theta_3 $.

Monday, January 1, 2007

2K7. Topic: Calculus. Level: Olympiad.

Problem: (2005 Putnam - A5) Evaluate $ \displaystyle \int_0^1 \frac{\ln{(x+1)}}{x^2+1} dx $.

Solution: This seemingly harmless integral will turn into a beast in a moment, but first, the Leibniz Integral Rule. This states that, for a multivariate function $ f(x, t) $, we have

$ \displaystyle \frac{\partial}{\partial t} \int_{a(t)}^{b(t)} f(x, t) dx = \int_{a(t)}^{b(t)} \frac{\partial f}{\partial t} dx + f(b(t), t) \frac{\partial b}{\partial t} - f(a(t), t) \frac{\partial a}{\partial t} $.

The neat thing is, when the bounds $ a(t) $ and $ b(t) $ are constant, the last two terms go away! So we basically just take the derivative of the function inside the integral. Anyway, so how does this apply to our problem? Well, our function seems to be univariate at the moment, but since we failed to solve it in its current form, let's complicate things. Suppose

$ f(x, t) = \frac{\ln{(tx+1)}}{x^2+1} $ and let $ \displaystyle I(t) = \int_0^1 f(x, t) dx $.

We want to evaluate $ I(1) $. Applying the Leibniz Integral Rule, we obtain

$ \displaystyle I^{\prime}(t) = \frac{\partial}{\partial t} \int_0^1 f(x, t) dx = \int_0^1 \frac{\partial f}{\partial t} dx $

$ \displaystyle I^{\prime}(t) = \int_0^1 \frac{x}{(tx+1)(x^2+1)} dx $.

Using partial fractions, this becomes

$ \displaystyle I^{\prime}(t) = \int_0^1 \left(-\frac{t}{t^2+1} \cdot \frac{1}{tx+1}+\frac{1}{t^2+1} \cdot \frac{x}{x^2+1}+\frac{t}{t^2+1} \cdot \frac{1}{x^2+1} \right) dx = \left[ -\frac{\ln{(tx+1)}}{t^2+1}+\frac{\ln{(x^2+1)}}{2(t^2+1)}+\frac{t}{t^2+1} \cdot \arctan{x} \right]_0^1 $

$ \displaystyle I^{\prime}(t) = -\frac{\ln{(t+1)}}{t^2+1}+\frac{\ln{2}}{2(t^2+1)}+\frac{\pi}{4} \cdot \frac{t}{t^2+1} $.

So it remains to recover $ I $ through solving the differential equation

$ \displaystyle I^{\prime}(t) = -\frac{\ln{(t+1)}}{t^2+1}+\frac{\ln{2}}{2(t^2+1)}+\frac{\pi}{4} \cdot \frac{t}{t^2+1} $.

Integrating both sides, we get

$ \displaystyle I(t) = \int_0^t \left(-\frac{\ln{(t+1)}}{t^2+1}+\frac{\ln{2}}{2(t^2+1)}+\frac{\pi}{4} \cdot \frac{t}{t^2+1}\right) dt = -\int_0^t \frac{\ln{(t+1)}}{t^2+1} dt + \frac{\ln{2}}{2}\arctan{t} + \frac{\pi}{8} \ln{(t^2+1)} $

$ \displaystyle I(1) = -\int_0^1 \frac{\ln{(t+1)}}{t^2+1} dt + \frac{\pi}{4} \ln{2} $.

But wait, recall that $ \displaystyle I(1) = \int_0^1 \frac{\ln{(x+1)}}{x^2+1} dx $, so in fact the previous equation yields

$ \displaystyle I(1) = -I(1) + \frac{\pi}{4} \ln{2} \Rightarrow I(1) = \frac{\pi}{8} \ln{2} $. QED.

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

Comment: This probably wasn't the cleanest solution to this integral. Other solutions involved the substitutions $ x = \tan{\theta} $, $ x = \frac{1-u}{1+u} $, as well as some crazy series expansion. This technique seems to be well-known though, associated with the famous physicist Richard Feynman as one of his favorite tricks. It can be very helpful in evaluating otherwise difficult to approach integrals.

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

Practice Problem: Evaluate $ \displaystyle \int_0^1 \frac{x-1}{\ln{x}} dx $.