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.
Saturday, April 28, 2007
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!
--------------------
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} $.
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 $.
$ 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?
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?
Tuesday, April 3, 2007
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 $.
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 $.
Subscribe to:
Posts (Atom)