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.
Tuesday, January 30, 2007
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 $.
$ \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).
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 $.
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.
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 $?
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?
$ \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 $.
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.
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.
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?
$ \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?
$ \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 $.
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 $.
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 $.
Subscribe to:
Posts (Atom)