Problem: (2005 AMC 12B - #25) Six ants are on the vertices of a regular octahedron - one on each vertex. Simultaneous and independently, they each traverse one edge and arrive at another vertex. What is the probability that no two ants arrive at the same vertex?
Solution: We wish to count the number of ways the ants can move such that no two arrive at the same vertex. Consider viewing the octahedron as two points with a square between them such that the square is perpendicular to the line containing the two points. Note that two of the ants on the square must move off and the two off the square must move on.
-----
CASE 1: Two ants opposite each other on the square move off.
There are two possible pairs of ants and each pair has two ways of moving off (each one can go to either point off the square). That's $4$ possibilities.
Now consider the remaining two ants on the square. There are two ways they can move such that they don't arrive at the same vertex. That's $2$ possibilities.
Now consider the two ants off the square. There are two ways they can move onto the square (each can go to either open point). That's $2$ possibilities.
So we have $4 \cdot 2 \cdot 2 = 16$ possibilities for the first case.
-----
CASE 2: Two ants adjacent to each other on the square move off.
There are four pairs of ants adjacent to each other on the square. Each pair can move off in two different ways (same argument as CASE 1). That's $8$ possibilities.
The remaining two ants can move anywhere on the square and not be at the same vertex, giving $4$ possibilities.
The two ants off the square can move onto the square in two different ways (same argument as CASE 1). That's $2$ possibilities.
So we have $8 \cdot 4\cdot 2 = 64$ possibilites for the second case.
-----
Now consider the total possible ways satisfying the condition: $16+64 = 80$. And the total number of ways the ants can move $4^6$ (each ant has $4$ places it can go). Thus our desired probability is
$\frac{80}{4^6} = \frac{5}{256} $.
--------------------
Comment: Admittedly, the problem does look daunting when encountered at the end of the AMC-12, in your final minutes of the test, and I did not try very hard to solve the problem at the time, either. However, once you find a relatively simple method to analyze the number of ways (viewing it as two points and a square - consider the possible pairs on the square), the real counting process is quite simple. And the problem seems to just finish itself.
--------------------
Practice Problem #1: Repeat the problem above, but use a tetrahedron instead of an octahedron.
Practice Problem #2: Consider a regular hexagon with all its diagonals drawn in. What is the probability that, given any two of the seven points (including the center - intersection of the diagonals), the line segment between the points is drawn?
Practice Problem #3: Four points are randomly chosen in the plane. What is the probability that the quadrilateral they form is convex?
Wednesday, November 30, 2005
Tuesday, November 29, 2005
Inequalities Revisited. Topic: Inequalities. Level: Olympiad.
Theorem: (Rearrangement Inequality) Given two nondecreasing sequences of positive reals $x_1 \le x_2 \le \cdots \le x_n$ and $y_1 \le y_2 \le \cdots \le y_n$,
$ \displaystyle \sum_{i=1}^n x_iy_i \ge \sum_{i=1}^n x_iy_{\delta(i)} $,
where $ \delta $ is some permutation of $1,2, \ldots, n $.
--------------------
Comment: The Rearragement Inequality is extremely useful, and can quickly kill some inequalities that may be a hassle to AM-GM over and over again, as you'll see in the next example. The proof of the theorem simply requires considering a possible permutation, subtracting it away from the maximum, and showing that the difference is greater than zero.
--------------------
Problem: (1999 United Kingdom - #7) Given three non-negative reals $p,q,r$ such that $p+q+r = 1$, prove that
$ 7(pq+qr+rp) \le 2+9pqr $.
Solution: We notice that the inequality we wish to prove is not homogenous - that is, the sums of the powers on the terms are not equal. Most of the classical inequalities require you to homogenize, and given our condition, we can do so (by multiplying by $p+q+r$ when necessary). After homogenizing, the inequality becomes
$ 7(pq+qr+rp)(p+q+r) \le 2(p+q+r)^3+9pqr $.
Now this may look uglier than before, but we notice a lot of terms cancel, leaving (you may do the algebra yourself if you wish)
$ p^2q+p^2r+q^2r+q^2p+r^2p+r^2q \le 2(p^3+q^3+r^3) $.
With enough experience, this will be an obvious direct result of Rearrangement, but to explicitly use it, we set (applied three times with $n = 2$ and WLOG assuming $p \le q \le r$):
$ x_1 = p^2 \le x_2 = q^2 $
$ y_1 = p \le y_2 = q $, from which we have
$ \displaystyle \sum_{i=1}^2 x_iy_i = p^3+q^3 \ge \sum_{i=1}^2 x_iy_{\delta(i)} = p^2q+q^2p $
where $ \delta = 2,1 $. As you can see applying this on the pairs $ (p,r); (q,r) $ the same way and summing them up, we get the desired result
$ p^2q+p^2r+q^2r+q^2p+r^2p+r^2q \le 2(p^3+q^3+r^3) $.
QED.
--------------------
Comment: An "extension" of the Rearrangement Inequality, is the Muirhead Inequality, which effectively demolishes symmetric, homogenized inequalities.
--------------------
Practice Problem #1: Prove, using Rearrangement, the Trivial Inequality:
$ (x-y)^2 \ge 0 $
for positive reals $x,y$.
Practice Problem #2: Prove, using Rearrangement, a special case of the Power-Mean Inequality:
$ \sqrt[n]{\frac{x^n+y^n+z^n}{3}} \ge \frac{x+y+z}{3} $
for a positive integer $n$ and positive reals $x,y,z$.
Practice Problem #3: Given positive reals $ a,b,c $, prove that
$ \frac{a}{b+c} + \frac{b}{a+c} + \frac{c}{a+b} \ge \frac{a}{a+b} + \frac{b}{b+c} + \frac{c}{c+a} $.
$ \displaystyle \sum_{i=1}^n x_iy_i \ge \sum_{i=1}^n x_iy_{\delta(i)} $,
where $ \delta $ is some permutation of $1,2, \ldots, n $.
--------------------
Comment: The Rearragement Inequality is extremely useful, and can quickly kill some inequalities that may be a hassle to AM-GM over and over again, as you'll see in the next example. The proof of the theorem simply requires considering a possible permutation, subtracting it away from the maximum, and showing that the difference is greater than zero.
--------------------
Problem: (1999 United Kingdom - #7) Given three non-negative reals $p,q,r$ such that $p+q+r = 1$, prove that
$ 7(pq+qr+rp) \le 2+9pqr $.
Solution: We notice that the inequality we wish to prove is not homogenous - that is, the sums of the powers on the terms are not equal. Most of the classical inequalities require you to homogenize, and given our condition, we can do so (by multiplying by $p+q+r$ when necessary). After homogenizing, the inequality becomes
$ 7(pq+qr+rp)(p+q+r) \le 2(p+q+r)^3+9pqr $.
Now this may look uglier than before, but we notice a lot of terms cancel, leaving (you may do the algebra yourself if you wish)
$ p^2q+p^2r+q^2r+q^2p+r^2p+r^2q \le 2(p^3+q^3+r^3) $.
With enough experience, this will be an obvious direct result of Rearrangement, but to explicitly use it, we set (applied three times with $n = 2$ and WLOG assuming $p \le q \le r$):
$ x_1 = p^2 \le x_2 = q^2 $
$ y_1 = p \le y_2 = q $, from which we have
$ \displaystyle \sum_{i=1}^2 x_iy_i = p^3+q^3 \ge \sum_{i=1}^2 x_iy_{\delta(i)} = p^2q+q^2p $
where $ \delta = 2,1 $. As you can see applying this on the pairs $ (p,r); (q,r) $ the same way and summing them up, we get the desired result
$ p^2q+p^2r+q^2r+q^2p+r^2p+r^2q \le 2(p^3+q^3+r^3) $.
QED.
--------------------
Comment: An "extension" of the Rearrangement Inequality, is the Muirhead Inequality, which effectively demolishes symmetric, homogenized inequalities.
--------------------
Practice Problem #1: Prove, using Rearrangement, the Trivial Inequality:
$ (x-y)^2 \ge 0 $
for positive reals $x,y$.
Practice Problem #2: Prove, using Rearrangement, a special case of the Power-Mean Inequality:
$ \sqrt[n]{\frac{x^n+y^n+z^n}{3}} \ge \frac{x+y+z}{3} $
for a positive integer $n$ and positive reals $x,y,z$.
Practice Problem #3: Given positive reals $ a,b,c $, prove that
$ \frac{a}{b+c} + \frac{b}{a+c} + \frac{c}{a+b} \ge \frac{a}{a+b} + \frac{b}{b+c} + \frac{c}{c+a} $.
Monday, November 28, 2005
Add Them Up. Topic: Sequences & Series. Level: AIME/Olympiad.
Problem: (1989 USAMO - #1) For each positive integer $n$, let
$ S_n = 1+\frac{1}{2}+ \cdots + \frac{1}{n} $
$ T_n = S_1+S_2+ \cdots + S_n $
$ U_n = \frac{T_1}{2}+\frac{T_2}{3} +\cdots + \frac{T_n}{n+1} $
Find, with proof, integers $0 < a,b,c,d < 1000000 $ such that $T_{1988} = aS_{1989}-b $ and $ U_{1988} = cS_{1989}-d $.
Solution: Well let's start with the first condition - $T_{1988} = aS_{1989}-b $. We claim that
$ T_n = (n+1)(S_{n+1}-1) $.
Consider writing $T_n$ as sum of the following sequences:
$S_1 = 1$
$S_2 = 1+\frac{1}{2} $
...
$S_n = 1+\frac{1}{2}+ \cdots +\frac{1}{n} $.
Notice that $1$ appears $n$ times, $\frac{1}{2}$ appears $n-1$ times, and more generally $\frac{1}{i}$ appears $ n+1-i $ times. Then we can say
$\displaystyle T_n = \sum_{i=1}^n \frac{n+1-i}{i} = (n+1)\sum_{i=1}^n \frac{1}{i} - \sum_{i=1}^n 1 = (n+1)S_n-n = (n+1)\left(S_{n+1}-\frac{1}{n+1}\right)-n = (n+1)(S_{n+1}-1) $
as claimed. Also, save the fact that $ T_n = (n+1)S_n - n $.
So then $T_{1988} = 1989(S_{1989}-1) = 1989S_{1989}-1989 \Rightarrow a = b = 1989 $.
Now, using $ T_n = (n+1)(S_{n+1}-1) $, we substitute into the $ U_n $ equation to get
$ \displaystyle U_n = \sum_{i=1}^n \frac{T_n}{n+1} = \sum_{i=1}^n \frac{(n+1)(S_{n+1}-1)}{n+1} = \sum_{i=1}^n S_{n+1} - \sum_{i=1}^n 1 = \sum_{i=1}^n S_{n+1} - n $.
But recall that $\displaystyle \sum_{i=1}^n S_{n+1} = T_{n+1}-1 $ and remember the fact we saved back up there, so our final equation becomes
$ U_n = T_{n+1}-(n+1) = (n+2)S_{n+1}-(n+1)-(n+1) = (n+2)S_{n+1}-2(n+1)$.
So $ U_{1988} = 1990S_{1989}-3978 \Rightarrow c = 1990, d = 3978 $.
Thus our final answer is $ a = 1989, b = 1989, c = 1990, d = 3978 $. QED.
--------------------
Comment: This was back in 1989, when the USAMO was a one-day, $ 3 \frac{1}{2} $ hour test with five problems. Not until 1996 did it become a two-day test.
--------------------
Practice Problem #1: Do the problem again with $ T_{2005} $ and $ U_{2005} $ instead, to fully understand the solution.
Practice Problem #2: Show that $ T_n+\ln{(n+1)} > U_n+n $ for all positive integers $n$.
$ S_n = 1+\frac{1}{2}+ \cdots + \frac{1}{n} $
$ T_n = S_1+S_2+ \cdots + S_n $
$ U_n = \frac{T_1}{2}+\frac{T_2}{3} +\cdots + \frac{T_n}{n+1} $
Find, with proof, integers $0 < a,b,c,d < 1000000 $ such that $T_{1988} = aS_{1989}-b $ and $ U_{1988} = cS_{1989}-d $.
Solution: Well let's start with the first condition - $T_{1988} = aS_{1989}-b $. We claim that
$ T_n = (n+1)(S_{n+1}-1) $.
Consider writing $T_n$ as sum of the following sequences:
$S_1 = 1$
$S_2 = 1+\frac{1}{2} $
...
$S_n = 1+\frac{1}{2}+ \cdots +\frac{1}{n} $.
Notice that $1$ appears $n$ times, $\frac{1}{2}$ appears $n-1$ times, and more generally $\frac{1}{i}$ appears $ n+1-i $ times. Then we can say
$\displaystyle T_n = \sum_{i=1}^n \frac{n+1-i}{i} = (n+1)\sum_{i=1}^n \frac{1}{i} - \sum_{i=1}^n 1 = (n+1)S_n-n = (n+1)\left(S_{n+1}-\frac{1}{n+1}\right)-n = (n+1)(S_{n+1}-1) $
as claimed. Also, save the fact that $ T_n = (n+1)S_n - n $.
So then $T_{1988} = 1989(S_{1989}-1) = 1989S_{1989}-1989 \Rightarrow a = b = 1989 $.
Now, using $ T_n = (n+1)(S_{n+1}-1) $, we substitute into the $ U_n $ equation to get
$ \displaystyle U_n = \sum_{i=1}^n \frac{T_n}{n+1} = \sum_{i=1}^n \frac{(n+1)(S_{n+1}-1)}{n+1} = \sum_{i=1}^n S_{n+1} - \sum_{i=1}^n 1 = \sum_{i=1}^n S_{n+1} - n $.
But recall that $\displaystyle \sum_{i=1}^n S_{n+1} = T_{n+1}-1 $ and remember the fact we saved back up there, so our final equation becomes
$ U_n = T_{n+1}-(n+1) = (n+2)S_{n+1}-(n+1)-(n+1) = (n+2)S_{n+1}-2(n+1)$.
So $ U_{1988} = 1990S_{1989}-3978 \Rightarrow c = 1990, d = 3978 $.
Thus our final answer is $ a = 1989, b = 1989, c = 1990, d = 3978 $. QED.
--------------------
Comment: This was back in 1989, when the USAMO was a one-day, $ 3 \frac{1}{2} $ hour test with five problems. Not until 1996 did it become a two-day test.
--------------------
Practice Problem #1: Do the problem again with $ T_{2005} $ and $ U_{2005} $ instead, to fully understand the solution.
Practice Problem #2: Show that $ T_n+\ln{(n+1)} > U_n+n $ for all positive integers $n$.
Sunday, November 27, 2005
Circular Reasoning. Topic: Geometry. Level: AMC/AIME.
Problem #1: (2006 Mock AIME 1 - #1) $2006$ points are evenly spaced on a circle. Given one point, find the number of other points that are less than one radius distance away from that point.
Solution: We know that one radius distance is equivalent to $ \frac{1}{6} $ of the circumference (by constructing an equilateral triangle with the center and two points on the circle).
We know each point is $\frac{1}{2006} $ of the circumference away from each other, so the $k$th point is $ \frac{k}{2006} $ arc distance away. We want $ \frac{k}{2006} < \frac{1}{6} \Rightarrow k \le 334 $. But since it can be on either side, we double that, to get $668.$. QED.
--------------------
Comment: Note that this following AMC-12 problem is considerably more difficult than the preceding AIME problem, though it happens quite often that a AMC-12 #25 is more difficult than an AIME #1.
--------------------
Problem #2: (2003 AMC 12B - #25) Three points are chosen randomly and independently on a circle. What is the probability that all 3 pairwise distances between the points are less than the radius of the circle?
Solution : Now on the surface it looks pretty easy, but remember, this is a #25 - chances are it won't come too quickly for an average problem-solver (it's easy to jump into a bunch of flawed arguments). First convert everything to arc lengths - one radius becomes $\frac{1}{6}$ circumference again. Consider the following argument:
The circumference is set to $1$. Let point $A$ be the "center" of the three points, the "center" being the point that both the other points are closest to (note that the existence of the "center" is guaranteed - think about it).
Call the shortest distance between two points to be $x$ (first assume $AB = x$) - we then have the other length $1-x$. Now think about the possibilities... we want to maintain
1. The minimum distance of $x$. So the arc $AC$ has to be greater than $x$ - $AC > x$.
2. The "center" status of $A$. So the arc $BC$ has to be greater than $AC$ so $ AC < \frac{1-x}{2} $ for a given $x$. Also, $ AB $ must be less than $ BC $ (which can be as small as $\frac{1-x}{2}$), so we have $ x < \frac{1-x}{2} \Rightarrow x < \frac{1}{3}$.
(1) We can graph this such that $AB$ is on the $x$-axis and $AC $ is on the $y$-axis following these rules: $ 0 < AB < \frac{1}{3} $ and $ AB < AC < \frac{1-AB}{2} $.
(2) Now recall that we assumed $AB = x$. But $ AC $ could be $x$ as well, so we apply the same argument, flipping $AB$ and $AC$. But the graph would be the same, only flipped over the line $y=x$, creating this:
where (1) creates the red region and (2) creates the blue region (both theoretically extending into the yellow region).
Those generate the total "number" of unique possibilites, denoted by the area beneath the graph. Now we have to find the ones that satisfy our given condition: the maximum arc length is less than $ \frac{1}{6} $.
However, we notice by introducing the center status of $A$ we automatically show that our maximum arc length is $AB+AC$ because it is always greater than the independent lengths ($AB+AC > AB$ and $AB+AC > AC$ - of course this is only when $AB$ and $AC$ are both less than $\frac{1}{6}$, which is all we care about). So we add to our graph the yellow region, $AB+AC < \frac{1}{6}$.
Thus the probability is (including the extensions of the red and blue regions into the yellow) $ \frac{[yellow]}{[red]+[blue]} = \frac{\frac{1}{72}}{\frac{1}{6}} = \frac{1}{12} $. QED.
--------------------
Comment: On the actual contest, the argument would probably be loosely made in the interest of saving time and you could probably finish something like this in 5-10 minutes at most if you knew where you were headed. Of course, given that this is the last problem of an AMC-12, I wouldn't be surprised if most people didn't have those 5-10 minutes to spare.
--------------------
Practice Problem #1: Find the probability that two points placed on a circle randomly and independently are within one radius distance of each other.
Practice Problem #2: In an acute angled triangle $ABC$, $\angle A = 30^{\circ}$. $H$ is the orthocenter and $M$ is the midpoint of $BC$. On the line $HM$, take point $T$ such that $HM=MT$. Show that $AT= 2BC$. (hint: Use complex numbers - see Post 13: November 24th, 2005).
Practice Problem #3: Three congruent circles of radius 1 intersect at a common point. A larger circle is circumscribed about them, tangent to each of them at one point. Consider the midpoint of one of the diameters of the smaller circles; call it $P$. What is the length of the arc along the bigger circle containing all the points that are within 2 units of $P$?
Solution: We know that one radius distance is equivalent to $ \frac{1}{6} $ of the circumference (by constructing an equilateral triangle with the center and two points on the circle).
We know each point is $\frac{1}{2006} $ of the circumference away from each other, so the $k$th point is $ \frac{k}{2006} $ arc distance away. We want $ \frac{k}{2006} < \frac{1}{6} \Rightarrow k \le 334 $. But since it can be on either side, we double that, to get $668.$. QED.
--------------------
Comment: Note that this following AMC-12 problem is considerably more difficult than the preceding AIME problem, though it happens quite often that a AMC-12 #25 is more difficult than an AIME #1.
--------------------
Problem #2: (2003 AMC 12B - #25) Three points are chosen randomly and independently on a circle. What is the probability that all 3 pairwise distances between the points are less than the radius of the circle?
Solution : Now on the surface it looks pretty easy, but remember, this is a #25 - chances are it won't come too quickly for an average problem-solver (it's easy to jump into a bunch of flawed arguments). First convert everything to arc lengths - one radius becomes $\frac{1}{6}$ circumference again. Consider the following argument:
The circumference is set to $1$. Let point $A$ be the "center" of the three points, the "center" being the point that both the other points are closest to (note that the existence of the "center" is guaranteed - think about it).
Call the shortest distance between two points to be $x$ (first assume $AB = x$) - we then have the other length $1-x$. Now think about the possibilities... we want to maintain
1. The minimum distance of $x$. So the arc $AC$ has to be greater than $x$ - $AC > x$.
2. The "center" status of $A$. So the arc $BC$ has to be greater than $AC$ so $ AC < \frac{1-x}{2} $ for a given $x$. Also, $ AB $ must be less than $ BC $ (which can be as small as $\frac{1-x}{2}$), so we have $ x < \frac{1-x}{2} \Rightarrow x < \frac{1}{3}$.
(1) We can graph this such that $AB$ is on the $x$-axis and $AC $ is on the $y$-axis following these rules: $ 0 < AB < \frac{1}{3} $ and $ AB < AC < \frac{1-AB}{2} $.
(2) Now recall that we assumed $AB = x$. But $ AC $ could be $x$ as well, so we apply the same argument, flipping $AB$ and $AC$. But the graph would be the same, only flipped over the line $y=x$, creating this:
where (1) creates the red region and (2) creates the blue region (both theoretically extending into the yellow region).
Those generate the total "number" of unique possibilites, denoted by the area beneath the graph. Now we have to find the ones that satisfy our given condition: the maximum arc length is less than $ \frac{1}{6} $.
However, we notice by introducing the center status of $A$ we automatically show that our maximum arc length is $AB+AC$ because it is always greater than the independent lengths ($AB+AC > AB$ and $AB+AC > AC$ - of course this is only when $AB$ and $AC$ are both less than $\frac{1}{6}$, which is all we care about). So we add to our graph the yellow region, $AB+AC < \frac{1}{6}$.
Thus the probability is (including the extensions of the red and blue regions into the yellow) $ \frac{[yellow]}{[red]+[blue]} = \frac{\frac{1}{72}}{\frac{1}{6}} = \frac{1}{12} $. QED.
--------------------
Comment: On the actual contest, the argument would probably be loosely made in the interest of saving time and you could probably finish something like this in 5-10 minutes at most if you knew where you were headed. Of course, given that this is the last problem of an AMC-12, I wouldn't be surprised if most people didn't have those 5-10 minutes to spare.
--------------------
Practice Problem #1: Find the probability that two points placed on a circle randomly and independently are within one radius distance of each other.
Practice Problem #2: In an acute angled triangle $ABC$, $\angle A = 30^{\circ}$. $H$ is the orthocenter and $M$ is the midpoint of $BC$. On the line $HM$, take point $T$ such that $HM=MT$. Show that $AT= 2BC$. (hint: Use complex numbers - see Post 13: November 24th, 2005).
Practice Problem #3: Three congruent circles of radius 1 intersect at a common point. A larger circle is circumscribed about them, tangent to each of them at one point. Consider the midpoint of one of the diameters of the smaller circles; call it $P$. What is the length of the arc along the bigger circle containing all the points that are within 2 units of $P$?
Saturday, November 26, 2005
Combina-WHAT? Topic: Combinatorics. Level: AMC/AIME.
Problem #1: Prove that $ nC0+nC1+\cdots+nCn = 2^n $ ($nCk$ denotes $n$ choose $k$).
Solution: Chances are you've seen this before, and there are many proofs to it (one of my favorites being the number of subsets of an $n$-element set... think about it).
But here's another cool proof, using our very own Binomial Theorem.
Consider $ (x+1)^n = (nC0)x^n+(nC1)x^{n-1}+\cdots+(nCn) $.
But upon setting $x = 1$, we immediately have $2^n = nC0+nC1+\cdots+nCn $ as desired. QED.
--------------------
Problem #2: Prove that $ nC0-nC1+\cdots+(-1)^n(nCn) = 0 $.
Solution: Well if you understood the concept behind the first problem, this one should come very easily.
$ (x+1)^n = (nC0)x^n+(nC1)x^{n-1}+\cdots+(nCn) $ so for $ x = -1 $ we have
$ 0 = (-1)^n(nC0)+(-1)^{n-1}(nC1)+\cdots+(nCn) $ from which we can just flip the sign (if necessary) to get the desired result. QED.
--------------------
Practice Problem #1: Prove $ nC0+nC1+\cdots+nCn = 2^n $ using the subsets argument.
Practice Problem #2: Show that $ nCr+nC(r+1) = (n+1)C(r+1)$.
Practice Problem #3: (1983 AIME #8) Find the largest two-digit prime that divides $200C100$.
Solution: Chances are you've seen this before, and there are many proofs to it (one of my favorites being the number of subsets of an $n$-element set... think about it).
But here's another cool proof, using our very own Binomial Theorem.
Consider $ (x+1)^n = (nC0)x^n+(nC1)x^{n-1}+\cdots+(nCn) $.
But upon setting $x = 1$, we immediately have $2^n = nC0+nC1+\cdots+nCn $ as desired. QED.
--------------------
Problem #2: Prove that $ nC0-nC1+\cdots+(-1)^n(nCn) = 0 $.
Solution: Well if you understood the concept behind the first problem, this one should come very easily.
$ (x+1)^n = (nC0)x^n+(nC1)x^{n-1}+\cdots+(nCn) $ so for $ x = -1 $ we have
$ 0 = (-1)^n(nC0)+(-1)^{n-1}(nC1)+\cdots+(nCn) $ from which we can just flip the sign (if necessary) to get the desired result. QED.
--------------------
Practice Problem #1: Prove $ nC0+nC1+\cdots+nCn = 2^n $ using the subsets argument.
Practice Problem #2: Show that $ nCr+nC(r+1) = (n+1)C(r+1)$.
Practice Problem #3: (1983 AIME #8) Find the largest two-digit prime that divides $200C100$.
Friday, November 25, 2005
Mix it Up. Topic: Polynomials/Inequalities. Level: Olympiad.
Problem #1: (ACoPS 5.5.22) Let $P$ be a polynomial with positive coefficients. Prove that if
$ P\left(\frac{1}{x}\right) \ge \frac{1}{P(x)} $
holds for $x=1$ then it holds for every $x > 0$.
Solution: Let $P(x) = a_nx^n+a_{n-1}x^{n-1}+ \cdots + a_0 $.
We have $ P(1) \ge \frac{1}{P(1)} \Rightarrow [P(1)]^2 = (a_n+a_{n-1}+\cdots+a_0)^2 \ge 1 $.
Then we have $ P(x) \cdot P\left(\frac{1}{x}\right) = (a_nx^n+a_{n-1}x^{n-1}+ \cdots + a_0)\left(a_n\frac{1}{x^n}+a_{n-1}\frac{1}{x^{n-1}}+ \cdots + a_0)$.
But $(a_nx^n+a_{n-1}x^{n-1}+ \cdots + a_0)\left(a_n\frac{1}{x^n}+a_{n-1}\frac{1}{x^{n-1}}+ \cdots + a_0) \ge (a_n+a_{n-1}+\cdots+a_0)^2 \ge 1 $
by Cauchy (see Post 12: November 24th, 2005). QED.
--------------------
Problem #2: (USAMO 1983 #2) Prove that the zeros of
$ x^5+ax^4+bx^3+cx^2+dx+e = 0 $
cannot all be real if $ 2a^2 < 5b $.
Solution: Hmm... coefficients of polynomials... let's break out Vieta's Formulas !
So we have $ a = -(r_1+r_2+r_3+r_4+r_5) = -\sum r_i $ (for shorthand).
And $ b = r_1r_2+r_1r_3+r_1r_4+r_1r_5+r_2r_3+r_2r_4+r_2r_5+r_3r_4+r_3r_5+r_4r_5 = \sum r_ir_j$ (again, for shorthand).
So we have $ 2a^2<5b \Rightarrow 2\left(\sum r_i\right)^2 < 5\sum r_ir_j $.
Expanding and simplifying, we have $ 2\left(\sum r_i^2\right) < \sum r_ir_j $ which can be rearranged to
$ \sum (r_i-r_j)^2 < 0 $ which clearly cannot hold if all the roots are real. QED.
--------------------
Practice Problem #1: Given the polynomial $ x^3+ax^2+bx+c $ with real coefficients, find the condition the polynomial must satisfy such that it has at least one nonreal root (based on $a,b,c$). And generalize for $a_nx^n+a_{n-1}x^{n-1}+ \cdots + a_0$.
Practice Problem #2: (ACoPS 5.5.36) Prove Cauchy-Schwarz using the polynomial
$ f(x) = (a_1x+b_1)^2+(a_2x+b_2)^2+\cdots+(a_nx+b_n)^2 $
by observing that $f$ has real zeros iff $ \frac{a_1}{b_1} = \frac{a_2}{b_2} = \cdots = \frac{a_n}{b_n} $.
$ P\left(\frac{1}{x}\right) \ge \frac{1}{P(x)} $
holds for $x=1$ then it holds for every $x > 0$.
Solution: Let $P(x) = a_nx^n+a_{n-1}x^{n-1}+ \cdots + a_0 $.
We have $ P(1) \ge \frac{1}{P(1)} \Rightarrow [P(1)]^2 = (a_n+a_{n-1}+\cdots+a_0)^2 \ge 1 $.
Then we have $ P(x) \cdot P\left(\frac{1}{x}\right) = (a_nx^n+a_{n-1}x^{n-1}+ \cdots + a_0)\left(a_n\frac{1}{x^n}+a_{n-1}\frac{1}{x^{n-1}}+ \cdots + a_0)$.
But $(a_nx^n+a_{n-1}x^{n-1}+ \cdots + a_0)\left(a_n\frac{1}{x^n}+a_{n-1}\frac{1}{x^{n-1}}+ \cdots + a_0) \ge (a_n+a_{n-1}+\cdots+a_0)^2 \ge 1 $
by Cauchy (see Post 12: November 24th, 2005). QED.
--------------------
Problem #2: (USAMO 1983 #2) Prove that the zeros of
$ x^5+ax^4+bx^3+cx^2+dx+e = 0 $
cannot all be real if $ 2a^2 < 5b $.
Solution: Hmm... coefficients of polynomials... let's break out Vieta's Formulas !
So we have $ a = -(r_1+r_2+r_3+r_4+r_5) = -\sum r_i $ (for shorthand).
And $ b = r_1r_2+r_1r_3+r_1r_4+r_1r_5+r_2r_3+r_2r_4+r_2r_5+r_3r_4+r_3r_5+r_4r_5 = \sum r_ir_j$ (again, for shorthand).
So we have $ 2a^2<5b \Rightarrow 2\left(\sum r_i\right)^2 < 5\sum r_ir_j $.
Expanding and simplifying, we have $ 2\left(\sum r_i^2\right) < \sum r_ir_j $ which can be rearranged to
$ \sum (r_i-r_j)^2 < 0 $ which clearly cannot hold if all the roots are real. QED.
--------------------
Practice Problem #1: Given the polynomial $ x^3+ax^2+bx+c $ with real coefficients, find the condition the polynomial must satisfy such that it has at least one nonreal root (based on $a,b,c$). And generalize for $a_nx^n+a_{n-1}x^{n-1}+ \cdots + a_0$.
Practice Problem #2: (ACoPS 5.5.36) Prove Cauchy-Schwarz using the polynomial
$ f(x) = (a_1x+b_1)^2+(a_2x+b_2)^2+\cdots+(a_nx+b_n)^2 $
by observing that $f$ has real zeros iff $ \frac{a_1}{b_1} = \frac{a_2}{b_2} = \cdots = \frac{a_n}{b_n} $.
Thursday, November 24, 2005
Simpler than it Sounds. Topic: Complex Numbers. Level: AMC/AIME.
Problem #1: Find the coordinates of the point $ (5,4) $ rotated around the point $ (2,1) $ by $ \frac{\pi}{4} $ radians counterclockwise.
Solution: Consider these points in the complex plane ($x$-axis becomes real part, $y$-axis becomes imaginary part).
We want to rotate $5+4i$ around $2+i$. Rewrite these in $ (r, \theta) $ form, where $ r$ is the magnitude and $\theta$ is the angle. We also have $ (r, \theta) = e^{i\theta} $ by the Euler Formula.
So, to simplify things, we shift $2+i$ to the origin, and now we want to rotate $ 3+3i = 3\sqrt{2}e^{i\frac{\pi}{4}} $. We notice that rotation by $ \frac{\pi}{4} $ simply adds $ \frac{\pi}{4} $ to the angle, resulting in $ 3\sqrt{2}e^{i\frac{\pi}{2}} = 3\sqrt{2}i$.
Shifting back to the "real" origin, our rotated point becomes $ 2+(1+3\sqrt{2})i $ in the complex plane and $ (2, 1+3\sqrt{2}) $ in the Cartesian plane. QED.
--------------------
Problem #2: Given that $ A(x_1,y_1) $ and $ B(x_2,y_2) $ are two vertices of an equilateral triangle, find all possible values for the third point, $ C$.
Solution: Convert them to complex numbers - $ X = x_1+y_1i $ and $ Y = x_2+y_2i$.
Notice that if we rotate $X$ around $ Y $ by $ \frac{\pi}{3} $ or $ -\frac{\pi}{3} $ radians, we get the only two possible points for $ Z $ ($C$ as a complex number).
So applying the same rotation method as in the first problem, we have $ Z = Y + (X-Y)e^{i\frac{\pi}{3}} $ or $ Z = Y+(X-Y)e^{-i\frac{\pi}{3}}$. We can translate this back to the Cartesian plane, but it's just a mess of algebra, not essential to understanding the method of rotation in the complex plane. QED.
--------------------
Practice Problem #1: Find the value of $ A = 3+i $ rotated by $ \frac{\pi}{2} $ radians counterclockwise.
Practice Problem #2: (WOOT Class) Show that, given three complex numbers $ A, B, C$ that lie on the unit circle, the orthocenter of the triangle formed by them is $ H = A+B+C $ (hint: If two complex numbers $X, Y$ are perpendicular, $\frac{X}{Y} $ is purely imaginary... prove it).
Practice Problem #3: (WOOT Message Board) Let $O$ be the center of a circle $\omega$. Points $A,B,C,D,E,F$ on $\omega$ are chosen such that the triangles $OAB,OCD,OEF$ are equilateral. Let $L,M,N$ be the midpoints of $BC,DE,FA$, respectively. Prove that triangle $LMN$ is equilateral.
Solution: Consider these points in the complex plane ($x$-axis becomes real part, $y$-axis becomes imaginary part).
We want to rotate $5+4i$ around $2+i$. Rewrite these in $ (r, \theta) $ form, where $ r$ is the magnitude and $\theta$ is the angle. We also have $ (r, \theta) = e^{i\theta} $ by the Euler Formula.
So, to simplify things, we shift $2+i$ to the origin, and now we want to rotate $ 3+3i = 3\sqrt{2}e^{i\frac{\pi}{4}} $. We notice that rotation by $ \frac{\pi}{4} $ simply adds $ \frac{\pi}{4} $ to the angle, resulting in $ 3\sqrt{2}e^{i\frac{\pi}{2}} = 3\sqrt{2}i$.
Shifting back to the "real" origin, our rotated point becomes $ 2+(1+3\sqrt{2})i $ in the complex plane and $ (2, 1+3\sqrt{2}) $ in the Cartesian plane. QED.
--------------------
Problem #2: Given that $ A(x_1,y_1) $ and $ B(x_2,y_2) $ are two vertices of an equilateral triangle, find all possible values for the third point, $ C$.
Solution: Convert them to complex numbers - $ X = x_1+y_1i $ and $ Y = x_2+y_2i$.
Notice that if we rotate $X$ around $ Y $ by $ \frac{\pi}{3} $ or $ -\frac{\pi}{3} $ radians, we get the only two possible points for $ Z $ ($C$ as a complex number).
So applying the same rotation method as in the first problem, we have $ Z = Y + (X-Y)e^{i\frac{\pi}{3}} $ or $ Z = Y+(X-Y)e^{-i\frac{\pi}{3}}$. We can translate this back to the Cartesian plane, but it's just a mess of algebra, not essential to understanding the method of rotation in the complex plane. QED.
--------------------
Practice Problem #1: Find the value of $ A = 3+i $ rotated by $ \frac{\pi}{2} $ radians counterclockwise.
Practice Problem #2: (WOOT Class) Show that, given three complex numbers $ A, B, C$ that lie on the unit circle, the orthocenter of the triangle formed by them is $ H = A+B+C $ (hint: If two complex numbers $X, Y$ are perpendicular, $\frac{X}{Y} $ is purely imaginary... prove it).
Practice Problem #3: (WOOT Message Board) Let $O$ be the center of a circle $\omega$. Points $A,B,C,D,E,F$ on $\omega$ are chosen such that the triangles $OAB,OCD,OEF$ are equilateral. Let $L,M,N$ be the midpoints of $BC,DE,FA$, respectively. Prove that triangle $LMN$ is equilateral.
Wednesday, November 23, 2005
To Equal or not to Equal. Topic: Inequalities. Level: AIME/Olympiad.
Problem #1: Prove that, given two positive reals $a$ and $b$, we have $\frac{a+b}{2} \ge \sqrt{ab}$.
Solution: Begin with the trivial inequality ($x^2 \ge 0$) applied on $a-b$. We have
$ (a-b)^2 \ge 0$
$ a^2-2ab+b^2 \ge 0$
$ a^2+2ab+b^2 \ge 4ab$
$ (a+b)^2 \ge 4ab$
$ a+b \ge 2\sqrt{ab}$
$\frac{a+b}{2} \ge \sqrt{ab}$
as desired. QED.
--------------------
Comment: Note that we have just derived the Arithmetic Mean-Geometric Mean Inequality, more commonly referred to as just AM-GM. This can be generalized to $n$ variables by induction, that is, $\frac{a_1+a_2+\cdots+a_n}{n} \ge \sqrt[n]{a_1a_2 \cdots a_n}$.
--------------------
Problem #2: Given two sequences of positive reals $ \{a_i\}$ and $ \{b_i\} $ for $ i = 1,2, \ldots, n$, prove that $ (a_1^2+a_2^2+\cdots+a_n^2)(b_1^2+b_2^2+\cdots+b_n^2) \ge (a_1b_1+a_2b_2+\cdots+a_nb_n)^2$.
Solution: We shall prove this with vectors (read the previous blog post to get some background information).
Consider the vector $A = (a_1,a_2,\ldots,a_n)$ and the vector $B = (b_1,b_2,\ldots,b_n)$ (in an $n$-space).
We have $|A||B| \ge |A||B|\cos{\theta} = A \cdot B$ since $ \cos{\theta} \le 1$.
But recall that $ A \cdot B = (a_1,a_2,\ldots,a_n) \cdot (b_1,b_2,\ldots,b_n) = (a_1b_1+a_2b_2+\cdots+a_nb_n) $.
Also, $ |A| = \sqrt{a_1^2+a_2^2+\cdots+a_n^2}$ and $ |B| = \sqrt{b_1^2+b_2^2+\cdots+b_n^2} $.
Combining them, we get $ \sqrt{a_1^2+a_2^2+\cdots++a_n^2} \cdot \sqrt{b_1^2+b_2^2+\cdots+b_n^2} \ge (a_1b_1+a_2b_2+\cdots+a_nb_n) $, from which our result follows directly upon squaring both sides:
$ (a_1^2+a_2^2+\cdots+a_n^2)(b_1^2+b_2^2+\cdots+b_n^2) \ge (a_1b_1+a_2b_2+\cdots+a_nb_n)^2 $. QED.
--------------------
Comment: This is known as Cauchy's Inequality, or the Cauchy-Schwarz Inequality. It is one of the most useful inequalities to know and can be generalized (see Holder's Inequality).
--------------------
Problem #3: Given three positive reals $a$, $b$, and $c$, prove that $\frac{a}{b+c}+\frac{b}{c+a}+\frac{c}{a+b} \ge \frac{3}{2}$.
Solution: Let's put our newly-learned inequalities in action!
By AM-GM, we have $a^2+b^2 \ge 2ab$. Applying this to the two other pairs and summing them up, we get
$a^2+b^2+c^2 \ge ab+bc+ca$.
Adding $2(ab+bc+ca)$ to both sides, we have
$ a^2+b^2+c^2+2(ab+bc+ca) = (a+b+c)^2 \ge 3(ab+bc+ca) \Rightarrow \frac{(a+b+c)^2}{2(ab+bc+ca)} \ge \frac{3}{2} $.
Rewrite the original LHS (left hand side) as $ \frac{a^2}{ab+ac}+\frac{b^2}{bc+ba}+\frac{c^2}{ca+cb}$. By Cauchy, we have
$ (ab+bc+bc+ba+ca+cb)\left(\frac{a^2}{ab+bc}+\frac{b^2}{bc+ba}+\frac{c^2}{ca+cb}\right) \ge (a+b+c)^2 $
with $ a_1^2 = ab+bc $, $ b_1^2 = \frac{a^2}{ab+bc}$, and similarly define $ a_2, a_3, b_2, b_3$.
So then dividing by $2(ab+bc+ca)$ and combining it with the previous inequality, we find
$ \frac{a^2}{ab+bc}+\frac{b^2}{bc+ba}+\frac{c^2}{ca+cb} \ge \frac{(a+b+c)^2}{2(ab+bc+ca)} \ge \frac{3}{2} $
as desired. QED.
--------------------
Comment: This is known as Nesbitt's Inequality, and many of the classical inequalities can be applied to prove it.
--------------------
Practice Problem #1: Prove the Root-Mean-Square - Arithmetic Mean Inequality - $ \sqrt{\frac{a_1^2+a_2^2+\cdots+a_n^2}{n}} \ge \frac{a_1+a_2+\cdots+a_n}{n} $.
Practice Problem #2: (IMO 1995 #A2) Given positive reals $a, b, c$ such that $abc = 1$, prove that $ \frac{1}{a^3(b+c)}+\frac{1}{b^3(c+a)}+\frac{1}{c^3(a+b)} \ge \frac{3}{2} $.
Solution: Begin with the trivial inequality ($x^2 \ge 0$) applied on $a-b$. We have
$ (a-b)^2 \ge 0$
$ a^2-2ab+b^2 \ge 0$
$ a^2+2ab+b^2 \ge 4ab$
$ (a+b)^2 \ge 4ab$
$ a+b \ge 2\sqrt{ab}$
$\frac{a+b}{2} \ge \sqrt{ab}$
as desired. QED.
--------------------
Comment: Note that we have just derived the Arithmetic Mean-Geometric Mean Inequality, more commonly referred to as just AM-GM. This can be generalized to $n$ variables by induction, that is, $\frac{a_1+a_2+\cdots+a_n}{n} \ge \sqrt[n]{a_1a_2 \cdots a_n}$.
--------------------
Problem #2: Given two sequences of positive reals $ \{a_i\}$ and $ \{b_i\} $ for $ i = 1,2, \ldots, n$, prove that $ (a_1^2+a_2^2+\cdots+a_n^2)(b_1^2+b_2^2+\cdots+b_n^2) \ge (a_1b_1+a_2b_2+\cdots+a_nb_n)^2$.
Solution: We shall prove this with vectors (read the previous blog post to get some background information).
Consider the vector $A = (a_1,a_2,\ldots,a_n)$ and the vector $B = (b_1,b_2,\ldots,b_n)$ (in an $n$-space).
We have $|A||B| \ge |A||B|\cos{\theta} = A \cdot B$ since $ \cos{\theta} \le 1$.
But recall that $ A \cdot B = (a_1,a_2,\ldots,a_n) \cdot (b_1,b_2,\ldots,b_n) = (a_1b_1+a_2b_2+\cdots+a_nb_n) $.
Also, $ |A| = \sqrt{a_1^2+a_2^2+\cdots+a_n^2}$ and $ |B| = \sqrt{b_1^2+b_2^2+\cdots+b_n^2} $.
Combining them, we get $ \sqrt{a_1^2+a_2^2+\cdots++a_n^2} \cdot \sqrt{b_1^2+b_2^2+\cdots+b_n^2} \ge (a_1b_1+a_2b_2+\cdots+a_nb_n) $, from which our result follows directly upon squaring both sides:
$ (a_1^2+a_2^2+\cdots+a_n^2)(b_1^2+b_2^2+\cdots+b_n^2) \ge (a_1b_1+a_2b_2+\cdots+a_nb_n)^2 $. QED.
--------------------
Comment: This is known as Cauchy's Inequality, or the Cauchy-Schwarz Inequality. It is one of the most useful inequalities to know and can be generalized (see Holder's Inequality).
--------------------
Problem #3: Given three positive reals $a$, $b$, and $c$, prove that $\frac{a}{b+c}+\frac{b}{c+a}+\frac{c}{a+b} \ge \frac{3}{2}$.
Solution: Let's put our newly-learned inequalities in action!
By AM-GM, we have $a^2+b^2 \ge 2ab$. Applying this to the two other pairs and summing them up, we get
$a^2+b^2+c^2 \ge ab+bc+ca$.
Adding $2(ab+bc+ca)$ to both sides, we have
$ a^2+b^2+c^2+2(ab+bc+ca) = (a+b+c)^2 \ge 3(ab+bc+ca) \Rightarrow \frac{(a+b+c)^2}{2(ab+bc+ca)} \ge \frac{3}{2} $.
Rewrite the original LHS (left hand side) as $ \frac{a^2}{ab+ac}+\frac{b^2}{bc+ba}+\frac{c^2}{ca+cb}$. By Cauchy, we have
$ (ab+bc+bc+ba+ca+cb)\left(\frac{a^2}{ab+bc}+\frac{b^2}{bc+ba}+\frac{c^2}{ca+cb}\right) \ge (a+b+c)^2 $
with $ a_1^2 = ab+bc $, $ b_1^2 = \frac{a^2}{ab+bc}$, and similarly define $ a_2, a_3, b_2, b_3$.
So then dividing by $2(ab+bc+ca)$ and combining it with the previous inequality, we find
$ \frac{a^2}{ab+bc}+\frac{b^2}{bc+ba}+\frac{c^2}{ca+cb} \ge \frac{(a+b+c)^2}{2(ab+bc+ca)} \ge \frac{3}{2} $
as desired. QED.
--------------------
Comment: This is known as Nesbitt's Inequality, and many of the classical inequalities can be applied to prove it.
--------------------
Practice Problem #1: Prove the Root-Mean-Square - Arithmetic Mean Inequality - $ \sqrt{\frac{a_1^2+a_2^2+\cdots+a_n^2}{n}} \ge \frac{a_1+a_2+\cdots+a_n}{n} $.
Practice Problem #2: (IMO 1995 #A2) Given positive reals $a, b, c$ such that $abc = 1$, prove that $ \frac{1}{a^3(b+c)}+\frac{1}{b^3(c+a)}+\frac{1}{c^3(a+b)} \ge \frac{3}{2} $.
Tuesday, November 22, 2005
Vectors... wow! Topic: Vector Geometry. Level: AMC/AIME.
Problem #1: Find the area of the triangle formed by the heads of two vectors, $A = (5, 67^{\circ})$ and $B = (4, 37^{\circ})$, and the origin.
Solution: So, we have two vectors with pretty ugly angles, but we do notice that they differ by exactly $30^{\circ}$! Hmm, then we know two sides and the angle between them...
And consequently we remember the formula $ [ABC] = \frac{1}{2}ab\sin{\angle C} $, which makes us happy.
Hence the area of the triangle is $ \frac{1}{2}(5)(4)(\sin{30^{\circ}}) = 5$. QED.
--------------------
Comment: Notice that the formula $ \frac{|A||B|\sin{\theta}}{2} = \frac{|A \times B|}{2}$, where $ A \times B $ is the cross product of $A$ and $B$.
--------------------
Problem #2: Show that the vectors $A = (3, 4, 5)$ and $B = (2, -4, 2) $ are perpendicular.
Solution: Consider the dot product of $A$ and $B$, $ A \cdot B$. The general definition of this is $A \cdot B = |A||B|\cos{\theta}$, where $\theta$ is the angle between the two vectors. Notice that if two vectors are perpendicular to each other, the angle $\theta = 90^{\circ} \Rightarrow \cos{\theta} = 0 \Rightarrow A \cdot B = 0$.
We can easily show that the dot product is distributive (left as an exercise to the reader), that is, $A \cdot (B+C) = A \cdot B + A \cdot C$.
Thus $A \cdot B = [(3, 0, 0)+(0, 4, 0)+(0, 0, 5)] \cdot [(2, 0, 0)+(0, -4, 0)+(0, 0, 2)]$. Distributing this, we see that only the terms that are parallel remain because all the axes are perpendicular to each other ($\theta = 90^{\circ}$ between any two axes).
So $ A \cdot B = (3, 0, 0) \cdot (2, 0, 0)+(0, 4, 0) \cdot (0, -4, 0)+(0, 0, 5) \cdot (0, 0, 2) = 6 +(-16)+10 = 0$. So $A$ is perpendicular to $B$. QED.
--------------------
Comment: In effect, we have just shown that given any two vectors $ X = (x_1, x_2, \ldots, x_n)$ and $ Y = (y_1, y_2, \ldots, y_n)$, we have $ X \cdot Y = x_1y_1+x_2y_2+\cdots+x_ny_n$, an interesting and useful result (these are all in $n$-spaces, where there actually exist $n$ dimensions).
--------------------
Practice Problem #1: Show that the dot product is distributive: $ A \cdot (B+C) = A \cdot B+ A \cdot C$.
Practice Problem #2: Find the area of the triangle formed by the points $(5,2)$, $(7,8)$, and $(2,1)$.
Practice Problem #3: Show that, given three vectors of equal magnitude $A$, $B$, and $C$, the orthocenter of the triangle formed by the heads of each of the vectors is $A+B+C$.
Practice Problem #4: Using Practice Problem #3, show that the centroid ($G$), circumcenter ($O$), and orthocenter ($H$) of a triangle are collinear and that $ OG:GH = 1:2$.
Solution: So, we have two vectors with pretty ugly angles, but we do notice that they differ by exactly $30^{\circ}$! Hmm, then we know two sides and the angle between them...
And consequently we remember the formula $ [ABC] = \frac{1}{2}ab\sin{\angle C} $, which makes us happy.
Hence the area of the triangle is $ \frac{1}{2}(5)(4)(\sin{30^{\circ}}) = 5$. QED.
--------------------
Comment: Notice that the formula $ \frac{|A||B|\sin{\theta}}{2} = \frac{|A \times B|}{2}$, where $ A \times B $ is the cross product of $A$ and $B$.
--------------------
Problem #2: Show that the vectors $A = (3, 4, 5)$ and $B = (2, -4, 2) $ are perpendicular.
Solution: Consider the dot product of $A$ and $B$, $ A \cdot B$. The general definition of this is $A \cdot B = |A||B|\cos{\theta}$, where $\theta$ is the angle between the two vectors. Notice that if two vectors are perpendicular to each other, the angle $\theta = 90^{\circ} \Rightarrow \cos{\theta} = 0 \Rightarrow A \cdot B = 0$.
We can easily show that the dot product is distributive (left as an exercise to the reader), that is, $A \cdot (B+C) = A \cdot B + A \cdot C$.
Thus $A \cdot B = [(3, 0, 0)+(0, 4, 0)+(0, 0, 5)] \cdot [(2, 0, 0)+(0, -4, 0)+(0, 0, 2)]$. Distributing this, we see that only the terms that are parallel remain because all the axes are perpendicular to each other ($\theta = 90^{\circ}$ between any two axes).
So $ A \cdot B = (3, 0, 0) \cdot (2, 0, 0)+(0, 4, 0) \cdot (0, -4, 0)+(0, 0, 5) \cdot (0, 0, 2) = 6 +(-16)+10 = 0$. So $A$ is perpendicular to $B$. QED.
--------------------
Comment: In effect, we have just shown that given any two vectors $ X = (x_1, x_2, \ldots, x_n)$ and $ Y = (y_1, y_2, \ldots, y_n)$, we have $ X \cdot Y = x_1y_1+x_2y_2+\cdots+x_ny_n$, an interesting and useful result (these are all in $n$-spaces, where there actually exist $n$ dimensions).
--------------------
Practice Problem #1: Show that the dot product is distributive: $ A \cdot (B+C) = A \cdot B+ A \cdot C$.
Practice Problem #2: Find the area of the triangle formed by the points $(5,2)$, $(7,8)$, and $(2,1)$.
Practice Problem #3: Show that, given three vectors of equal magnitude $A$, $B$, and $C$, the orthocenter of the triangle formed by the heads of each of the vectors is $A+B+C$.
Practice Problem #4: Using Practice Problem #3, show that the centroid ($G$), circumcenter ($O$), and orthocenter ($H$) of a triangle are collinear and that $ OG:GH = 1:2$.
Monday, November 21, 2005
Polynomial Power. Topic: Algebra/Polynomials. Level: AIME.
Problem: (2006 Mock AIME 1 - #14) Let $P(x)$ be a monic polynomial of degree $n \ge 1$ such that
$ [P(x)]^3 = [P(x)]^2-P(x)+6$
for $x = 1, 2, \ldots , n$. Let $n_0$ be the smallest $n$ such that $P(0) > (P(1)+P(2)+ \cdots +P(n))^3$.
Find the remainder when $P(0)$ is divided by $1000$ given $n = n_0$.
Solution: Well the condition we're given as it is doesn't look particularly helpful in defining the polynomial, especially with the cube. So we try and factor it (almost always a safe bet) and we find
$ (P(x)-2)([P(x)]^2+P(x)+3) = 0$.
But we notice that $ [P(x)]^2+P(x)+3 = \left(P(x)+\frac{1}{2}\right)^2 + \frac{11}{4} > 0$. So then we must have $ P(x)-2 = 0 $ for $x = 1, 2, \ldots, n$.
Consider the polynomial $H(x) = P(x)-2$. It has zeros at $x = 1, 2, \ldots, n$ and is also monic with degree $n$. Hence $H(x) = (x-1)(x-2)\cdots(x-n) \Rightarrow P(x) = (x-1)(x-2)\cdots(x-n)+2$.
Then we have $P(0) = (-1)^n\cdot n!+2 > (P(1)+P(2)+\cdots+P(n))^3 = (2n)^3 = 8n^3$. Checking, we find the first $n$ such that this is true is $n = 8$. Therefore, $P(0) = (-1)^8 \cdot 8!+2 = 40322$. So our answer is $322$. QED.
--------------------
Pracitice Problem #1: Factor $ x^4+64 $.
Practice Problem #2: Let $P(x)$ be a monic polynomial of degree $n$ such that $P(x) = x$ for $x = 1,2,\ldots,n$. Find a closed expression for $P(n+1)$.
$ [P(x)]^3 = [P(x)]^2-P(x)+6$
for $x = 1, 2, \ldots , n$. Let $n_0$ be the smallest $n$ such that $P(0) > (P(1)+P(2)+ \cdots +P(n))^3$.
Find the remainder when $P(0)$ is divided by $1000$ given $n = n_0$.
Solution: Well the condition we're given as it is doesn't look particularly helpful in defining the polynomial, especially with the cube. So we try and factor it (almost always a safe bet) and we find
$ (P(x)-2)([P(x)]^2+P(x)+3) = 0$.
But we notice that $ [P(x)]^2+P(x)+3 = \left(P(x)+\frac{1}{2}\right)^2 + \frac{11}{4} > 0$. So then we must have $ P(x)-2 = 0 $ for $x = 1, 2, \ldots, n$.
Consider the polynomial $H(x) = P(x)-2$. It has zeros at $x = 1, 2, \ldots, n$ and is also monic with degree $n$. Hence $H(x) = (x-1)(x-2)\cdots(x-n) \Rightarrow P(x) = (x-1)(x-2)\cdots(x-n)+2$.
Then we have $P(0) = (-1)^n\cdot n!+2 > (P(1)+P(2)+\cdots+P(n))^3 = (2n)^3 = 8n^3$. Checking, we find the first $n$ such that this is true is $n = 8$. Therefore, $P(0) = (-1)^8 \cdot 8!+2 = 40322$. So our answer is $322$. QED.
--------------------
Pracitice Problem #1: Factor $ x^4+64 $.
Practice Problem #2: Let $P(x)$ be a monic polynomial of degree $n$ such that $P(x) = x$ for $x = 1,2,\ldots,n$. Find a closed expression for $P(n+1)$.
Sunday, November 20, 2005
Go Go Geometry! Topic: Geometry/Trigonometry. Level: AIME.
Problem: (2006 Mock AIME 1 - #15) Let $ABCD$ be a rectangle and $AB = 24$. Let $E$ be a point on $BC$ (between $B$ and $C$) such that $DE = 25$ and $\tan{\angle BDE} = 3$. Let $F$ be the foot of the perpendicular from $A$ to $BD$. Extend $AF$ to intersect $DC$ at $G$. Extend $DE$ to intersect $AG$ at $H$. Let $I$ be the foot of the perpendicular from $H$ to $DG$. The length of $IG$ is $\displaystyle \frac{m}{n}$, where $m$ and $n$ are relatively prime positive integers. Suppose $\alpha$ is the sum of the distinct prime factors of $m$ and $\beta$ is the sum of the distinct prime factors of $n$. Find $\alpha + \beta$.
Solution: We begin by solving for $EC = \sqrt{25^2-24^2} = 7$. Then $\tan{EDC} = \frac{7}{24}$.
By the tangent addition formula, we have
$\tan{BDC} = \tan{(BDE+EDC)} = \frac{\tan{BDE}+\tan{EDC}}{1-\tan{BDE}\tan{EDC}} = \frac{3+\frac{7}{24}}{1-3\left(\frac{7}{24}\right)} = \frac{79}{3} $.
Since $\tan{BDC} = \frac{BC}{CD}$, we have $\displaystyle BC = (CD)\tan{BDC} = 24\left(\frac{79}{3}\right) = 632$.
Notice that $\angle AGD = 90 - \angle BDC \Rightarrow \tan{AGD} = \frac{1}{\tan{BDC}} = \frac{3}{79}$.
Then $\tan{AGD} = \frac{AD}{DG} \Rightarrow DG = \frac{AD}{\tan{AGD}} = \frac{632}{\frac{3}{79}} = \frac{2^3 \cdot 79}{3}$.
Consider $\triangle HIG$. We have $\tan{HGI} = \frac{HI}{IG} \Rightarrow HI = (IG)\tan{HGI} = \frac{3}{79}(IG)$.
Notice that $\triangle EDC$ is similar to $\triangle HDI$, so $\frac{HI}{ID} = \frac{EC}{CD} = \frac{7}{24} \Rightarrow HI = \frac{7}{24}(ID) = \frac{7}{24}(DG-IG)$.
Combining our two expressions for $HI$, we get
$ HI = \frac{3}{79}(IG) = \frac{7}{24}(DG-IG)$.
Solving this for $IG$, we get
$IG = \frac{\frac{7}{24}(DG)}{\frac{3}{79}+\frac{7}{24}$.
But we calculated $DG = \frac{2^3 \cdot 79}{3}$ above, so upon substitution we get
$IG = \frac{\frac{7}{24}\left(\frac{2^3 \cdot 79}{3}\right)}{\frac{3 \cdot 24 + 7 \cdot 79}{24 \cdot 79}} = \frac{2^3 \cdot 7 \cdot 79^3}{3 \cdot 5^4} $.
Summing the distinct prime factors, we have $2+7+79+3+5 = 96$.
Solution: We begin by solving for $EC = \sqrt{25^2-24^2} = 7$. Then $\tan{EDC} = \frac{7}{24}$.
By the tangent addition formula, we have
$\tan{BDC} = \tan{(BDE+EDC)} = \frac{\tan{BDE}+\tan{EDC}}{1-\tan{BDE}\tan{EDC}} = \frac{3+\frac{7}{24}}{1-3\left(\frac{7}{24}\right)} = \frac{79}{3} $.
Since $\tan{BDC} = \frac{BC}{CD}$, we have $\displaystyle BC = (CD)\tan{BDC} = 24\left(\frac{79}{3}\right) = 632$.
Notice that $\angle AGD = 90 - \angle BDC \Rightarrow \tan{AGD} = \frac{1}{\tan{BDC}} = \frac{3}{79}$.
Then $\tan{AGD} = \frac{AD}{DG} \Rightarrow DG = \frac{AD}{\tan{AGD}} = \frac{632}{\frac{3}{79}} = \frac{2^3 \cdot 79}{3}$.
Consider $\triangle HIG$. We have $\tan{HGI} = \frac{HI}{IG} \Rightarrow HI = (IG)\tan{HGI} = \frac{3}{79}(IG)$.
Notice that $\triangle EDC$ is similar to $\triangle HDI$, so $\frac{HI}{ID} = \frac{EC}{CD} = \frac{7}{24} \Rightarrow HI = \frac{7}{24}(ID) = \frac{7}{24}(DG-IG)$.
Combining our two expressions for $HI$, we get
$ HI = \frac{3}{79}(IG) = \frac{7}{24}(DG-IG)$.
Solving this for $IG$, we get
$IG = \frac{\frac{7}{24}(DG)}{\frac{3}{79}+\frac{7}{24}$.
But we calculated $DG = \frac{2^3 \cdot 79}{3}$ above, so upon substitution we get
$IG = \frac{\frac{7}{24}\left(\frac{2^3 \cdot 79}{3}\right)}{\frac{3 \cdot 24 + 7 \cdot 79}{24 \cdot 79}} = \frac{2^3 \cdot 7 \cdot 79^3}{3 \cdot 5^4} $.
Summing the distinct prime factors, we have $2+7+79+3+5 = 96$.
Thursday, November 17, 2005
2006 Mock AIME 1.
Here is the first AoPS Mock AIME of the 2005-2006 year, written by yours truly. If you wish to participate officially, please create an AoPS account at the AoPS forum.
2006 Mock AIME 1
Date: Friday, Nov. 18th to Sunday, Nov. 20th, 2005
Time: 3 hours, self-timed
Format: 15 questions, Free Response (ALL answers are integers from 000 to 999, inclusive)
Scoring: 1 point per correct answer (No guessing penalty)
Submitting Answers: PM the answers to me, paladin8.
Answer Format: (As follows)
1. Answer to #1
2. Answer to #2
...
15. Answer to #15
2006 Mock AIME 1 Questions
P.S. I'll be gone the next two days, so don't expect blog posts.
EDIT: Ack, #14 should be taken mod 1000, to get an AIME answer, my mistake to anyone who has taken it already. I'll modify the actual PDF file when I get home.
EDIT 2: All better.
EDIT 3: #15 was also written incorrectly (hey, it's not that easy to write hard AIME problems); fixed now.
2006 Mock AIME 1
Date: Friday, Nov. 18th to Sunday, Nov. 20th, 2005
Time: 3 hours, self-timed
Format: 15 questions, Free Response (ALL answers are integers from 000 to 999, inclusive)
Scoring: 1 point per correct answer (No guessing penalty)
Submitting Answers: PM the answers to me, paladin8.
Answer Format: (As follows)
1. Answer to #1
2. Answer to #2
...
15. Answer to #15
2006 Mock AIME 1 Questions
P.S. I'll be gone the next two days, so don't expect blog posts.
EDIT: Ack, #14 should be taken mod 1000, to get an AIME answer, my mistake to anyone who has taken it already. I'll modify the actual PDF file when I get home.
EDIT 2: All better.
EDIT 3: #15 was also written incorrectly (hey, it's not that easy to write hard AIME problems); fixed now.
Wednesday, November 16, 2005
Modular Math. Topic: Number Theory. Level: AMC/AIME.
Problem: What is the remainder when you divide $6^{2005}+8^{2005}$ by $49$?
Solution Modular arithmetic is a useful tool for this problem. The concept is really quite simple:
We state that $a \equiv b \pmod{c} \Rightarrow c|(a-b)$,
that is, $a$ and $b$ leave the same remainder upon division by $c$.
We rewrite the problem as evaluating $6^{2005}+8^{2005} \pmod{49}$.
The key to this problem is noticing that $6 = 7-1$ and $8 = 7+1$. Rewrite them as such:
$(7-1)^{2005}+(7+1)^{2005}$.
Applying our handy Binomial Theorem, we see that
$\displaystyle (7-1)^{2005} = (2005C0)(7^{2005}) - (2005C1)(7^{2004}) + \ldots +(2005C2004)(7)-(2005C2005)$.
Consider this $\pmod{49}$ or $\pmod{7^2}$. We note that any term with a power of $7$ greater than or equal to $2$ is $0 \pmod{49}$ (make sure you get this, review the definition of mod if you don't). Thus the only terms that we need to consider are the last two: $\displaystyle (2005C2004)(7)-(2005C2005) = 2005(7)-1$.
Similarly, the only two terms of $(7+1)^{2005}$ we need to consider are $\displaystyle (2005C2004)(7)+(2005C2005) = 2005(7)+1$.
Summing the two, we have $(2005(7)-1)+(2005(7)-1) = 4010(7) \equiv 42 \pmod{49}$ (you can work out the details yourself). Hence our answer is $42$. QED.
--------------------
Comment: Modular arithmetic has extremely wide applications in Number Theory, including a number of important theorems you should be familiar with (e.g. Fermat's Little Theorem). Learning this concept will increase your ability to solve NT problems dramatically. If you just love Number Theory and want to learn more about it, check out the PROMYS website; it's a summer camp devoted entirely to NT.
--------------------
Practice Problem: Find the remainder when $1+10+10^2+\ldots+10^{2005}$ is divided by $9$.
Solution Modular arithmetic is a useful tool for this problem. The concept is really quite simple:
We state that $a \equiv b \pmod{c} \Rightarrow c|(a-b)$,
that is, $a$ and $b$ leave the same remainder upon division by $c$.
We rewrite the problem as evaluating $6^{2005}+8^{2005} \pmod{49}$.
The key to this problem is noticing that $6 = 7-1$ and $8 = 7+1$. Rewrite them as such:
$(7-1)^{2005}+(7+1)^{2005}$.
Applying our handy Binomial Theorem, we see that
$\displaystyle (7-1)^{2005} = (2005C0)(7^{2005}) - (2005C1)(7^{2004}) + \ldots +(2005C2004)(7)-(2005C2005)$.
Consider this $\pmod{49}$ or $\pmod{7^2}$. We note that any term with a power of $7$ greater than or equal to $2$ is $0 \pmod{49}$ (make sure you get this, review the definition of mod if you don't). Thus the only terms that we need to consider are the last two: $\displaystyle (2005C2004)(7)-(2005C2005) = 2005(7)-1$.
Similarly, the only two terms of $(7+1)^{2005}$ we need to consider are $\displaystyle (2005C2004)(7)+(2005C2005) = 2005(7)+1$.
Summing the two, we have $(2005(7)-1)+(2005(7)-1) = 4010(7) \equiv 42 \pmod{49}$ (you can work out the details yourself). Hence our answer is $42$. QED.
--------------------
Comment: Modular arithmetic has extremely wide applications in Number Theory, including a number of important theorems you should be familiar with (e.g. Fermat's Little Theorem). Learning this concept will increase your ability to solve NT problems dramatically. If you just love Number Theory and want to learn more about it, check out the PROMYS website; it's a summer camp devoted entirely to NT.
--------------------
Practice Problem: Find the remainder when $1+10+10^2+\ldots+10^{2005}$ is divided by $9$.
Tuesday, November 15, 2005
Power of a Point. Topic: Geometry. Level: AMC/AIME.
Problem: Given a circle that passes through the points $(3,4)$ and $(6,8)$, find the length of a tangent to the circle from the origin.
Solution: Consider Power of a Point, which states that
$a^2 = b(b+c) = d(d+e)$, all of which are equal to the power of the point at which they intersect.
Now consider the tangent from the origin in the problem (call this length $x$) and notice that the secant from the origin through $(3,4)$ passes through $(6,8)$ as well.
Then by Power of a Point applied to the origin, we have $x^2 = (\sqrt{3^2+4^2})(\sqrt{6^2+8^2}) = (5)(10) = 50 \Rightarrow x = \sqrt{50}$. QED.
Note: On the actual contest (ARML) a third point was provided to define the circle. We notice, however, that this third point is not necessary and was thus omitted in this rewording of the problem.
--------------------
Practice Problem: Given two circles, find all points $P$ such that the power of point $P$ with respect to both circles is equal.
Solution: Consider Power of a Point, which states that
$a^2 = b(b+c) = d(d+e)$, all of which are equal to the power of the point at which they intersect.
Now consider the tangent from the origin in the problem (call this length $x$) and notice that the secant from the origin through $(3,4)$ passes through $(6,8)$ as well.
Then by Power of a Point applied to the origin, we have $x^2 = (\sqrt{3^2+4^2})(\sqrt{6^2+8^2}) = (5)(10) = 50 \Rightarrow x = \sqrt{50}$. QED.
Note: On the actual contest (ARML) a third point was provided to define the circle. We notice, however, that this third point is not necessary and was thus omitted in this rewording of the problem.
--------------------
Practice Problem: Given two circles, find all points $P$ such that the power of point $P$ with respect to both circles is equal.
Monday, November 14, 2005
Diophantine Fun. Topic: Number Theory. Level: AIME.
Problem: Find all integer solutions $(m,n)$ to the equation
$n^4+n^3+2n^2+2n+1 = m^2$.
Solution: Let me introduce a technique used to solve diophantine equations with a power (square in this case) on one side and a multiple of that power (fourth power) on the other: Bounding.
--------------------
Example - Suppose you had the equation $n^2+3n+3 = m^2$ (assume positive integers for the example; it is not necessary for the actual problem though). We can say
$(n+1)^2 < n^2+3n+3 < (n+2)^2$ which can be verified by expanding.
The LHS becomes $0 < n+2$ and the RHS becomes $0 < n+1$.
But there are no integer squares between $(n+1)^2$ and $(n+2)^2$ so we can conclude that there are no solutions.
--------------------
Now back to the problem... we look for bounding squares; however, this requires some experimenting and matching coefficients. We want to match at least the first two terms - $n^4+n^3$.
After playing around with squares, we find a pretty good bound that works for $n \ge 4$ and $n \le 0$:
$\displaystyle \left(n^2+\frac{n}{2}+\frac{1}{2}\right)^2 \le n^4+n^3+2n^2+2n+1 \le \left(n^2+\frac{n}{2}+1\right)^2$.
The LHS becomes $\displaystyle 0 \le \frac{3}{4}(n+1)^2$ and the RHS $\displaystyle 0 \le n\left(\frac{n}{4}-1\right)$ (hence the restrictions on $n$).
Since there are no squares between $\displaystyle \left(n^2+\frac{n}{2}+\frac{1}{2}\right)^2$ and $\displaystyle \left(n^2+\frac{n}{2}+1\right)^2$, the only possible solutions are the equality conditions and $n=1,2,3$.
Checking those three, we find nothing, so we move to the equality conditions.
As noted above, the equality conditions are $\displaystyle 0 = \frac{3}{4}(n+1)^2$ and $\displaystyle 0 = n\left(\frac{n}{4}-1\right)$, giving the solutoins $n=-1, 0, 4$. Then $m = \pm 1, \pm 1, \pm 19$, respectively.
Hence our solutions are: $(m,n) = (-1, \pm 1); (0, \pm 1); (4, \pm 19)$. QED.
--------------------
Practice Problem: Find all nonnegative integer solutions $(a,b)$ to the equation
$a^6+2a^4+2a^2+2a+1 = b^2$.
$n^4+n^3+2n^2+2n+1 = m^2$.
Solution: Let me introduce a technique used to solve diophantine equations with a power (square in this case) on one side and a multiple of that power (fourth power) on the other: Bounding.
--------------------
Example - Suppose you had the equation $n^2+3n+3 = m^2$ (assume positive integers for the example; it is not necessary for the actual problem though). We can say
$(n+1)^2 < n^2+3n+3 < (n+2)^2$ which can be verified by expanding.
The LHS becomes $0 < n+2$ and the RHS becomes $0 < n+1$.
But there are no integer squares between $(n+1)^2$ and $(n+2)^2$ so we can conclude that there are no solutions.
--------------------
Now back to the problem... we look for bounding squares; however, this requires some experimenting and matching coefficients. We want to match at least the first two terms - $n^4+n^3$.
After playing around with squares, we find a pretty good bound that works for $n \ge 4$ and $n \le 0$:
$\displaystyle \left(n^2+\frac{n}{2}+\frac{1}{2}\right)^2 \le n^4+n^3+2n^2+2n+1 \le \left(n^2+\frac{n}{2}+1\right)^2$.
The LHS becomes $\displaystyle 0 \le \frac{3}{4}(n+1)^2$ and the RHS $\displaystyle 0 \le n\left(\frac{n}{4}-1\right)$ (hence the restrictions on $n$).
Since there are no squares between $\displaystyle \left(n^2+\frac{n}{2}+\frac{1}{2}\right)^2$ and $\displaystyle \left(n^2+\frac{n}{2}+1\right)^2$, the only possible solutions are the equality conditions and $n=1,2,3$.
Checking those three, we find nothing, so we move to the equality conditions.
As noted above, the equality conditions are $\displaystyle 0 = \frac{3}{4}(n+1)^2$ and $\displaystyle 0 = n\left(\frac{n}{4}-1\right)$, giving the solutoins $n=-1, 0, 4$. Then $m = \pm 1, \pm 1, \pm 19$, respectively.
Hence our solutions are: $(m,n) = (-1, \pm 1); (0, \pm 1); (4, \pm 19)$. QED.
--------------------
Practice Problem: Find all nonnegative integer solutions $(a,b)$ to the equation
$a^6+2a^4+2a^2+2a+1 = b^2$.
Hello!
Welcome to my blog! This will be an ongoing journal of mathematical problems and problem solving techniques, targetted at high school students like myself aiming to do well on the American Math Competitions. The difficulty will range from mostly difficult AMC problems to USAMO problems. Enjoy!
Subscribe to:
Posts (Atom)