Problem: (2000 IMO - #2) Let $a, b, c$ be positive real numbers so that $abc=1$. Prove that
$\left( a-1+\frac 1b \right) \left( b-1+\frac 1c \right) \left( c-1+\frac 1a \right) \leq 1$.
Solution: The standard trick to solve the condition $ abc = 1 $ is to substitute
$ a = \frac{x}{y}$, $ b = \frac{y}{z}$, $ c = \frac{z}{x} $
for positive reals $ x, y, z $ (their existence is guaranteed since it's a three-variable system with three equations).
Our inequality reduces to
$ \left(\frac{x+z-y}{y}\right)\left(\frac{y+x-z}{z}\right)\left(\frac{z+y-x}{x}\right) \le 1 $.
Multiplying through by $ xyz $, expanding, and rearranging everything to the RHS, we have
$ 0 \le x^3+y^3+z^3-x^2y-x^2z-y^2z-y^2x-z^2x-z^2y+3xyz $
or
$ 0 \le x(x-y)(x-z)+y(y-z)(y-x)+z(z-x)(z-y) $,
which is just Schur's Inequality, so the result is proved. QED.
--------------------
Comment: The condition $ abc = 1 $ almost always calls for the substitution above. It also works with $ abc \ge 1 $ in which case you simply have another variable multiplied by each of the terms.
--------------------
Practice Problem: Go take the 2006 Mock AIME 5 below.
Monday, February 27, 2006
Sunday, February 26, 2006
Legend of Max. Topic: Inequalities. Level: Olympiad.
Problem: (1999 USAMO - #4) Let $a_{1}, a_{2}, \ldots, a_{n}$ ($n > 3$) be real numbers such that
$a_{1} + a_{2} + \cdots + a_{n} \geq n \qquad$ and $\qquad a_{1}^{2} + a_{2}^{2} + \cdots + a_{n}^{2} \geq n^{2}$.
Prove that $\max(a_{1}, a_{2}, \ldots, a_{n}) \geq 2$.
Solution: To simply things, let $ x_i = 2-a_i $. We wish to show that there exists an $ x_i \le 0 $.
Our conditions become
$ (2-x_1)+(2-x_2)+\cdots+(2-x_n) \ge n \Rightarrow x_1+x_2+\cdots+x_n \le n $.
$ (2-x_1)^2+(2-x_2^2)+\cdots+(2-x_n)^2 \ge n^2 $.
Assume for the sake of contradiction that $ x_i > 0 $ for all $ i $ and let $ x_1+x_2+\cdots+x_n = k \le n $. We have
$ (2-x_1)^2+(2-x_2)^2+\cdots+(2-x_n^2) = (x_1^2+x_2^2+\cdots+x_n^2) - 4(x_1+x_2+\cdots+x_n)+4n \ge n^2 $, or
$ (x_1^2+x_2^2+\cdots+x_n^2) - 4(x_1+x_2+\cdots+x_n) \ge n^2-4n $.
But we have $ x_1^2+x_2^2+\cdots+x_n^2 < (x_1+x_2+\cdots+x_n)^2 = k^2 $, so
$ (x_1^2+x_2^2+\cdots+x_n^2) - 4(x_1+x_2+\cdots+x_n) < k^2-4k $.
However, since $ n \ge k $ and $ n \ge 4 $, we have $ n^2-4n \ge k^2-4k $ (looking at the parabola it is easy to see; $ x^2-4x $ has zeros at $ x = 0, 4 $). Therefore
$ (x_1^2+x_2^2+\cdots+x_n^2) - 4(x_1+x_2+\cdots+x_n) < k^2-4k \le n^2-4n $.
But we also had
$ (x_1^2+x_2^2+\cdots+x_n^2) - 4(x_1+x_2+\cdots+x_n) \ge n^2-4n $,
so that gives us a contradiction. Hence our assumption must be false and there exists an $ x_i \le 0 \Rightarrow a_i \ge 2 $ as desired. QED.
--------------------
Comment: This wasn't a particularly difficult inequality, but it has some key ideas. Using all parts of the question is important (in this case $ n > 3 $ is actually relevant). Another note is that this didn't really require any of the classical inequalities, just algebraic manipulation. Lastly, the crucial step was setting converting the real $ a_i $ to positive $ x_i $ which makes things a whole lot nicer.
--------------------
Practice Problem: Go take the 2006 Mock AIME 5 below.
$a_{1} + a_{2} + \cdots + a_{n} \geq n \qquad$ and $\qquad a_{1}^{2} + a_{2}^{2} + \cdots + a_{n}^{2} \geq n^{2}$.
Prove that $\max(a_{1}, a_{2}, \ldots, a_{n}) \geq 2$.
Solution: To simply things, let $ x_i = 2-a_i $. We wish to show that there exists an $ x_i \le 0 $.
Our conditions become
$ (2-x_1)+(2-x_2)+\cdots+(2-x_n) \ge n \Rightarrow x_1+x_2+\cdots+x_n \le n $.
$ (2-x_1)^2+(2-x_2^2)+\cdots+(2-x_n)^2 \ge n^2 $.
Assume for the sake of contradiction that $ x_i > 0 $ for all $ i $ and let $ x_1+x_2+\cdots+x_n = k \le n $. We have
$ (2-x_1)^2+(2-x_2)^2+\cdots+(2-x_n^2) = (x_1^2+x_2^2+\cdots+x_n^2) - 4(x_1+x_2+\cdots+x_n)+4n \ge n^2 $, or
$ (x_1^2+x_2^2+\cdots+x_n^2) - 4(x_1+x_2+\cdots+x_n) \ge n^2-4n $.
But we have $ x_1^2+x_2^2+\cdots+x_n^2 < (x_1+x_2+\cdots+x_n)^2 = k^2 $, so
$ (x_1^2+x_2^2+\cdots+x_n^2) - 4(x_1+x_2+\cdots+x_n) < k^2-4k $.
However, since $ n \ge k $ and $ n \ge 4 $, we have $ n^2-4n \ge k^2-4k $ (looking at the parabola it is easy to see; $ x^2-4x $ has zeros at $ x = 0, 4 $). Therefore
$ (x_1^2+x_2^2+\cdots+x_n^2) - 4(x_1+x_2+\cdots+x_n) < k^2-4k \le n^2-4n $.
But we also had
$ (x_1^2+x_2^2+\cdots+x_n^2) - 4(x_1+x_2+\cdots+x_n) \ge n^2-4n $,
so that gives us a contradiction. Hence our assumption must be false and there exists an $ x_i \le 0 \Rightarrow a_i \ge 2 $ as desired. QED.
--------------------
Comment: This wasn't a particularly difficult inequality, but it has some key ideas. Using all parts of the question is important (in this case $ n > 3 $ is actually relevant). Another note is that this didn't really require any of the classical inequalities, just algebraic manipulation. Lastly, the crucial step was setting converting the real $ a_i $ to positive $ x_i $ which makes things a whole lot nicer.
--------------------
Practice Problem: Go take the 2006 Mock AIME 5 below.
2006 Mock AIME 5.
Here's the 2006 Mock AIME 5, prepared by me.
Rules are the same as usual, go to AoPS if you want to discuss the problems. 3 hours, no calculators, all answers are integers from 000-999, inclusive. Have fun!
2006 Mock AIME 5
Rules are the same as usual, go to AoPS if you want to discuss the problems. 3 hours, no calculators, all answers are integers from 000-999, inclusive. Have fun!
2006 Mock AIME 5
Linkage. Topic: NT/Sequences and Series. Level: Olympiad.
Problem: (2002 USAMO - #5) Let $a,b$ be integers greater than $2$. Prove that there exists a positive integer $k$ and a finite sequence $n_1, n_2, \ldots, n_k$ of positive integers such that $n_1 = a, n_k = b$, and $n_i n_{i+1}$ is divisible by $n_i + n_{i+1}$ for each $i$ ($1 \leq i < k$).
Solution: Call two integers $a$ and $b$ "linked" if there exists a sequence as described in the question (note that two integers are always mutually linked; just reverse the sequence). We wish to show that all integers $a,b > 2$ are linked. If we can show that $m$ and $m+1$ are linked for any integer $m > 2$ in a finite number of terms (links), the problem is solved. Consider the following sequence:
$m$, $m(m-1)$, $m(m-1)(m-2)$, $2m(m-1)$, $2m(m+1)$, $m(m+1)(m-1)$, $m(m+1)$, $m+1$,
which can easily be shown to satisfy the property in the question. Thus $m$ and $m+1$ are always linked for $m > 2$. Hence, by induction, any integers $a, b > 2$ are linked (assuming WLOG $a
--------------------
Comment: The proof of this, when presented, is very short. In actuality, this problem took quite a while to solve; first to figure out to try and link consecutive integers and then to actually find the link. Playing around with the numbers eventually gave the right sequence.
Solution: Call two integers $a$ and $b$ "linked" if there exists a sequence as described in the question (note that two integers are always mutually linked; just reverse the sequence). We wish to show that all integers $a,b > 2$ are linked. If we can show that $m$ and $m+1$ are linked for any integer $m > 2$ in a finite number of terms (links), the problem is solved. Consider the following sequence:
$m$, $m(m-1)$, $m(m-1)(m-2)$, $2m(m-1)$, $2m(m+1)$, $m(m+1)(m-1)$, $m(m+1)$, $m+1$,
which can easily be shown to satisfy the property in the question. Thus $m$ and $m+1$ are always linked for $m > 2$. Hence, by induction, any integers $a, b > 2$ are linked (assuming WLOG $a
--------------------
Comment: The proof of this, when presented, is very short. In actuality, this problem took quite a while to solve; first to figure out to try and link consecutive integers and then to actually find the link. Playing around with the numbers eventually gave the right sequence.
Saturday, February 25, 2006
Power Hungry. Topic: NT/Sequences and Series. Level: Olympiad.
Problem: (2005 IMO - #4) Determine all positive integers relatively prime to all the terms of the infinite sequence
$ a_n=2^n+3^n+6^n -1,\ n\geq 1 $.
Solution: We claim that the only such integer is $ 1 $. Consider any prime $ p > 3 $ and the term $ a_{p-2} $. We have
$ a_{p-2} = 2^{p-2}+3^{p-2}+6^{p-2}-1 = \frac{2^{p-1}}{2}+\frac{3^{p-1}}{3}+\frac{6^{p-1}}{6}-1 $,
which, by taking a common denominator and factoring, becomes
$ a_{p-2} = \frac{(2^{p-1}+2)(3^{p-1}+3)-12}{6} $.
But by Fermat's Little Theorem, we have $ 2^{p-1} \equiv 3^{p-1} \equiv 1 \pmod{p} $, so
$ a_{p-2} \equiv \frac{(1+2)(1+3)-12}{6} \equiv 0 \pmod{p} $.
So we have shown that $ p|a_{p-2} $ for all primes $ p > 3 $. Noting that $ a_2 = 48 $, which is divisible by both $ 2 $ and $ 3 $, we have that every positive integer divisible by a prime is not relatively prime to all terms in the sequence (since at least one term is divisible by every prime). Hence the only possible number is $ 1 $, as claimed. QED.
--------------------
Comment: The quickest way to find this solution was seeing that $ \frac{1}{2}+\frac{1}{3}+\frac{1}{6}-1 = 0 $. And since multiplicative inverses always exist modulo a prime, the term $ a_{p-2} $ is divisible by $ p $.
$ a_n=2^n+3^n+6^n -1,\ n\geq 1 $.
Solution: We claim that the only such integer is $ 1 $. Consider any prime $ p > 3 $ and the term $ a_{p-2} $. We have
$ a_{p-2} = 2^{p-2}+3^{p-2}+6^{p-2}-1 = \frac{2^{p-1}}{2}+\frac{3^{p-1}}{3}+\frac{6^{p-1}}{6}-1 $,
which, by taking a common denominator and factoring, becomes
$ a_{p-2} = \frac{(2^{p-1}+2)(3^{p-1}+3)-12}{6} $.
But by Fermat's Little Theorem, we have $ 2^{p-1} \equiv 3^{p-1} \equiv 1 \pmod{p} $, so
$ a_{p-2} \equiv \frac{(1+2)(1+3)-12}{6} \equiv 0 \pmod{p} $.
So we have shown that $ p|a_{p-2} $ for all primes $ p > 3 $. Noting that $ a_2 = 48 $, which is divisible by both $ 2 $ and $ 3 $, we have that every positive integer divisible by a prime is not relatively prime to all terms in the sequence (since at least one term is divisible by every prime). Hence the only possible number is $ 1 $, as claimed. QED.
--------------------
Comment: The quickest way to find this solution was seeing that $ \frac{1}{2}+\frac{1}{3}+\frac{1}{6}-1 = 0 $. And since multiplicative inverses always exist modulo a prime, the term $ a_{p-2} $ is divisible by $ p $.
Thursday, February 23, 2006
Pair Of Products From P. Topic: Geometry. Level: Olympiad.
Problem: (2000 MOP Rookie Contest, Gabriel Carroll Original) Let $ABCD$ be a square of side $1$ and $P$ be a point in the plane. Prove that $PA \cdot PB + PC \cdot PD \ge 1$.
Solution: First we want to settle the case in which $ P $ is either on the opposite side of $ AB $ as $ CD $ is or vice versa. By symmetry, we can just show it for one side. WLOG, assume $ P $ is on the opposite side of $ AB $ as $ CD $ is (or $ P $ is to the "left" of $ AB $ in the diagram).
But then $ PC \ge BC = 1 $ and $ PD \ge AD = 1 $ so $ PC \cdot PD \ge 1 $ and the inequality clearly holds.
So now we move on to the case in which $ AB $ and $ CD $ are on opposite sides of $ P $, as shown in the diagram. Let $ E $ and $ F $ be the feet of the perpendiculars from $ P $ to $ BC $ and $ AD $, respectively.
We have
$ PA \cdot PB \ge PA \cdot PB \sin{\angle APB} = 2[APB] = [BEFA] $
and
$ PC \cdot PD \ge PC \cdot PD \sin{\angle CPD} = 2[CPD] = [CEFD] $,
both from the fact that half of the product of two sides in a triangle and the sine of the angle between them gives the area. Hence $ PA \cdot PB + PC \cdot PD \ge [BEFA]+[CEFD] = [ABCD] = 1 $ as desired. QED.
--------------------
Comment: Using coordinate geometry was pretty tempting in this problem, especially since it turns the problem into an algebraic inequality which are usually easier, but this proof is actually much nicer. Also, knowing all the ways to find the area of a triangle is extremely useful in geometry problems because it gives you much more flexibility in rewriting expressions.
--------------------
Practice Problem #1: Generalize the problem for a square of side $ k $.
Practice Problem #2: Find and prove $ 5 $ different formulas for the area of a triangle (yes, there are definitely that many).
Solution: First we want to settle the case in which $ P $ is either on the opposite side of $ AB $ as $ CD $ is or vice versa. By symmetry, we can just show it for one side. WLOG, assume $ P $ is on the opposite side of $ AB $ as $ CD $ is (or $ P $ is to the "left" of $ AB $ in the diagram).
But then $ PC \ge BC = 1 $ and $ PD \ge AD = 1 $ so $ PC \cdot PD \ge 1 $ and the inequality clearly holds.
So now we move on to the case in which $ AB $ and $ CD $ are on opposite sides of $ P $, as shown in the diagram. Let $ E $ and $ F $ be the feet of the perpendiculars from $ P $ to $ BC $ and $ AD $, respectively.
We have
$ PA \cdot PB \ge PA \cdot PB \sin{\angle APB} = 2[APB] = [BEFA] $
and
$ PC \cdot PD \ge PC \cdot PD \sin{\angle CPD} = 2[CPD] = [CEFD] $,
both from the fact that half of the product of two sides in a triangle and the sine of the angle between them gives the area. Hence $ PA \cdot PB + PC \cdot PD \ge [BEFA]+[CEFD] = [ABCD] = 1 $ as desired. QED.
--------------------
Comment: Using coordinate geometry was pretty tempting in this problem, especially since it turns the problem into an algebraic inequality which are usually easier, but this proof is actually much nicer. Also, knowing all the ways to find the area of a triangle is extremely useful in geometry problems because it gives you much more flexibility in rewriting expressions.
--------------------
Practice Problem #1: Generalize the problem for a square of side $ k $.
Practice Problem #2: Find and prove $ 5 $ different formulas for the area of a triangle (yes, there are definitely that many).
Wednesday, February 22, 2006
Divisibility. Topic: Number Theory. Level: Olympiad.
Problem: (Gabriel Carroll Original) Find all positive integers $ a,b,c $ such that $ a|(bc+1) $, $ b|(ca+1) $, $ c|(ab+1) $.
Solution: We first claim that they must all be pairwise relatively prime. Assume the opposite, that $ gcd(a,b) = k \neq 1 $. But then $ bc+1 $ is not divisible by $ k $ so $ a $ cannot divide it. Contradiction. So $ a,b,c $ are pairwise relatively prime.
Multiply the divisibilities together. We then have
$ abc|(ab+1)(bc+1)(ca+1) \Rightarrow abc|[(abc)^2+(a+b+c)(abc)+ab+bc+ca+1] \Rightarrow abc|(ab+bc+ca+1) $.
Suppose $ min(a,b,c) \ge 3 $. Then we clearly have $ a,b,c $ distinct (or they wouldn't be relatively prime), so assume WLOG that $ 3 \le a < b < c $.
Then $ abc \ge 3bc = bc+bc+bc \ge (ab+1)+bc+(ca+1) > ab+bc+ca+1 $. But if $ abc|(ab+bc+ca+1) $, we have $ abc \le ab+bc+ca+1 $. Contradiction. So $ min(a,b,c) < 3 $.
Then we check $ a = 1, 2 $. Again, we assume WLOG that $ a \le b \le c $.
$ a = 1 $: We have $ b|(c+1) $ and $ c|(b+1) $ so $ b \le c+1 $, $ c \le b+1 $. Then since $ b \le c $, we have $ b = c $ or $ b+1 = c $. If $ b = c $, we have $ b|(b+1) \Rightarrow b|1 \Rightarrow b = 1 $. If $ b+1 = c $, we have $ b|(b+2) \Rightarrow b|2 \Rightarrow b = 1, 2 $. This gives us $ (b,c) = (1,1); (1,2); (2,3) $.
$ a = 2 $: We have $ b|(2c+1) $ and $ c|(2b+1) $. Note that $ 2b+1 $ cannot have any divisors between $ b $ and itself. This is true because other than itself its next largest possible divisor is $ \frac{2b+1}{2} $ and the other ones are all less than $ b $. But since $ \frac{2b+1}{2} $ is never an integer, this is impossible. Therefore, since $ b \le c $, we have $ c = 2b+1 $. This gives us $ b|(4b+3) \Rightarrow b|3 \Rightarrow b = 3 $, so $ (b,c) = (3,7) $ is a solution.
Hence our solutions are $ (a,b,c) = (1,1,1); (1,1,2); (1,2,3); (2,3,7) $ and all permutations of them. QED.
--------------------
Comment: This problem required some messy casework and bounding, and it's really easy to miss solutions (especially the last one). Thorough and rigorous arguments must be maintained to find them all.
Solution: We first claim that they must all be pairwise relatively prime. Assume the opposite, that $ gcd(a,b) = k \neq 1 $. But then $ bc+1 $ is not divisible by $ k $ so $ a $ cannot divide it. Contradiction. So $ a,b,c $ are pairwise relatively prime.
Multiply the divisibilities together. We then have
$ abc|(ab+1)(bc+1)(ca+1) \Rightarrow abc|[(abc)^2+(a+b+c)(abc)+ab+bc+ca+1] \Rightarrow abc|(ab+bc+ca+1) $.
Suppose $ min(a,b,c) \ge 3 $. Then we clearly have $ a,b,c $ distinct (or they wouldn't be relatively prime), so assume WLOG that $ 3 \le a < b < c $.
Then $ abc \ge 3bc = bc+bc+bc \ge (ab+1)+bc+(ca+1) > ab+bc+ca+1 $. But if $ abc|(ab+bc+ca+1) $, we have $ abc \le ab+bc+ca+1 $. Contradiction. So $ min(a,b,c) < 3 $.
Then we check $ a = 1, 2 $. Again, we assume WLOG that $ a \le b \le c $.
$ a = 1 $: We have $ b|(c+1) $ and $ c|(b+1) $ so $ b \le c+1 $, $ c \le b+1 $. Then since $ b \le c $, we have $ b = c $ or $ b+1 = c $. If $ b = c $, we have $ b|(b+1) \Rightarrow b|1 \Rightarrow b = 1 $. If $ b+1 = c $, we have $ b|(b+2) \Rightarrow b|2 \Rightarrow b = 1, 2 $. This gives us $ (b,c) = (1,1); (1,2); (2,3) $.
$ a = 2 $: We have $ b|(2c+1) $ and $ c|(2b+1) $. Note that $ 2b+1 $ cannot have any divisors between $ b $ and itself. This is true because other than itself its next largest possible divisor is $ \frac{2b+1}{2} $ and the other ones are all less than $ b $. But since $ \frac{2b+1}{2} $ is never an integer, this is impossible. Therefore, since $ b \le c $, we have $ c = 2b+1 $. This gives us $ b|(4b+3) \Rightarrow b|3 \Rightarrow b = 3 $, so $ (b,c) = (3,7) $ is a solution.
Hence our solutions are $ (a,b,c) = (1,1,1); (1,1,2); (1,2,3); (2,3,7) $ and all permutations of them. QED.
--------------------
Comment: This problem required some messy casework and bounding, and it's really easy to miss solutions (especially the last one). Thorough and rigorous arguments must be maintained to find them all.
Tuesday, February 21, 2006
Big ol' GCD. Topic: NT/Pigeonhole Principle. Level: Olympiad.
Problem: (2002 USAMO - Proposed, Gabriel Carroll Original) Let $n$ be an integer greater than $1$. Suppose that $n$ distinct positive integers are given, all less than $n^2$. Prove that there exist some two of them whose greatest common divisor is less than $n$.
Solution: We will use some interesting facts about divisors. Firstly, $ gcd(a,b) | (a-b) $ (the greatest common divisor divides the difference). This is pretty obvious because $ gcd(a,b)|a $ and $ gcd(a,b)|b $. And secondly, if $ a|b $ then $ a \le b $ which is quite obvious too, since we have $ b = ka $ with $ k \ge 1 $.
Suppose one of the numbers, $ m $, is less than $ n $. Let $ p $ be any of the other numbers. Then $ gcd(m,p)|m \Rightarrow gcd(m,p) \le m < n $ and we are done. So assume all the numbers are at least $ n $.
Partition the interval $ [n, n^2-1] $ into sets of $ n $ consecutive integers. We get
$ [n, 2n-1] $, $ [2n, 3n-1] $, $\ldots$, $ [n^2-n, n^2-1] $.
It's easy to see there are $ n-1 $ sets (the first begins with $ 1 \cdot n $ and the last with $ (n-1) \cdot n $). Then by Pigeonhole, we know two of our original $ n $ integers fall into one interval. Let these be $ q,r $.
We have $ q-r < n $, so $ gcd(q,r)|(q-r) \Rightarrow gcd(q,r) \le q-r < n $. Hence there exists two of the integers whose greatest common divisor is less than $ n $. QED.
--------------------
Comment: This is a pretty interesting problem, combining basic number theory with a nice application of the Pigeonhole Principle. The key step is noticing that if two numbers lie in an interval of $ n $ consecutive integers then their greatest common divisor is less than $ n $. Then we have to eliminate the smallest interval $ [1, n-1] $ so we could have just $ n-1 $ intervals and apply Pigeonhole.
--------------------
Practice Problem: Find all integer values $ a,b,c $ such that the equation $ ax+by = c $ has a solution $ (x,y) $ in the integers.
Solution: We will use some interesting facts about divisors. Firstly, $ gcd(a,b) | (a-b) $ (the greatest common divisor divides the difference). This is pretty obvious because $ gcd(a,b)|a $ and $ gcd(a,b)|b $. And secondly, if $ a|b $ then $ a \le b $ which is quite obvious too, since we have $ b = ka $ with $ k \ge 1 $.
Suppose one of the numbers, $ m $, is less than $ n $. Let $ p $ be any of the other numbers. Then $ gcd(m,p)|m \Rightarrow gcd(m,p) \le m < n $ and we are done. So assume all the numbers are at least $ n $.
Partition the interval $ [n, n^2-1] $ into sets of $ n $ consecutive integers. We get
$ [n, 2n-1] $, $ [2n, 3n-1] $, $\ldots$, $ [n^2-n, n^2-1] $.
It's easy to see there are $ n-1 $ sets (the first begins with $ 1 \cdot n $ and the last with $ (n-1) \cdot n $). Then by Pigeonhole, we know two of our original $ n $ integers fall into one interval. Let these be $ q,r $.
We have $ q-r < n $, so $ gcd(q,r)|(q-r) \Rightarrow gcd(q,r) \le q-r < n $. Hence there exists two of the integers whose greatest common divisor is less than $ n $. QED.
--------------------
Comment: This is a pretty interesting problem, combining basic number theory with a nice application of the Pigeonhole Principle. The key step is noticing that if two numbers lie in an interval of $ n $ consecutive integers then their greatest common divisor is less than $ n $. Then we have to eliminate the smallest interval $ [1, n-1] $ so we could have just $ n-1 $ intervals and apply Pigeonhole.
--------------------
Practice Problem: Find all integer values $ a,b,c $ such that the equation $ ax+by = c $ has a solution $ (x,y) $ in the integers.
Doors, Doors, and Mores! Topic: Invariants. Level: AIME/Olympiad.
Problem: (2000-2001 Berkeley Math Circle Contest, Gabriel Carroll Original) A company wants to construct its new office building, a $2001 \times 2001$ square grid of rooms, with doors connecting pairs of adjacent rooms, so that each room has exactly two doors. Prove that this cannot be done.
Solution: Place the lower left corner at the origin. Label each room by its lower-left corner. Number the rooms in the following way - if the sum of its label ($ (x,y) \rightarrow x+y $) is even, it is $ 0 $ and if the sum of its label is odd, it is $ 1 $. We note that each door connects two rooms of opposite numbers.
Since each room has two doors, we have a total of $ 2 \cdot 2001^2 $ doors, but this counts each door twice - once from each side. So we divide by two to just get $ 2001^2 $ doors, which is odd.
The number of doors in all the rooms is also equal to the number of doors in rooms with value $ 1 $ (since each door in a $ 0 $ room will be counted by the $ 1 $ room on the other side). But if each room has exactly two doors, the total number must be even, which cannot equal the odd sum above. Contradiction.
So it is impossible to have exactly two doors in every room. QED.
--------------------
Comment: Once again, we see that the right numbering works wonders. Parity is usually a good thing to watch out for in invariant problems ("cannot be done" is a good clue).
Solution: Place the lower left corner at the origin. Label each room by its lower-left corner. Number the rooms in the following way - if the sum of its label ($ (x,y) \rightarrow x+y $) is even, it is $ 0 $ and if the sum of its label is odd, it is $ 1 $. We note that each door connects two rooms of opposite numbers.
Since each room has two doors, we have a total of $ 2 \cdot 2001^2 $ doors, but this counts each door twice - once from each side. So we divide by two to just get $ 2001^2 $ doors, which is odd.
The number of doors in all the rooms is also equal to the number of doors in rooms with value $ 1 $ (since each door in a $ 0 $ room will be counted by the $ 1 $ room on the other side). But if each room has exactly two doors, the total number must be even, which cannot equal the odd sum above. Contradiction.
So it is impossible to have exactly two doors in every room. QED.
--------------------
Comment: Once again, we see that the right numbering works wonders. Parity is usually a good thing to watch out for in invariant problems ("cannot be done" is a good clue).
Zzz... Topic: Complex Numbers/Trigonometry. Level: AIME/Olympiad.
Problem: (1999-2000 Berkeley Math Circle Contest, Gabriel Carroll Original) Let $ z = \cos{\frac{2\pi}{n}}+i \sin{\frac{2\pi}{n}} $ where $ n $ is a positive integer. Prove that
$ \frac{1}{1+z}+\frac{1}{1+z^2}+\cdots+\frac{1}{1+z^n} = \frac{n}{2} $.
Solution: It should be clear that $ z $ is one of the $ n $th roots of unity. Then by DeMoivre's, we find that $ z, z^2, \ldots, z^n $ are exactly the $ n $th roots of unity. So we may write $ z^k $ as $ \cos{\frac{2\pi k}{n}}+i \sin{\frac{2\pi k}{n}} $.
Consider the sum $ \frac{1}{1+z^k}+\frac{1}{1+z^{n-k}} $. We have
$ \frac{1}{\left(1+\cos{\frac{2\pi k}{n}}\right)+i \sin{\frac{2\pi k}{n}}} + \frac{1}{\left(1+\cos{\frac{2\pi (n-k)}{n}}\right)+i \sin{\frac{2\pi (n-k)}{n}}} $.
This is ugly, but by multiplying the denominators by their complex conjugates, it comes out to
$ \frac{\left(1+\cos{\frac{2\pi k}{n}}\right)-i \sin{\frac{2\pi k}{n}}}{2\left(1+\cos{\frac{2\pi k}{n}}\right)} + \frac{\left(1+\cos{\frac{2\pi (n-k)}{n}}\right)-i \sin{\frac{2\pi (n-k)}{n}}}{2\left(1+\cos{\frac{2\pi (n-k)}{n}}\right)} $.
Note that $ \cos{\frac{2\pi k}{n}} = \cos{\frac{2\pi (n-k)}{n}} $ and $ \sin{\frac{2\pi k}{n}} = -\sin{\frac{2\pi (n-k)}{n}} $, and it simplifies nicely to (after applying the Pythagorean identity)
$ \frac{2\left(1+\cos{\frac{2\pi k}{n}}\right)}{2\left(1+\cos{\frac{2\pi k}{n}}\right)} = 1 $.
Since $ n $ is odd, there are $ \frac{n-1}{2} $ pairs that sum to $ 1 $ and the only term left is $ \frac{1}{1+z^n} = \frac{1}{1+1} = \frac{1}{2} $, so the sum is $ \frac{n-1}{2}+\frac{1}{2} = \frac{n}{2} $ as desired. QED.
--------------------
Comment: This is quite a bit of algebra to work through; the way I first saw it was geometrically. The reciprocal of a complex number is equivalent to the complex conjugate divided by the norm, so clearly adding the reciprocals of complex conjugates will clear the imaginary part. Since we have the roots of unity, the complex conjugates are $ z^k $ and $ z^{n-k} $, giving the approach above.
--------------------
Practice Problem: (2004 AIME1 - #13) The polynomial $P(x)=(1+x+x^2+\cdots+x^{17})^2-x^{17}$ has $34$ complex roots of the form $z_k=r_k[\cos(2\pi a_k)+i\sin(2\pi a_k)]$, $k=1, 2, 3,\ldots, 34$, with $00$. Given that $a_1+a_2+a_3+a_4+a_5=m/n$, where $m$ and $n$ are relatively prime positive integers, find $m+n$.
$ \frac{1}{1+z}+\frac{1}{1+z^2}+\cdots+\frac{1}{1+z^n} = \frac{n}{2} $.
Solution: It should be clear that $ z $ is one of the $ n $th roots of unity. Then by DeMoivre's, we find that $ z, z^2, \ldots, z^n $ are exactly the $ n $th roots of unity. So we may write $ z^k $ as $ \cos{\frac{2\pi k}{n}}+i \sin{\frac{2\pi k}{n}} $.
Consider the sum $ \frac{1}{1+z^k}+\frac{1}{1+z^{n-k}} $. We have
$ \frac{1}{\left(1+\cos{\frac{2\pi k}{n}}\right)+i \sin{\frac{2\pi k}{n}}} + \frac{1}{\left(1+\cos{\frac{2\pi (n-k)}{n}}\right)+i \sin{\frac{2\pi (n-k)}{n}}} $.
This is ugly, but by multiplying the denominators by their complex conjugates, it comes out to
$ \frac{\left(1+\cos{\frac{2\pi k}{n}}\right)-i \sin{\frac{2\pi k}{n}}}{2\left(1+\cos{\frac{2\pi k}{n}}\right)} + \frac{\left(1+\cos{\frac{2\pi (n-k)}{n}}\right)-i \sin{\frac{2\pi (n-k)}{n}}}{2\left(1+\cos{\frac{2\pi (n-k)}{n}}\right)} $.
Note that $ \cos{\frac{2\pi k}{n}} = \cos{\frac{2\pi (n-k)}{n}} $ and $ \sin{\frac{2\pi k}{n}} = -\sin{\frac{2\pi (n-k)}{n}} $, and it simplifies nicely to (after applying the Pythagorean identity)
$ \frac{2\left(1+\cos{\frac{2\pi k}{n}}\right)}{2\left(1+\cos{\frac{2\pi k}{n}}\right)} = 1 $.
Since $ n $ is odd, there are $ \frac{n-1}{2} $ pairs that sum to $ 1 $ and the only term left is $ \frac{1}{1+z^n} = \frac{1}{1+1} = \frac{1}{2} $, so the sum is $ \frac{n-1}{2}+\frac{1}{2} = \frac{n}{2} $ as desired. QED.
--------------------
Comment: This is quite a bit of algebra to work through; the way I first saw it was geometrically. The reciprocal of a complex number is equivalent to the complex conjugate divided by the norm, so clearly adding the reciprocals of complex conjugates will clear the imaginary part. Since we have the roots of unity, the complex conjugates are $ z^k $ and $ z^{n-k} $, giving the approach above.
--------------------
Practice Problem: (2004 AIME1 - #13) The polynomial $P(x)=(1+x+x^2+\cdots+x^{17})^2-x^{17}$ has $34$ complex roots of the form $z_k=r_k[\cos(2\pi a_k)+i\sin(2\pi a_k)]$, $k=1, 2, 3,\ldots, 34$, with $0
Monday, February 20, 2006
Just One Stone. Topic: Invariants/NT. Level: Olympiad.
Problem: (1998 MOP Rookie Contest, Gabriel Carroll Original) Given a row of $n$ squares ($n > 1$) we place stones in some squares so that no square contains more than one stone. We define the following operation: First, for each square containing a stone (other than the rightmost square), we add a stone to the square to its right. Then, if any square contains $> 1$ stone, remove two stones from it and add a stone to the square on its right (if this square exists). Repeat this second step until each square has at most one stone.
Now, we start with initial configuration $C$ of stones and apply the operation repeatedly. After an odd number of iterations $C$ reappears. Show that $C$ contains at most one stone.
Solution: Consider assigning values to the squares such that any stone in the square has that value. Let the $ k $th square have value $ 2^k $. Now look at the stone farthest to the left. Call the position of this stone $ m $. It clearly never changes under the operation, and each iteration places a stone to the right of it. So take the sum of all the stones $ \pmod{2^{m+2}} $ and call it $ S $. Obviously any addition of stones beyond the $ m+1 $ spot does not affect $ S $ and the second part of the operation doesn't affect $ S $ either by virtue of our numbering (it's invariant under this part of the operation). So we find that $ S $ is affected only by addition of stones in the $ m+1 $ spot (since there are no spots before that are affected). But we said that every iteration a stone is placed in this spot and if there are an odd number of iterations, say $ 2p+1 $ of them, $ S $ increases by $ (2p+1)2^{m+1} = p \cdot 2^{m+2}+2^{m+1} \equiv 2^{m+1} \pmod{2^{m+2}} $ and we find that $ S $ changes. But clearly if we have the initial configuration $ S $ must be the same. That means the $ m+1 $ spot can't exist, or that there can only be one stone, in the $ n $ spot. QED.
--------------------
Comment: The key step in this problem is applying the numbering so that the sum is invariant under the second part of the operation. After this and using mods we basically don't have to worry about what happens with everything beyond the first stone.
--------------------
Practice Problem: (Olympiad Problem Solving Class) Six pieces are placed in the first quadrant in the six squares closest to the origin. Each turn, we may take one piece away and replace it with two pieces in the two squares directly to the right and above the square we took the piece away from. Prove that we can never remove all pieces from the original six squares. Is it possible with just pieces in the three closest squares with a finite number of moves? [Reworded]
Now, we start with initial configuration $C$ of stones and apply the operation repeatedly. After an odd number of iterations $C$ reappears. Show that $C$ contains at most one stone.
Solution: Consider assigning values to the squares such that any stone in the square has that value. Let the $ k $th square have value $ 2^k $. Now look at the stone farthest to the left. Call the position of this stone $ m $. It clearly never changes under the operation, and each iteration places a stone to the right of it. So take the sum of all the stones $ \pmod{2^{m+2}} $ and call it $ S $. Obviously any addition of stones beyond the $ m+1 $ spot does not affect $ S $ and the second part of the operation doesn't affect $ S $ either by virtue of our numbering (it's invariant under this part of the operation). So we find that $ S $ is affected only by addition of stones in the $ m+1 $ spot (since there are no spots before that are affected). But we said that every iteration a stone is placed in this spot and if there are an odd number of iterations, say $ 2p+1 $ of them, $ S $ increases by $ (2p+1)2^{m+1} = p \cdot 2^{m+2}+2^{m+1} \equiv 2^{m+1} \pmod{2^{m+2}} $ and we find that $ S $ changes. But clearly if we have the initial configuration $ S $ must be the same. That means the $ m+1 $ spot can't exist, or that there can only be one stone, in the $ n $ spot. QED.
--------------------
Comment: The key step in this problem is applying the numbering so that the sum is invariant under the second part of the operation. After this and using mods we basically don't have to worry about what happens with everything beyond the first stone.
--------------------
Practice Problem: (Olympiad Problem Solving Class) Six pieces are placed in the first quadrant in the six squares closest to the origin. Each turn, we may take one piece away and replace it with two pieces in the two squares directly to the right and above the square we took the piece away from. Prove that we can never remove all pieces from the original six squares. Is it possible with just pieces in the three closest squares with a finite number of moves? [Reworded]
Sunday, February 19, 2006
Sleeping. Topic: Pigeonhole Principle. Level: AIME/Olympiad.
Problem: (1986 USAMO - #4) 5 professors are attending a lecture. During the lecture, each of them falls asleep twice and between each pair of professors they are asleep at the same moment at least once. Prove that three of them are asleep at the same moment. [Reworded]
Solution: This is an interesting problem and a cool application of the Pigeonhole Principle.
All the "moments" are treated as the start of an interval.
For each professor, there are 2 falling asleep moments, making 10 total. Call this set of moments S. For each pair, there is a moment at which both are asleep, making 10 also. Call this set of moments T. If any two moments in T are the same, we are done. If not, then they are all different.
We can correspond each moment in T with a moment in S because at the beginning of any interval in which two professors are sleeping, one of them must have just fallen asleep. However, the first 2 moments in S have to come before or at the same time as the first moment in T (since two have to fall asleep before two can be sleeping at the same time). Then the remaining 9 moments in T have to correspond with the 8 other moments in S, which means (by Pigeonhole) that 2 moments in T must be the same. Contradiction.
Hence there must be some moment at which three professors are asleep. QED.
--------------------
Comment: The proof of this is not extremely difficult, but it requires some innovative thinking to discover.
--------------------
Practice Problem: (1989 USAMO - #2) The 20 members of a local tennis club have scheduled exactly 14 two-person games among themselves, with each member playing in at least one game. Prove that within this schedule there must be a set of 6 games with 12 distinct players.
Solution: This is an interesting problem and a cool application of the Pigeonhole Principle.
All the "moments" are treated as the start of an interval.
For each professor, there are 2 falling asleep moments, making 10 total. Call this set of moments S. For each pair, there is a moment at which both are asleep, making 10 also. Call this set of moments T. If any two moments in T are the same, we are done. If not, then they are all different.
We can correspond each moment in T with a moment in S because at the beginning of any interval in which two professors are sleeping, one of them must have just fallen asleep. However, the first 2 moments in S have to come before or at the same time as the first moment in T (since two have to fall asleep before two can be sleeping at the same time). Then the remaining 9 moments in T have to correspond with the 8 other moments in S, which means (by Pigeonhole) that 2 moments in T must be the same. Contradiction.
Hence there must be some moment at which three professors are asleep. QED.
--------------------
Comment: The proof of this is not extremely difficult, but it requires some innovative thinking to discover.
--------------------
Practice Problem: (1989 USAMO - #2) The 20 members of a local tennis club have scheduled exactly 14 two-person games among themselves, with each member playing in at least one game. Prove that within this schedule there must be a set of 6 games with 12 distinct players.
Saturday, February 18, 2006
Deriving the Quadratic Formula. Topic: Algebra. Level: AMC.
Problem: (Quadratic Formula) Given positive reals $ a,b,c $, find a formula in terms of $ a,b,c $ that gives the roots of the quadratic $ ax^2+bx+c = 0 $.
Solution: The formula is obviously very well-known, but the derivation is interesting and is an interesting use of a method called completing the square.
From $ ax^2+bx+c = 0 $ we first divide through by $ a $ to get a monic quadratic. This makes completing the square easier. So we have $ x^2+\frac{b}{a}x+\frac{c}{a} = 0 $.
As completing the square implies, we want to make a square. It is important that both the $ x^2 $ and $ x $ terms are in the square so we have only a constant remaining. We rewrite our quadratic as
$ \left(x+\frac{b}{2a}\right)^2+\left(\frac{c}{a}-\frac{b^2}{4a^2}\right) = 0 $, or
$ \left(x+\frac{b}{2a}\right)^2 = \frac{b^2-4ac}{4a^2} $.
From here we see the seemingly random terms of the quadratic formula appear. Square rooting both sides, we find
$ x+\frac{b}{2a} = \pm \frac{\sqrt{b^2-4ac}}{2a} $, and
$ x = \frac{-b \pm \sqrt{b^2-4ac}}{2a} $
as desired. QED.
--------------------
Comment: The solution is quite simple, and the only key step is completing the square, which pretty much finished it off.
--------------------
Practice Problem #1: Graph $ 3x^2+18x+5y^2+20y = 96 $.
Practice Problem #2: Solve $ x^2+2x = 4y+2 $ for positive integers $ x,y $.
Solution: The formula is obviously very well-known, but the derivation is interesting and is an interesting use of a method called completing the square.
From $ ax^2+bx+c = 0 $ we first divide through by $ a $ to get a monic quadratic. This makes completing the square easier. So we have $ x^2+\frac{b}{a}x+\frac{c}{a} = 0 $.
As completing the square implies, we want to make a square. It is important that both the $ x^2 $ and $ x $ terms are in the square so we have only a constant remaining. We rewrite our quadratic as
$ \left(x+\frac{b}{2a}\right)^2+\left(\frac{c}{a}-\frac{b^2}{4a^2}\right) = 0 $, or
$ \left(x+\frac{b}{2a}\right)^2 = \frac{b^2-4ac}{4a^2} $.
From here we see the seemingly random terms of the quadratic formula appear. Square rooting both sides, we find
$ x+\frac{b}{2a} = \pm \frac{\sqrt{b^2-4ac}}{2a} $, and
$ x = \frac{-b \pm \sqrt{b^2-4ac}}{2a} $
as desired. QED.
--------------------
Comment: The solution is quite simple, and the only key step is completing the square, which pretty much finished it off.
--------------------
Practice Problem #1: Graph $ 3x^2+18x+5y^2+20y = 96 $.
Practice Problem #2: Solve $ x^2+2x = 4y+2 $ for positive integers $ x,y $.
Thursday, February 16, 2006
Guess What? It's Parallel! Topic: Vector Geometry. Level: Olympiad.
Problem: (Arbelos - Volume 5, Chapter 4 Cover Problem) Let $ ABC $ be a triangle and let $ A^{\prime} $ be a point on the circumcircle of $ ABC $. Denote $ H $ the orthocenter of $ \triangle ABC $ and $ H^{\prime} $ the orthocenter of $ \triangle A^{\prime}BC $. Prove that $ AHH^{\prime}A^{\prime} $ is a parallelogram.
Solution: Let $ O $ be the circumcenter of the two triangles and set it to be the origin. Let $ A, A^{\prime}, B, C $ denote the vectors to each of the points, respectively. Note that $ |A| = |A^{\prime}| = |B| = |C| $.
We claim that $ H = A+B+C $ and $ H^{\prime} = A^{\prime}+B+C $ (as vectors).
To prove this we only need to show that $ H-A $ is perpendicular to $ B-C $, and by symmetry everything else follows.
Assume $ H = A+B+C $. Then $ H-A = B+C $. Consider the dot product $ (B+C) \cdot (B-C) = B \cdot B - C \cdot C = |B|^2-|C|^2 = 0 $. But the dot product of two vectors can be zero iff they are perpendicular, and the result follows.
Now back to the problem. Since $ AH $ and $ A^{\prime}H^{\prime} $ are both perpendicular to $ BC $, they are clearly parallel.
Consider writing $ AA^{\prime} $ as the vector $ A^{\prime}-A $ and $ HH^{\prime} $ as the vector $ H^{\prime}-H $, which by our claim above is equivalent to $ (A^{\prime}+B+C) - (A+B+C) = A^{\prime}-A $. Since $ AA^{\prime} $ and $ HH^{\prime} $ are the same vector, they are going in the same direction and thus parallel. Then $ AHH^{\prime}A^{\prime} $ is a parallelogram, as desired. QED.
--------------------
Comment: A very powerful use of vector geometry, as it simplifies the problem immensely, especially with the common formula for the orthocenter.
--------------------
Practice Problem: Let $ G $ be the centroid of $ \triangle ABC $ and $ G^{\prime} $ be the centroid of $ \triangle A^{\prime}BC $. Prove that $ GG^{\prime} $ is parallel to $ AA^{\prime} $.
Solution: Let $ O $ be the circumcenter of the two triangles and set it to be the origin. Let $ A, A^{\prime}, B, C $ denote the vectors to each of the points, respectively. Note that $ |A| = |A^{\prime}| = |B| = |C| $.
We claim that $ H = A+B+C $ and $ H^{\prime} = A^{\prime}+B+C $ (as vectors).
To prove this we only need to show that $ H-A $ is perpendicular to $ B-C $, and by symmetry everything else follows.
Assume $ H = A+B+C $. Then $ H-A = B+C $. Consider the dot product $ (B+C) \cdot (B-C) = B \cdot B - C \cdot C = |B|^2-|C|^2 = 0 $. But the dot product of two vectors can be zero iff they are perpendicular, and the result follows.
Now back to the problem. Since $ AH $ and $ A^{\prime}H^{\prime} $ are both perpendicular to $ BC $, they are clearly parallel.
Consider writing $ AA^{\prime} $ as the vector $ A^{\prime}-A $ and $ HH^{\prime} $ as the vector $ H^{\prime}-H $, which by our claim above is equivalent to $ (A^{\prime}+B+C) - (A+B+C) = A^{\prime}-A $. Since $ AA^{\prime} $ and $ HH^{\prime} $ are the same vector, they are going in the same direction and thus parallel. Then $ AHH^{\prime}A^{\prime} $ is a parallelogram, as desired. QED.
--------------------
Comment: A very powerful use of vector geometry, as it simplifies the problem immensely, especially with the common formula for the orthocenter.
--------------------
Practice Problem: Let $ G $ be the centroid of $ \triangle ABC $ and $ G^{\prime} $ be the centroid of $ \triangle A^{\prime}BC $. Prove that $ GG^{\prime} $ is parallel to $ AA^{\prime} $.
Tuesday, February 14, 2006
When In Doubt, Polynomialize! Topic: Generating Functions. Level: Olympiad.
Definition: A generating function is simply a polynomial (or a power series, since it is infinite) $ \displaystyle P(x) = a_0+a_1x+a_2x^2+\cdots = \sum_{i=0}^{\infty} a_ix^i $ whose coefficients give the sequence $ \displaystyle \{a_i\}_{i=0}^{\infty} $.
The following problem will describe an interesting use of generating functions.
--------------------
Problem: Given reals $ A $ and $ B $, find the closed form expression for a sequence satisfying the recurrence
$ a_{n+1} = Aa_n+Ba_{n-1} $
for $ n = 1,2,\ldots $ and $ a_0 = 1 $, $ a_1 = A $.
Solution: Generating functions are in general useful tools for solving recurrences. It can get a bit ugly, but if you work through the algebra right, it comes out nicely.
First off, let $ P(x) = a_0+a_1x+a_2x^2+\cdots $ be the generating function for the sequence.
Consider the following procedure:
Take the recurrence $ a_{i+1} = Aa_i+Ba_{i-1} $ and multiply it by $ x^i $. We now have $ a_{i+1}x^i = Aa_ix^i+Ba_{i-1}x^i $. Sum these from $ i = 1 $ to infinity to get
$ \displaystyle \sum_{i=1}^{\infty} a_{i+1}x^i = A\sum_{i=1}^{\infty} a_ix^i + B\sum_{i=1}^{\infty} a_{i-1}x^i $.
But notice that
$ \displaystyle \sum_{i=1}^{\infty} a_{i+1}x^i = \frac{P(x)-a_0}{x} $, $ \displaystyle A\sum_{i=1}^{\infty} a_ix^i = A(P(x)-a_0) $, and $ \displaystyle B\sum_{i=1}^{\infty} a_{i-1}x^i = BxP(x) $.
Thus we have
$ \frac{P(x)-a_0}{x} = A(P(x)-a_0)+BxP(x) $, or
$ P(x) = \frac{a_0}{1-Ax-Bx^2} $.
This looks pretty nice, but how do we find the coefficients? Let $ r $ and $ s $ be the reciprocals of the roots of the quadratic $ 1-Ax-Bx^2 = 0 $. We have $ r+s = A $ and $ rs = -B $ as well as $ 1-Ax-Bx^2 = (1-rx)(1-sx) $.
So $ P(x) = \frac{a_0}{(1-rx)(1-sx)} $. Now set $ a_0 = 1 $ to simplify things (note that the result can easily be extended to any $ a_0 $ but it's just more convenient this way). Using the partial fraction decomposition, we obtain
$ P(x) = \frac{1}{(1-rx)(1-sx)} = \frac{r}{(r-s)(1-rx)}-\frac{s}{(r-s)(1-sx)} = \frac{1}{r-s}\left(\frac{r}{1-rx}-\frac{s}{1-sx}\right) $.
Expanding using the sum of an infinite geometric series (ignore the restrictions on the ratio; it might diverge but as long as we don't actually evaluate $ P(x) $ for any $ x $ it's ok) to get
$ P(x) = \frac{1}{r-s}(r+r^2x+r^3x^2+\cdots)-\frac{1}{r-s}(s+s^2x+s^3x^2+\cdots) $, or
$ P(x) = \frac{1}{r-s}((r-s)+(r^2-s^2)x+(r^3-s^3)x^2+\cdots) = a_0+a_1x+a_2x^2+\cdots$
from which we can easily see that $ a_n = \frac{1}{r-s}(r^{n+1}-s^{n+1}) $. QED.
--------------------
Comment: This has some very nice results, including the famous Fibonacci Sequence, when $ A = B = 1 $. We have $ r,s $ the reciprocals of the roots of $ 1-x-x^2 = 0 $ which happen to be $ \frac{1+\sqrt{5}}{2} $ and $ \frac{1-\sqrt{5}}{2} $, giving the well-known closed form for that sequence.
--------------------
Practice Problem: Try your hand at the recurrence $ a_{n+1} = a_n+a_{n-1}+a_{n-2} $ with $ a_0 = a_1 = 1 $.
The following problem will describe an interesting use of generating functions.
--------------------
Problem: Given reals $ A $ and $ B $, find the closed form expression for a sequence satisfying the recurrence
$ a_{n+1} = Aa_n+Ba_{n-1} $
for $ n = 1,2,\ldots $ and $ a_0 = 1 $, $ a_1 = A $.
Solution: Generating functions are in general useful tools for solving recurrences. It can get a bit ugly, but if you work through the algebra right, it comes out nicely.
First off, let $ P(x) = a_0+a_1x+a_2x^2+\cdots $ be the generating function for the sequence.
Consider the following procedure:
Take the recurrence $ a_{i+1} = Aa_i+Ba_{i-1} $ and multiply it by $ x^i $. We now have $ a_{i+1}x^i = Aa_ix^i+Ba_{i-1}x^i $. Sum these from $ i = 1 $ to infinity to get
$ \displaystyle \sum_{i=1}^{\infty} a_{i+1}x^i = A\sum_{i=1}^{\infty} a_ix^i + B\sum_{i=1}^{\infty} a_{i-1}x^i $.
But notice that
$ \displaystyle \sum_{i=1}^{\infty} a_{i+1}x^i = \frac{P(x)-a_0}{x} $, $ \displaystyle A\sum_{i=1}^{\infty} a_ix^i = A(P(x)-a_0) $, and $ \displaystyle B\sum_{i=1}^{\infty} a_{i-1}x^i = BxP(x) $.
Thus we have
$ \frac{P(x)-a_0}{x} = A(P(x)-a_0)+BxP(x) $, or
$ P(x) = \frac{a_0}{1-Ax-Bx^2} $.
This looks pretty nice, but how do we find the coefficients? Let $ r $ and $ s $ be the reciprocals of the roots of the quadratic $ 1-Ax-Bx^2 = 0 $. We have $ r+s = A $ and $ rs = -B $ as well as $ 1-Ax-Bx^2 = (1-rx)(1-sx) $.
So $ P(x) = \frac{a_0}{(1-rx)(1-sx)} $. Now set $ a_0 = 1 $ to simplify things (note that the result can easily be extended to any $ a_0 $ but it's just more convenient this way). Using the partial fraction decomposition, we obtain
$ P(x) = \frac{1}{(1-rx)(1-sx)} = \frac{r}{(r-s)(1-rx)}-\frac{s}{(r-s)(1-sx)} = \frac{1}{r-s}\left(\frac{r}{1-rx}-\frac{s}{1-sx}\right) $.
Expanding using the sum of an infinite geometric series (ignore the restrictions on the ratio; it might diverge but as long as we don't actually evaluate $ P(x) $ for any $ x $ it's ok) to get
$ P(x) = \frac{1}{r-s}(r+r^2x+r^3x^2+\cdots)-\frac{1}{r-s}(s+s^2x+s^3x^2+\cdots) $, or
$ P(x) = \frac{1}{r-s}((r-s)+(r^2-s^2)x+(r^3-s^3)x^2+\cdots) = a_0+a_1x+a_2x^2+\cdots$
from which we can easily see that $ a_n = \frac{1}{r-s}(r^{n+1}-s^{n+1}) $. QED.
--------------------
Comment: This has some very nice results, including the famous Fibonacci Sequence, when $ A = B = 1 $. We have $ r,s $ the reciprocals of the roots of $ 1-x-x^2 = 0 $ which happen to be $ \frac{1+\sqrt{5}}{2} $ and $ \frac{1-\sqrt{5}}{2} $, giving the well-known closed form for that sequence.
--------------------
Practice Problem: Try your hand at the recurrence $ a_{n+1} = a_n+a_{n-1}+a_{n-2} $ with $ a_0 = a_1 = 1 $.
Monday, February 13, 2006
Function Substitution. Topic: Inequalities. Level: Olympiad.
Theorem: (Jensen's Inequality) Let $ f $ be a function that is convex on the interval $ I $. Given positive reals $ a_1, a_2, \ldots, a_n \in I $ and positive real weights $ w_1, w_2, \ldots, w_n $ such that $ w_1+w_2+\cdots+w_n = 1 $, we have
$ w_1f(a_1)+w_2f(a_2)+\cdots+w_nf(a_n) \ge f(w_1a_1+w_2a_2+\cdots+w_na_n) $.
If $ f $ is concave on $ I $, the inequality is reversed.
--------------------
Problem: (1998 IMO Shortlist - A3) Let $r_{1},r_{2},\ldots ,r_{n}$ be real numbers greater than or equal to $1$. Prove that
$\frac{1}{r_{1} + 1} + \frac{1}{r_{2} + 1} + \cdots +\frac{1}{r_{n}+1} \geq \frac{n}{ \sqrt[n]{r_{1}r_{2} \cdots r_{n}}+1}$.
Solution: The $ n $ functions on the LHS and the single function on the RHS gives us the idea of using Jensen's. However, we can't really get a geometric mean via Jensen's, so this approach doesn't look promising.
On the other hand, since we have $ r_i \ge 1 $, consider the substitution $ r_i = e^{a_i} $ for nonnegative reals $ a_1, a_2, \ldots, a_n $. We then have $ \sqrt[n]{r_1r_2 \cdots r_n} = e^{\frac{a_1+a_2+\cdots+a_n}{n}} $. Aha! We have converted the geometric mean to an arithmetic one, suggesting Jensen's.
Consider the function $ f(x) = \frac{1}{e^x+1} $. Since $ f^{\prime\prime}(x) = \frac{2xe^x}{(e^x+1)^2} \ge 0 $ for $ x \in [0, \infty) $, the function is convex and we may apply Jensen's on $ f $. Setting $ w_1 = w_2 = \cdots = w_n = \frac{1}{n} $, we have
$ \frac{1}{n}f(a_1)+\frac{1}{n}f(a_2)+\cdots+\frac{1}{n}f(a_n) \ge f\left(\frac{a_1+a_2+\cdots+a_n}{n}\right) $,
which is just
$ \frac{1}{r_1+1}+\frac{1}{r_2+1}+\cdots+\frac{1}{r_n+1} \ge \frac{n}{ \sqrt[n]{r_{1}r_{2} \cdots r_{n}}+1} $,
as desired. QED.
$ w_1f(a_1)+w_2f(a_2)+\cdots+w_nf(a_n) \ge f(w_1a_1+w_2a_2+\cdots+w_na_n) $.
If $ f $ is concave on $ I $, the inequality is reversed.
--------------------
Problem: (1998 IMO Shortlist - A3) Let $r_{1},r_{2},\ldots ,r_{n}$ be real numbers greater than or equal to $1$. Prove that
$\frac{1}{r_{1} + 1} + \frac{1}{r_{2} + 1} + \cdots +\frac{1}{r_{n}+1} \geq \frac{n}{ \sqrt[n]{r_{1}r_{2} \cdots r_{n}}+1}$.
Solution: The $ n $ functions on the LHS and the single function on the RHS gives us the idea of using Jensen's. However, we can't really get a geometric mean via Jensen's, so this approach doesn't look promising.
On the other hand, since we have $ r_i \ge 1 $, consider the substitution $ r_i = e^{a_i} $ for nonnegative reals $ a_1, a_2, \ldots, a_n $. We then have $ \sqrt[n]{r_1r_2 \cdots r_n} = e^{\frac{a_1+a_2+\cdots+a_n}{n}} $. Aha! We have converted the geometric mean to an arithmetic one, suggesting Jensen's.
Consider the function $ f(x) = \frac{1}{e^x+1} $. Since $ f^{\prime\prime}(x) = \frac{2xe^x}{(e^x+1)^2} \ge 0 $ for $ x \in [0, \infty) $, the function is convex and we may apply Jensen's on $ f $. Setting $ w_1 = w_2 = \cdots = w_n = \frac{1}{n} $, we have
$ \frac{1}{n}f(a_1)+\frac{1}{n}f(a_2)+\cdots+\frac{1}{n}f(a_n) \ge f\left(\frac{a_1+a_2+\cdots+a_n}{n}\right) $,
which is just
$ \frac{1}{r_1+1}+\frac{1}{r_2+1}+\cdots+\frac{1}{r_n+1} \ge \frac{n}{ \sqrt[n]{r_{1}r_{2} \cdots r_{n}}+1} $,
as desired. QED.
Complex Stuff! Topic: Complex Numbers/Geometry. Level: AIME.
Introduction: First, I'm going to go over a cool property of complex numbers that helps us immensely with the following AIME problem. Given any complex number $ z = a+bi = re^{i\theta} $ (make sure you understand all these forms; for more information, go here), we can rotate $ z $ about the origin by an angle $ \phi $ by multiplying by $ e^{i\phi} $.
The easiest way to show this is by saying $ ze^{i\phi} = (re^{i\theta})e^{i\phi} = re^{i(\theta+\phi)} $ from which we easily see that the angle of $ z $ simply increases by $ \phi $.
--------------------
Problem: (1994 AIME - #8) The points $(0,0)$, $(a,11)$, and $(b,37)$ are the vertices of an equilateral triangle. Find the value of $ab$.
Solution: At first glance, we're like AIME problem + analytic geometry = brute force! But then that doesn't turn out so nicely, so we remember that complex numbers are cool.
We know that in an equilateral triangle the angles are all $ \frac{\pi}{6} $. And since the origin is one of our vertices, by rotating the first point (call it $ A $) by $ \frac{\pi}{6} $ counterclockwise should result in the second point (call it $ B $). Note that it isn't the other way around by looking at a simple picture.
But by our little useful fact above, we rewrite $ A = a+11i $ and $ B = b+37i $ and thus by rotation $ Ae^{i\frac{\pi}{6}} = (a+11i)\left(\frac{1}{2}+\frac{\sqrt{3}}{2}i\right) = \frac{a-11\sqrt{3}}{2}+\frac{11+a\sqrt{3}}{2}i $ must equal $ B = b+37i $.
Equating the real and imaginary parts, we have
$ \frac{a-11\sqrt{3}}{2} = b $
$ \frac{11+a\sqrt{3}}{2} = 37 $
The second equation gives us $ a = 21\sqrt{3} $ and plugging back into the first we have $ b = 5\sqrt{3} $, giving us the answer $ ab = 315 $. QED.
--------------------
Comment: If you truly want to experience the elegance of the complex number solution, try using the distance formula to solve it; it's definitely not fun. In any case, the use of complex numbers can be generalized to many geometry problems - a lot of the time you can just put stuff on the complex plane and see what happens.
--------------------
Practice Problem: Using the complex plane, show that the sum of the $ n $th roots of unity is zero.
The easiest way to show this is by saying $ ze^{i\phi} = (re^{i\theta})e^{i\phi} = re^{i(\theta+\phi)} $ from which we easily see that the angle of $ z $ simply increases by $ \phi $.
--------------------
Problem: (1994 AIME - #8) The points $(0,0)$, $(a,11)$, and $(b,37)$ are the vertices of an equilateral triangle. Find the value of $ab$.
Solution: At first glance, we're like AIME problem + analytic geometry = brute force! But then that doesn't turn out so nicely, so we remember that complex numbers are cool.
We know that in an equilateral triangle the angles are all $ \frac{\pi}{6} $. And since the origin is one of our vertices, by rotating the first point (call it $ A $) by $ \frac{\pi}{6} $ counterclockwise should result in the second point (call it $ B $). Note that it isn't the other way around by looking at a simple picture.
But by our little useful fact above, we rewrite $ A = a+11i $ and $ B = b+37i $ and thus by rotation $ Ae^{i\frac{\pi}{6}} = (a+11i)\left(\frac{1}{2}+\frac{\sqrt{3}}{2}i\right) = \frac{a-11\sqrt{3}}{2}+\frac{11+a\sqrt{3}}{2}i $ must equal $ B = b+37i $.
Equating the real and imaginary parts, we have
$ \frac{a-11\sqrt{3}}{2} = b $
$ \frac{11+a\sqrt{3}}{2} = 37 $
The second equation gives us $ a = 21\sqrt{3} $ and plugging back into the first we have $ b = 5\sqrt{3} $, giving us the answer $ ab = 315 $. QED.
--------------------
Comment: If you truly want to experience the elegance of the complex number solution, try using the distance formula to solve it; it's definitely not fun. In any case, the use of complex numbers can be generalized to many geometry problems - a lot of the time you can just put stuff on the complex plane and see what happens.
--------------------
Practice Problem: Using the complex plane, show that the sum of the $ n $th roots of unity is zero.
Sunday, February 12, 2006
Weighted Bigness. Topic: Inequalities. Level: Olympiad.
Problem: Let $ A = (a_1, a_2, \ldots, a_n) $ and $ B = (b_1, b_2, \ldots, b_n) $ be sequences of reals such that for $ k = 1, 2, \ldots, n $ we have
$ \displaystyle \sum_{i=1}^k a_i \ge \sum_{i=1}^k b_i $.
Given a set of nonincreasing positive real weights $ w = (w_1, w_2, \ldots, w_n) $, prove that for $ k = 1,2, \ldots, n $ we have
$ \displaystyle \sum_{i=1}^k a_iw_i \ge \sum_{i=1}^k b_iw_i $.
Solution: We will prove the result for an arbitrary value of $ k $.
We know $ \displaystyle \sum_{i=1}^k a_i \ge \sum_{i=1}^k b_i $. Multiply that inequality by $ w_k $ to obtain
$ \displaystyle \sum_{i=1}^k a_iw_k \ge \sum_{i=1}^k b_iw_k $, or
$ \displaystyle \sum_{i=1}^{k-1} (a_i-b_i)w_k+(a_k-b_k)w_k \ge 0 $.
But since $ w_{k-1} \ge w_k $, we have
$ \displaystyle \sum_{i=1}^{k-1} (a_i-b_i)w_{k-1} = \sum_{i=1}^{k-2} (a_i-b_i)w_{k-1}+(a_{k-1}-b_{k-1})w_{k-1} \ge \sum_{i=1}^{k-1} (a_i-b_i)w_k $, so
$ \displaystyle \sum_{i=1}^{k-2} (a_i-b_i)w_{k-1}+(a_{k-1}-b_{k-1})w_{k-1}+(a_k-b_k)w_k \ge 0 $ as well.
Repeating this process until we get to $ 1 $, we obtain
$ \displaystyle \sum_{i=1}^k (a_i-b_i)w_i \ge 0 \Rightarrow \sum_{i=1}^k a_iw_i \ge \sum_{i=1}^k b_iw_i $.
Since $ k $ was arbitrarily chosen, it must hold for all values $ 1,2, \ldots, n $ and the result is proved. QED.
--------------------
Comment: Sort of an interesting result, though not particularly surprising. Just a little bit of algebra to work through and the proof is pretty straightforward.
--------------------
Practice Problem: Think up an inequality problem of your own! It's good practice.
$ \displaystyle \sum_{i=1}^k a_i \ge \sum_{i=1}^k b_i $.
Given a set of nonincreasing positive real weights $ w = (w_1, w_2, \ldots, w_n) $, prove that for $ k = 1,2, \ldots, n $ we have
$ \displaystyle \sum_{i=1}^k a_iw_i \ge \sum_{i=1}^k b_iw_i $.
Solution: We will prove the result for an arbitrary value of $ k $.
We know $ \displaystyle \sum_{i=1}^k a_i \ge \sum_{i=1}^k b_i $. Multiply that inequality by $ w_k $ to obtain
$ \displaystyle \sum_{i=1}^k a_iw_k \ge \sum_{i=1}^k b_iw_k $, or
$ \displaystyle \sum_{i=1}^{k-1} (a_i-b_i)w_k+(a_k-b_k)w_k \ge 0 $.
But since $ w_{k-1} \ge w_k $, we have
$ \displaystyle \sum_{i=1}^{k-1} (a_i-b_i)w_{k-1} = \sum_{i=1}^{k-2} (a_i-b_i)w_{k-1}+(a_{k-1}-b_{k-1})w_{k-1} \ge \sum_{i=1}^{k-1} (a_i-b_i)w_k $, so
$ \displaystyle \sum_{i=1}^{k-2} (a_i-b_i)w_{k-1}+(a_{k-1}-b_{k-1})w_{k-1}+(a_k-b_k)w_k \ge 0 $ as well.
Repeating this process until we get to $ 1 $, we obtain
$ \displaystyle \sum_{i=1}^k (a_i-b_i)w_i \ge 0 \Rightarrow \sum_{i=1}^k a_iw_i \ge \sum_{i=1}^k b_iw_i $.
Since $ k $ was arbitrarily chosen, it must hold for all values $ 1,2, \ldots, n $ and the result is proved. QED.
--------------------
Comment: Sort of an interesting result, though not particularly surprising. Just a little bit of algebra to work through and the proof is pretty straightforward.
--------------------
Practice Problem: Think up an inequality problem of your own! It's good practice.
Saturday, February 11, 2006
Diophantine Galore!. Topic: Number Theory. Level: AIME/Olympiad.
Problem #1: (360 Problems for Mathematical Contests - 2.1.19) Solve in the nonnegative integers the equation
$ x^2+8y^2+6xy-3x-6y = 3 $.
Solution: Write the equation as a quadratic in $ x $, that is
$ x^2+(6y-3)x+(8y^2-6y-3) = 0 $.
The discriminant of this quadratic is $ (6y-3)^2-4(8y^2-6y-3) = (2y-3)^2+12 $. Since we are only looking for integral solutions, $ (2y-3)^2+12 $ has to be the square of a rational, but since it is integral, it must be the square of an integer. So $ (2y-3)^2+12 = a^2 $, but the difference between two squares must be the sum of consecutive odd integers and the only way $ 12 $ can be written like that is $ 12 = 5+7 $. So $ 2y-3 = 2 $ (since the difference between $ 2^2 $ and $ 3^2 $ is $ 5 $) is the only possible value, but that has no solutions. Hence our original equation has no solutions. QED.
--------------------
Problem #2: (360 Problems for Mathematical Contests - 2.1.24) Solve in the nonnegative integers the equation
$ x+y+z+xyz = xy+yz+zx+2 $.
Solution: Factor the given equation to get $ (x-1)(y-1)(z-1) = 1 $. So we have either $ x-1 = y-1 = z-1 = 1 $ or two of them negative and the other positive. This gives us the solutions
$ (2,2,2); (2,0,0); (0,2,0); (0,0,2) $. QED.
--------------------
Comment: Two relatively simple diophantine equations (equations in which we are only looking for integral solutions), but they introduce important techniques. Rewriting as a quadratic and looking at the determinant is often a good way to go, especially if you can show the determinant is less than zero or something. Factoring is of course an extremely common method but a lot of the time the right way to factor may be difficult to find.
--------------------
Practice Problem: Try finding the factoring solution to the first problem (it exists).
$ x^2+8y^2+6xy-3x-6y = 3 $.
Solution: Write the equation as a quadratic in $ x $, that is
$ x^2+(6y-3)x+(8y^2-6y-3) = 0 $.
The discriminant of this quadratic is $ (6y-3)^2-4(8y^2-6y-3) = (2y-3)^2+12 $. Since we are only looking for integral solutions, $ (2y-3)^2+12 $ has to be the square of a rational, but since it is integral, it must be the square of an integer. So $ (2y-3)^2+12 = a^2 $, but the difference between two squares must be the sum of consecutive odd integers and the only way $ 12 $ can be written like that is $ 12 = 5+7 $. So $ 2y-3 = 2 $ (since the difference between $ 2^2 $ and $ 3^2 $ is $ 5 $) is the only possible value, but that has no solutions. Hence our original equation has no solutions. QED.
--------------------
Problem #2: (360 Problems for Mathematical Contests - 2.1.24) Solve in the nonnegative integers the equation
$ x+y+z+xyz = xy+yz+zx+2 $.
Solution: Factor the given equation to get $ (x-1)(y-1)(z-1) = 1 $. So we have either $ x-1 = y-1 = z-1 = 1 $ or two of them negative and the other positive. This gives us the solutions
$ (2,2,2); (2,0,0); (0,2,0); (0,0,2) $. QED.
--------------------
Comment: Two relatively simple diophantine equations (equations in which we are only looking for integral solutions), but they introduce important techniques. Rewriting as a quadratic and looking at the determinant is often a good way to go, especially if you can show the determinant is less than zero or something. Factoring is of course an extremely common method but a lot of the time the right way to factor may be difficult to find.
--------------------
Practice Problem: Try finding the factoring solution to the first problem (it exists).
Friday, February 10, 2006
Not Everyone Can Win. Topic: Algebra/Inequalities. Level: AIME/Olympiad.
Problem: (360 Problems for Mathematical Contests - 1.1.23) Let $ a,b,c $ be real numbers such that $ abc = 1 $. Prove that at most two of the numbers
$ 2a-\frac{1}{b}$, $2b-\frac{1}{c}$, $2c-\frac{1}{a} $
are greater than $ 1 $.
Solution: We proceed by contradiction, that is, assuming the opposite of what we wish to prove and showing that it is impossible. So assume all three are greater than $ 1 $.
Then their product is also greater than $ 1 $, giving
$ \left(2a-\frac{1}{b}\right)\left(2b-\frac{1}{c}\right)\left(2c-\frac{1}{a}\right) > 1 $
Expanding and substituting $ abc = 1 $, we have
$ 2(a+b+c)-\left(\frac{1}{a}+\frac{1}{b}+\frac{1}{c}\right) < 3 $.
But we also have the sum of the three greater than $ 3 $, which means
$ 2(a+b+c)-\left(\frac{1}{a}+\frac{1}{b}+\frac{1}{c}\right) > 3 $,
giving a contraction (since it cannot be both greater than and less than $ 3 $). Hence our assumption must be false and at most two of the numbers can be greater than $ 1 $. QED.
--------------------
Comment: Contradiction is a powerful technique for solving problems - oftentimes the words "at most" or "at least" lead to a possible contradiction solution.
--------------------
Practice Problem: (Olympiad Problem Solving MidTerm) Prove there are infinitely many primes of the form $ 6n+5 $ by contradiction.
$ 2a-\frac{1}{b}$, $2b-\frac{1}{c}$, $2c-\frac{1}{a} $
are greater than $ 1 $.
Solution: We proceed by contradiction, that is, assuming the opposite of what we wish to prove and showing that it is impossible. So assume all three are greater than $ 1 $.
Then their product is also greater than $ 1 $, giving
$ \left(2a-\frac{1}{b}\right)\left(2b-\frac{1}{c}\right)\left(2c-\frac{1}{a}\right) > 1 $
Expanding and substituting $ abc = 1 $, we have
$ 2(a+b+c)-\left(\frac{1}{a}+\frac{1}{b}+\frac{1}{c}\right) < 3 $.
But we also have the sum of the three greater than $ 3 $, which means
$ 2(a+b+c)-\left(\frac{1}{a}+\frac{1}{b}+\frac{1}{c}\right) > 3 $,
giving a contraction (since it cannot be both greater than and less than $ 3 $). Hence our assumption must be false and at most two of the numbers can be greater than $ 1 $. QED.
--------------------
Comment: Contradiction is a powerful technique for solving problems - oftentimes the words "at most" or "at least" lead to a possible contradiction solution.
--------------------
Practice Problem: (Olympiad Problem Solving MidTerm) Prove there are infinitely many primes of the form $ 6n+5 $ by contradiction.
Thursday, February 9, 2006
Smaller... and Smaller... and Smaller. Topic: Monovariants/NT. Level: Olympiad.
Problem: (1997 USAMO - #1) Let $ p_1, p_2, \ldots $ be the prime numbers listed in increasing order, and let $ x_0 $ be a real number between $ 0 $ and $ 1 $. For positive integral $ k $, define
$ x_k $ by $ x_k = 0 $ if $ x_{k-1} = 0 $ and $ x_k = \left\{ \frac{p_k}{x_{k-1}} \right\} $ if $ x_{k-1} \neq 0 $,
where $ \{x\} $ denotes the fractional part of $ x $. (The fractional part of $x$ is given by $x - \lfloor x \rfloor$ where $\lfloor x \rfloor$ is the greatest integer less than or equal to x.) Find, with proof, all $x_0$ satisfying $0 < x_0 < 1$ for which the sequence $x_0, x_1, x_2, \ldots$ eventually becomes $0$.
Solution: We claim that the sequence becomes $ 0 $ iff $ x_0 $ is rational.
First we prove that if $ x_0 $ is irrational then the sequence never becomes $ 0 $.
If $ x_{k-1} $ is irrational, then $ x_k = \left\{\frac{p_k}{x_{k-1}}\right\} $ is clearly irrational as well. So if $ x_0 $ is irrational by induction all $ x_i $ are irrational. Since $ 0 $ is rational, the sequence can never become $ 0 $.
Next we prove that for all rational $ x_0 $, the sequence becomes $ 0 $.
Consider $ x_{k-1} = \frac{a}{b} $ for positive integers $ a,b $ with $ a
--------------------
Comment: Notice that the proof has NOTHING to do with primes. That's rather unusual on olympiads, giving extraneous information, but it was a good way to throw people off. As long as we have a sequence of positive integers (instead of the primes), the proof holds.
$ x_k $ by $ x_k = 0 $ if $ x_{k-1} = 0 $ and $ x_k = \left\{ \frac{p_k}{x_{k-1}} \right\} $ if $ x_{k-1} \neq 0 $,
where $ \{x\} $ denotes the fractional part of $ x $. (The fractional part of $x$ is given by $x - \lfloor x \rfloor$ where $\lfloor x \rfloor$ is the greatest integer less than or equal to x.) Find, with proof, all $x_0$ satisfying $0 < x_0 < 1$ for which the sequence $x_0, x_1, x_2, \ldots$ eventually becomes $0$.
Solution: We claim that the sequence becomes $ 0 $ iff $ x_0 $ is rational.
First we prove that if $ x_0 $ is irrational then the sequence never becomes $ 0 $.
If $ x_{k-1} $ is irrational, then $ x_k = \left\{\frac{p_k}{x_{k-1}}\right\} $ is clearly irrational as well. So if $ x_0 $ is irrational by induction all $ x_i $ are irrational. Since $ 0 $ is rational, the sequence can never become $ 0 $.
Next we prove that for all rational $ x_0 $, the sequence becomes $ 0 $.
Consider $ x_{k-1} = \frac{a}{b} $ for positive integers $ a,b $ with $ a
--------------------
Comment: Notice that the proof has NOTHING to do with primes. That's rather unusual on olympiads, giving extraneous information, but it was a good way to throw people off. As long as we have a sequence of positive integers (instead of the primes), the proof holds.
Wednesday, February 8, 2006
Pick As Many As You Can. Topic: Sets/Pigeonhole Principle. Level: AIME/Olympiad.
Problem: (WOOT Test 6 - #1) Let $A$ be a subset of $\{1, 2, \ldots , 2006\}$, such that for all $x, y \in A$ with $x \neq y$, the sum $x + y$ is not divisible by $1003$. Find, with proof, the maximum value of $|A|$ (the number of elements in $A$).
Solution: We claim that the maximum $ |A| $ is $ 1003 $.
Suppose there are at least $ 1004 $ elements in $ A $. Then for some $ x \in \{1,2, \ldots, 2006 \} $ we have both $ x \in A $ and $ 2006-x \in A $ by the Pigeonhole Principle. But the sum of these is $ 2006 $, which is divisible by $ 1003 $. Hence $ |A| < 1004 $.
Now we show that a set with $ |A| = 1003 $ exists. Consider $ \{1,2,\ldots,501, 1003, 1004, \ldots, 1504 \} $. Since all the elements are $ 0,1,\ldots, 501 \pmod{1003} $ (and there is only one element divisible by $ 1003 $), we clearly cannot have two sum to $ 0 \pmod{1003} $. QED.
--------------------
Comment: Didn't choose to do this problem on the test; it was pretty easy though. A good exercise in working with sets and the Pigeonhole Principle.
--------------------
Practice Problem: What would be the maximum $ |A| $ if $ x-y $ for any $ x, y \in A $ is not divisible by $ 1003 $ either?
Solution: We claim that the maximum $ |A| $ is $ 1003 $.
Suppose there are at least $ 1004 $ elements in $ A $. Then for some $ x \in \{1,2, \ldots, 2006 \} $ we have both $ x \in A $ and $ 2006-x \in A $ by the Pigeonhole Principle. But the sum of these is $ 2006 $, which is divisible by $ 1003 $. Hence $ |A| < 1004 $.
Now we show that a set with $ |A| = 1003 $ exists. Consider $ \{1,2,\ldots,501, 1003, 1004, \ldots, 1504 \} $. Since all the elements are $ 0,1,\ldots, 501 \pmod{1003} $ (and there is only one element divisible by $ 1003 $), we clearly cannot have two sum to $ 0 \pmod{1003} $. QED.
--------------------
Comment: Didn't choose to do this problem on the test; it was pretty easy though. A good exercise in working with sets and the Pigeonhole Principle.
--------------------
Practice Problem: What would be the maximum $ |A| $ if $ x-y $ for any $ x, y \in A $ is not divisible by $ 1003 $ either?
Monday, February 6, 2006
Meeting Time! Topic: Geometry. Level: Olympiad.
Problem: (1997 Hungary-Israel, MOP Geometry Packet) The three squares $ ACC_1A^{\prime\prime} $, $ ABB_1A^{\prime} $, $ BCDE $ are constructed externally on the sides of triangle $ ABC $. Let $ P $ be the center of $ BCDE $. Prove that the lines $ A^{\prime}C, A^{\prime\prime}B, PA $ are concurrent.
Solution: So a fun concurrency problem for the day... first off, we must remember that there are a bunch of right angles in there because of squares and I'm not going to be explicitly saying it each time, but whenever I assume an angle to be right, it will be in a square. Let $ X $ be the intersection of $ BA^{\prime\prime} $ and $ CA^{\prime} $ (not on diagram). Note that we DO NOT KNOW if $ X $ lies on $ AP $ yet (or we would have assumed the result). $ F $ is the extension of $ AX $ to meet $ BC $. We do not know if $ P $ lies on line $ AXF $.
First, look at $ \triangle BAA^{\prime\prime} $ and $ \triangle CAA^{\prime} $. We see that $ CA = AA^{\prime\prime} $, $ BA = AA^{\prime} $, and $ \angle BAA^{\prime\prime} = 90^{\circ}+\angle BAC = \angle CAA^{\prime} $ so by SAS congruency, we have the two triangles congruent. Hence $ \angle AA^{\prime}H = \angle XBH $ and $ \angle AA^{\prime\prime}G = XCG $.
Then $ \angle A^{\prime}XB = 180^{\circ}-(45^{\circ}-\angle AA^{\prime}H)-(45^{\circ}+\angle XBH) = 90^{\circ} $. But since $ \angle A^{\prime}AB = 90^{\circ} $ as well, quadrilateral $ A^{\prime}AXB $ is cyclic.
From that, we have $ \angle BAX = \angle BA^{\prime}X = 45^{\circ}-\angle AA^{\prime}H = 45^{\circ}-\angle XBH = 45^{\circ}-\angle XBA $, so $ \angle AXB = 180^{\circ}-\angle BAX-\angle XBA = 135^{\circ} $. That gives us $ \angle BXF = 45^{\circ} $. Similarly, for the other side, we can show that $ \angle CXF = 45^{\circ} $ and $ \angle BXC = 90^{\circ} $.
Then consider quadrilateral $ XBCP $. Since $ \angle BXC+\angle BPC = 90^{\circ}+90^{\circ} = 180^{\circ} $, we have $ XBCP $ cyclic. Therefore, $ \angle BXP = \angle BCP = 45^{\circ} $. But since $ \angle BXF = 45^{\circ} $ as we found above, $ P $ must lie on line $ AXF $. Therefore, $ A, X, F, P $ are collinear and $ X $, the intersection of $ BA^{\prime\prime} $ and $ CA^{\prime} $, lies on $ AP $, meaning $ BA^{\prime\prime}, CA^{\prime}, AP $ are concurrent, as desired. QED.
--------------------
Comment: Concurrency problems (showing that three or more lines intersect at a single point) can be solved in a variety of ways. One of them, shown in this problem, is proving that the intersection of two lines lies on the third. Other methods include Ceva's Thoerem and the trigonometric from of Ceva's Theorem. Another topic that goes along with this nicely is collinearity - showing three or more points lie on a single line.
--------------------
Practice Problem: (1997 USAMO - #2) Let $ABC$ be a triangle, and draw isosceles triangles $DBC,AEC,ABF$ external to $ABC$ (with $BC,CA,AB$ as their respective bases). Prove that the lines through $A,B,C$ perpendicular to $EF, FD,DE$, respectively, are concurrent.
Solution: So a fun concurrency problem for the day... first off, we must remember that there are a bunch of right angles in there because of squares and I'm not going to be explicitly saying it each time, but whenever I assume an angle to be right, it will be in a square. Let $ X $ be the intersection of $ BA^{\prime\prime} $ and $ CA^{\prime} $ (not on diagram). Note that we DO NOT KNOW if $ X $ lies on $ AP $ yet (or we would have assumed the result). $ F $ is the extension of $ AX $ to meet $ BC $. We do not know if $ P $ lies on line $ AXF $.
First, look at $ \triangle BAA^{\prime\prime} $ and $ \triangle CAA^{\prime} $. We see that $ CA = AA^{\prime\prime} $, $ BA = AA^{\prime} $, and $ \angle BAA^{\prime\prime} = 90^{\circ}+\angle BAC = \angle CAA^{\prime} $ so by SAS congruency, we have the two triangles congruent. Hence $ \angle AA^{\prime}H = \angle XBH $ and $ \angle AA^{\prime\prime}G = XCG $.
Then $ \angle A^{\prime}XB = 180^{\circ}-(45^{\circ}-\angle AA^{\prime}H)-(45^{\circ}+\angle XBH) = 90^{\circ} $. But since $ \angle A^{\prime}AB = 90^{\circ} $ as well, quadrilateral $ A^{\prime}AXB $ is cyclic.
From that, we have $ \angle BAX = \angle BA^{\prime}X = 45^{\circ}-\angle AA^{\prime}H = 45^{\circ}-\angle XBH = 45^{\circ}-\angle XBA $, so $ \angle AXB = 180^{\circ}-\angle BAX-\angle XBA = 135^{\circ} $. That gives us $ \angle BXF = 45^{\circ} $. Similarly, for the other side, we can show that $ \angle CXF = 45^{\circ} $ and $ \angle BXC = 90^{\circ} $.
Then consider quadrilateral $ XBCP $. Since $ \angle BXC+\angle BPC = 90^{\circ}+90^{\circ} = 180^{\circ} $, we have $ XBCP $ cyclic. Therefore, $ \angle BXP = \angle BCP = 45^{\circ} $. But since $ \angle BXF = 45^{\circ} $ as we found above, $ P $ must lie on line $ AXF $. Therefore, $ A, X, F, P $ are collinear and $ X $, the intersection of $ BA^{\prime\prime} $ and $ CA^{\prime} $, lies on $ AP $, meaning $ BA^{\prime\prime}, CA^{\prime}, AP $ are concurrent, as desired. QED.
--------------------
Comment: Concurrency problems (showing that three or more lines intersect at a single point) can be solved in a variety of ways. One of them, shown in this problem, is proving that the intersection of two lines lies on the third. Other methods include Ceva's Thoerem and the trigonometric from of Ceva's Theorem. Another topic that goes along with this nicely is collinearity - showing three or more points lie on a single line.
--------------------
Practice Problem: (1997 USAMO - #2) Let $ABC$ be a triangle, and draw isosceles triangles $DBC,AEC,ABF$ external to $ABC$ (with $BC,CA,AB$ as their respective bases). Prove that the lines through $A,B,C$ perpendicular to $EF, FD,DE$, respectively, are concurrent.
Sunday, February 5, 2006
How Much Can You See? Topic: Geometry. Level: AMC/AIME.
Problem: (2006 AMC 12A - #22) A circle of radius $r$ is concentric with and outside a regular hexagon of side length $2$. The probability that three entire sides of the hexagon are visible from a randomly chosen point on the circle is $\frac{1}{2}$. What is $r$?
Solution: Consider the six arcs formed by extending two side to intersect the circle as shown in the diagram ($AB$ is one of these arcs). They represent the points from which one can see three entire sides of the hexagon (key step). Since there are six of them and must encompass half of the total arc length of the circle, or $180^{\circ}$, each must be $30^{\circ}$. Therefore we have $ \angle AOB = 30^{\circ} $.
Then we have $ \angle BAO = 75^{\circ} $ because $ \triangle AOB $ is isosceles. Note that $ \triangle ACB $ is equilateral because $ \angle ACB = 60^{\circ} $ and it is isosceles. Let $D$ be the foot of the perpendicular from $O$ to $AC$. We have $ \angle DAO = \angle CAO = \angle BAO-\angle BAC = 75^{\circ}-60^{\circ} = 15^{\circ} $. Note that $ DO = \sqrt{3} $ by the $ 30-60-90 $ triangles formed by the hexagon. Then the radius is $ AO = \frac{DO}{\sin{15^{\circ}}} = \frac{\sqrt{3}}{\frac{\sqrt{6}-\sqrt{2}}{4}} = 3\sqrt{2}+\sqrt{6} $. QED.
--------------------
Comment: I really liked this problem, because it was cool to translate the wording into a diagram and then if you drew the right line ($OD$) you were set with simple trigonometry. Other solutions use the Law of Cosines or the Law of Sines, but I personally favor this one which is quick and rather elegant (besides the unavoidable $\sin{15^{\circ}}$).
Solution: Consider the six arcs formed by extending two side to intersect the circle as shown in the diagram ($AB$ is one of these arcs). They represent the points from which one can see three entire sides of the hexagon (key step). Since there are six of them and must encompass half of the total arc length of the circle, or $180^{\circ}$, each must be $30^{\circ}$. Therefore we have $ \angle AOB = 30^{\circ} $.
Then we have $ \angle BAO = 75^{\circ} $ because $ \triangle AOB $ is isosceles. Note that $ \triangle ACB $ is equilateral because $ \angle ACB = 60^{\circ} $ and it is isosceles. Let $D$ be the foot of the perpendicular from $O$ to $AC$. We have $ \angle DAO = \angle CAO = \angle BAO-\angle BAC = 75^{\circ}-60^{\circ} = 15^{\circ} $. Note that $ DO = \sqrt{3} $ by the $ 30-60-90 $ triangles formed by the hexagon. Then the radius is $ AO = \frac{DO}{\sin{15^{\circ}}} = \frac{\sqrt{3}}{\frac{\sqrt{6}-\sqrt{2}}{4}} = 3\sqrt{2}+\sqrt{6} $. QED.
--------------------
Comment: I really liked this problem, because it was cool to translate the wording into a diagram and then if you drew the right line ($OD$) you were set with simple trigonometry. Other solutions use the Law of Cosines or the Law of Sines, but I personally favor this one which is quick and rather elegant (besides the unavoidable $\sin{15^{\circ}}$).
Saturday, February 4, 2006
A Lot Of Terms. Topic: Algebra/Polynomials. Level: AMC/AIME.
Problem: (2006 AMC 12A - #24) The expression
$ (x+y+z)^{2006}+(x-y-z)^{2006} $
is simplified by expanding it and combining like terms. How many terms are in the simplified expression?
Solution: This was probably my favorite problem (or #22) on the AMC-12A, though it should've been more around #20.
At first we're like oh, should've memorized trinomial expansion! And then we're like maybe we can work with binomial expansion instead since we actually know that.
Then try setting $ w = y+z $.
We now have $ (x+w)^{2006}+(x-w)^{2006} $. It's easy to see that when $ w $ is taken to an odd power the terms from the first expansion and the second expansion will cancel each other out. Using the Binomial Theorem we have the remaining even terms to be
$ 2(x^{2006}+2006C2 \cdot x^{2004}w^2+\cdots+w^{2006}) $
Since each of these terms have a different power of $ x $, we just need to find the number of terms within the expansion of $ w = y+z $ to some power. Using the Binomial Theorem again, we find that $ w^n = (y+z)^n $ simply has $ n+1 $ terms, which should be pretty clear.
Then the total number of terms, by just using the even powers above and ignoring any constants and $x$'s since they don't affect the terms, is $ (0+1)+(2+1)+(4+1)+\cdots+(2006+1) $ from each of $ (y+z)^0, (y+z)^2, \ldots, (y+z)^{2006} $. This simplifies to
$ 1+3+5+\cdots+2007 $,
and a handy formula tells us that the sum of the first $ n $ positive odd integers is just $ n^2 $, so since $ 2007 $ is the $ 1004 $th positive odd integer we have
$ 1+3+5+\cdots+2007 = 1004^2 = 1008016$
different terms. QED.
--------------------
Comment: A fun problem, quick and slick to do on the actual test. It's a good lesson that multinomial expansions are no fun and usually the binomial expansion is good enough (or you could just extend the idea).
--------------------
Practice Problem: (1990 AIME - #2) Evaluate $ (52+6\sqrt{43})^{\frac{3}{2}}-(52+6\sqrt{43})^{\frac{3}{2}} $.
$ (x+y+z)^{2006}+(x-y-z)^{2006} $
is simplified by expanding it and combining like terms. How many terms are in the simplified expression?
Solution: This was probably my favorite problem (or #22) on the AMC-12A, though it should've been more around #20.
At first we're like oh, should've memorized trinomial expansion! And then we're like maybe we can work with binomial expansion instead since we actually know that.
Then try setting $ w = y+z $.
We now have $ (x+w)^{2006}+(x-w)^{2006} $. It's easy to see that when $ w $ is taken to an odd power the terms from the first expansion and the second expansion will cancel each other out. Using the Binomial Theorem we have the remaining even terms to be
$ 2(x^{2006}+2006C2 \cdot x^{2004}w^2+\cdots+w^{2006}) $
Since each of these terms have a different power of $ x $, we just need to find the number of terms within the expansion of $ w = y+z $ to some power. Using the Binomial Theorem again, we find that $ w^n = (y+z)^n $ simply has $ n+1 $ terms, which should be pretty clear.
Then the total number of terms, by just using the even powers above and ignoring any constants and $x$'s since they don't affect the terms, is $ (0+1)+(2+1)+(4+1)+\cdots+(2006+1) $ from each of $ (y+z)^0, (y+z)^2, \ldots, (y+z)^{2006} $. This simplifies to
$ 1+3+5+\cdots+2007 $,
and a handy formula tells us that the sum of the first $ n $ positive odd integers is just $ n^2 $, so since $ 2007 $ is the $ 1004 $th positive odd integer we have
$ 1+3+5+\cdots+2007 = 1004^2 = 1008016$
different terms. QED.
--------------------
Comment: A fun problem, quick and slick to do on the actual test. It's a good lesson that multinomial expansions are no fun and usually the binomial expansion is good enough (or you could just extend the idea).
--------------------
Practice Problem: (1990 AIME - #2) Evaluate $ (52+6\sqrt{43})^{\frac{3}{2}}-(52+6\sqrt{43})^{\frac{3}{2}} $.
Thursday, February 2, 2006
Little Triangles. Topic: Geometry. Level: AIME/Olympiad.
Problem: (MOP Geometry Packet) Let $A_0B_0C_0$ be a triangle and $P$ a point. Define a new triangle whose vertices $A_1,B_1,C_1$ as the feet of the perpendiculars from $P$ to $B_0C_0,C_0A_0,A_0B_0$, respectively. Similarly, define the triangles $A_2B_2C_2$ and $A_3B_3C_3$. Show that $A_3B_3C_3$ is similar to $A_0B_0C_0$ (i.e. the third pedal triangle is similar to the original triangle).
Solution: Consider the "pedal operation" on the angles of a triangle, that is, the operation that takes a point inside a triangle, drops perpendiculars to the sides, and gives the angles of the triangle formed by the feet of the perpendiculars. Let $ f(A,B,C) $ be this operation. We want to show that $ f(f(f(A,B,C))) = (A,B,C) $.
Define the angles and points as in the diagram; $ A^{\prime}, B^{\prime}, C^{\prime} $ are the feet of the perpendiculars opposite sides $ A,B,C $ respectively, and $ \angle B^{\prime}AP = \alpha_1, \angle C^{\prime}AP = \alpha_2 $ and similarly for the other two angles.
We will define $ f(A,B,C) = (B^{\prime},C^{\prime},A^{\prime}) $.
Consider quadrilaterals $ AB^{\prime}PC^{\prime}, BC^{\prime}PA^{\prime}, CA^{\prime}PB^{\prime} $. They are all cyclic because $ \angle AB^{\prime}P = \angle AC^{\prime}P = \angle BC^{\prime}P = \angle BA^{\prime}P = \angle CA^{\prime}P = \angle CB^{\prime}P = 90^{\circ} $.
Thus we have $ \angle B^{\prime} = \angle A^{\prime}B^{\prime}C^{\prime} = \angle A^{\prime}B^{\prime}P+\angle C^{\prime}B^{\prime}P = \angle A^{\prime}CP+\angle C^{\prime}AP = \gamma_1+\alpha_2 $. Similarly, $ \angle C^{\prime} = \alpha_1+\beta_2 $ and $ \angle A^{\prime} = \beta_1+\gamma_2 $.
So $ f(\alpha_1+\alpha_2, \beta_1+\beta_2, \gamma_1+\gamma_2) = (\gamma_1+\alpha_2, \alpha_1+\beta_2, \beta_1+\gamma_2) $.
Note that the second component of each angle is invariant under $ f $. Hence $ f $ simply cycles $ \alpha_1, \beta_1, \gamma_1 $. Since there are three of them, applying $ f $ three times will give the original arrangement and the angles will the be same as of the original triangle, giving similarity. QED.
--------------------
Comment: The pedal triangle is a less common geometry topic for most people, but it's pretty cool. There are all sorts of neat things you can do with pedal triangles and pedal polygons in general.
--------------------
Practice Problem: Prove that the fourth pedal quadrilateral is similar to the quadrilateral. The result can be generalized.
Solution: Consider the "pedal operation" on the angles of a triangle, that is, the operation that takes a point inside a triangle, drops perpendiculars to the sides, and gives the angles of the triangle formed by the feet of the perpendiculars. Let $ f(A,B,C) $ be this operation. We want to show that $ f(f(f(A,B,C))) = (A,B,C) $.
Define the angles and points as in the diagram; $ A^{\prime}, B^{\prime}, C^{\prime} $ are the feet of the perpendiculars opposite sides $ A,B,C $ respectively, and $ \angle B^{\prime}AP = \alpha_1, \angle C^{\prime}AP = \alpha_2 $ and similarly for the other two angles.
We will define $ f(A,B,C) = (B^{\prime},C^{\prime},A^{\prime}) $.
Consider quadrilaterals $ AB^{\prime}PC^{\prime}, BC^{\prime}PA^{\prime}, CA^{\prime}PB^{\prime} $. They are all cyclic because $ \angle AB^{\prime}P = \angle AC^{\prime}P = \angle BC^{\prime}P = \angle BA^{\prime}P = \angle CA^{\prime}P = \angle CB^{\prime}P = 90^{\circ} $.
Thus we have $ \angle B^{\prime} = \angle A^{\prime}B^{\prime}C^{\prime} = \angle A^{\prime}B^{\prime}P+\angle C^{\prime}B^{\prime}P = \angle A^{\prime}CP+\angle C^{\prime}AP = \gamma_1+\alpha_2 $. Similarly, $ \angle C^{\prime} = \alpha_1+\beta_2 $ and $ \angle A^{\prime} = \beta_1+\gamma_2 $.
So $ f(\alpha_1+\alpha_2, \beta_1+\beta_2, \gamma_1+\gamma_2) = (\gamma_1+\alpha_2, \alpha_1+\beta_2, \beta_1+\gamma_2) $.
Note that the second component of each angle is invariant under $ f $. Hence $ f $ simply cycles $ \alpha_1, \beta_1, \gamma_1 $. Since there are three of them, applying $ f $ three times will give the original arrangement and the angles will the be same as of the original triangle, giving similarity. QED.
--------------------
Comment: The pedal triangle is a less common geometry topic for most people, but it's pretty cool. There are all sorts of neat things you can do with pedal triangles and pedal polygons in general.
--------------------
Practice Problem: Prove that the fourth pedal quadrilateral is similar to the quadrilateral. The result can be generalized.
Wednesday, February 1, 2006
Ptolemy Saves the Day! Topic: Geometry/Inequalities. Level: Olympiad.
Problem: (1997 MOP) Let $Q$ be a quadrilateral whose side lengths are $a, b, c, d$, in that order. Show that the area of $Q$ does not exceed $ \frac{ac + bd}{2}$.
Solution: Let $ A $ be the area of $ Q $. Consider writing $ A $ in terms of $ x,y,z,w $ as shown in the diagram. A common formula for the area of a triangle is equal to half of the product of two sides and the sine of the angle between them. So we have
$ A = \frac{1}{2}(xy\sin{\theta}+wz\sin{\theta}+xw\sin{(180-\theta)}+yz\sin{(180-\theta)}) $.
And since $ \sin{\theta} = \sin{(180-\theta)} $, we get
$ A = \frac{1}{2}\sin{\theta}(xy+wz+xw+yz) = \frac{1}{2}\sin{\theta}(x+z)(y+w) \le \frac{1}{2}(x+z)(y+w) $.
By Ptolemy's Inequality, we know $ ac+bd \ge (x+z)(y+w) $, so then
$ A \le \frac{1}{2}(x+z)(y+w) \le \frac{ac+bd}{2} $
as desired. QED.
--------------------
Comment: There should be a geometric, slice-it-up proof to this problem, but the trigonometric proof works out quite nicely as well. Ptolemy's Inequality is pretty useful; the equality case, when the quadrilateral is cyclic, is probably used the most. Whenever a problem has a cyclic quadrilateral with side lengths, Ptolemy is always worth a try. There is a really nice proof using complex numbers (or vectors) and the triangle inequality; see if you can find it.
--------------------
Practice Problem: Find the proof of Ptolemy's Inequality mentioned above.
Solution: Let $ A $ be the area of $ Q $. Consider writing $ A $ in terms of $ x,y,z,w $ as shown in the diagram. A common formula for the area of a triangle is equal to half of the product of two sides and the sine of the angle between them. So we have
$ A = \frac{1}{2}(xy\sin{\theta}+wz\sin{\theta}+xw\sin{(180-\theta)}+yz\sin{(180-\theta)}) $.
And since $ \sin{\theta} = \sin{(180-\theta)} $, we get
$ A = \frac{1}{2}\sin{\theta}(xy+wz+xw+yz) = \frac{1}{2}\sin{\theta}(x+z)(y+w) \le \frac{1}{2}(x+z)(y+w) $.
By Ptolemy's Inequality, we know $ ac+bd \ge (x+z)(y+w) $, so then
$ A \le \frac{1}{2}(x+z)(y+w) \le \frac{ac+bd}{2} $
as desired. QED.
--------------------
Comment: There should be a geometric, slice-it-up proof to this problem, but the trigonometric proof works out quite nicely as well. Ptolemy's Inequality is pretty useful; the equality case, when the quadrilateral is cyclic, is probably used the most. Whenever a problem has a cyclic quadrilateral with side lengths, Ptolemy is always worth a try. There is a really nice proof using complex numbers (or vectors) and the triangle inequality; see if you can find it.
--------------------
Practice Problem: Find the proof of Ptolemy's Inequality mentioned above.
Subscribe to:
Posts (Atom)