Mathematical Food for Thought


			Mathematical Food for Thought

google
yahoo
bing

About
Serves a Daily Special and an All-You-Can-Eat Course in Problem Solving. Courtesy of me, Jeffrey Wang.

Meta
- Register
- Log in
- Valid XHTML
- XFN
- WordPress

Credits
- Design by Stacee Leung
- Coded by Daynah Nguyen
- Powered by Wordpress

Da Roots. Topic: Algebra/Complex Numbers Level: AIME.	March 11th, 2007
Problem: (2007 Mock AIME 6 – #7) Let $P_n(x) = 1+x+x^2+\cdots+x^n$ and $Q_n(x) = P_1 \cdot P_2 \cdots P_n$ for all integers $n \ge 1$ . How many more distinct complex roots does $Q_{1004}$ have than $Q_{1003}$ ? Solution: Well, is familiar. Rewrite as $P_n(x) = \frac{x^{n+1}-1}{x-1}$ , i.e. the th roots of unity except . Since $Q_{1004}$ just contains a $P_{1004}$ term that $Q_{1003}$ doesn’t have, we only need to think about that term in relation to the previous ones. So we want to find out how many of the th roots of unity are not -th roots of unity for any . Well, recalling that any -th root of unity can be written as $e^{2 \pi i \frac{p}{k}} = \cos{\left(2 \pi \frac{p}{k}\right)}+i \sin{\left(2 \pi \frac{p}{k}\right)}$ for $p = 0, 1, \ldots, k-1$ , it remains to find the number of such that $\frac{p}{1005}$ does not reduce. But this, of course, is simply $\phi(1005) = 1005\left(1-\frac{1}{3}\right)\left(1-\frac{1}{5}\right)\left(1-\frac{1}{67}\right) = 2 \cdot 4 \cdot 66 = 528$ . QED. ——————– Comment: Definitely one of my favorite problems on the test because it has a really nice and clean solution once you see it. And it wasn’t too difficult to see either; combining a little knowledge of roots of unity with a little knowledge of the $\phi$ function made it a good problem. Furthermore, it offers the nice generalization that has $\phi(n+1)$ more distinct roots than $Q_{n-1}$ . ——————– Practice Problem: (2007 Mock AIME 6 – #8) A sequence of positive reals is defined by , , and $a_n \cdot a_{n+2} = a_{n+1}$ for all integers $n \ge 0$ . Given that $a_{2007}+a_{2008} = 3$ and $a_{2007} \cdot a_{2008} = \frac{1}{3}$ , find . Posted in AIME, Algebra, Complex Numbers \|\| 1 Comment »
Spinning Away… Topic: Complex Numbers. Level: AIME/Olympiad.	January 4th, 2007
Problem: (2004 Putnam – B4) Let be a positive integer, $n \ge 2$ , and put $\theta = 2 \pi /n$ . Define points in the - plane, for $k = 1, 2, \ldots, n$ . Let be the map that rotates the plane counterclockwise by the angle $\theta$ about the point . Let denote the map obtained by applying, in order, , then , $\ldots$ , then . For any arbitrary point , find, and simplify, the coordinates of . Solution: Hmm, rotations, and lots of them. That’s a big hint to use complex numbers! Recall that the rotation of a point around a point counterclockwise by an angle of $\alpha$ is $z_2+(z_1-z_2)e^{i \alpha}$ . Let’s use this formula over and over again. Start with the point , but write it as $r e^{i \phi}$ , which is much more convenient notation for rotating. Then, if we rotate around , we get $re^{i \phi} \rightarrow 1+(re^{i \phi}-1)e^{i \theta} = 1-e^{i \theta}+re^{i(\phi+\theta)}$ . Continuing this, rotating around $P_2 = 2, P_3 = 3, \ldots, P_n = n$ , we find that the points are $2-(e^{i \theta}+e^{i 2\theta})+re^{i(\phi+2\theta)}$ , $3-(e^{i \theta}+e^{i 2\theta}+e^{i 3\theta})+re^{i(\phi+3\theta)}$ , $\ldots$ . An easy induction gives us the final position as $\displaystyle n – \sum_{k=1}^n e^{i k \theta} + re^{i(\phi+n\theta)}$ . However, we know that $e^{i k \theta}$ for $k = 1, 2, \ldots, n$ are the roots of the polynomial , so their sum is zero. Also, $n\theta = 2 \pi$ so $re^{i(\phi+n\theta)} = re^{i\phi}$ . Thus the result is $n+r^{i \phi} = (n,0)+(x,y) = (x+n, y)$ . QED. ——————– Comment: This is a really neat application of the power of complex numbers in rotation problems. Basically, rotating in the plane means use complex numbers to reduce everything to algebra (which is infinitely better than geometry…). Not bad at all for a B4. Note another solution that I found to be quite interesting. Take a regular -gon of side length and top edge with vertices and . The map corresponds to a “rolling” of the -gon along the -axis. Since that translates the -gon units in the positive direction, it can be argued that it does the same for all points in the plane. ——————– Practice Problem: Given three points , let $\theta_1, \theta_2, \theta_3$ be the smallest angles that must be rotated to lie on line , must be rotated to lie on line , and must be rotated to lie on , respectively. Find the maximum value of $\theta_1+\theta_2+\theta_3$ . Posted in AIME, Complex Numbers, Olympiad \|\| 2 Comments »
Complexity. Topic: Complex Numbers/Polynomials. Level: AIME/Olympiad.	December 12th, 2006
Problem: Let $f(x) = x^{2004}+2x^{2003}+\cdots+2004x+2005$ . If $z = \cos{\frac{\pi}{1003}}+i \sin{\frac{\pi}{1003}}$ and $N = f(z)f(z^2) \cdots f(z^{2005})$ , find the remainder when is divided . [Reworded] Solution: Well is pretty ugly looking at the moment, let’s fix that. We can write it as the sum of the following series: $1+x+x^2+\cdots+x^{2004} = \frac{x^{2005}-1}{x-1}$ $1+x+x^2+\cdots+x^{2003} = \frac{x^{2004}-1}{x-1}$ $\cdots$ $1+x = \frac{x^2-1}{x-1}$ $1 = \frac{x-1}{x-1}$ , since all of them are geometric series with common ratio . Summing these up, we have $f(x) = \frac{x^{2005}+x^{2004}+\cdots+x+1-2006}{x-1}$ . The top is again a geometric series with common ratio (without that part) so we can write it ias $f(x) = \frac{\frac{x^{2006}-1}{x-1}-2006}{x-1}$ . But wait, if then $x^{2006} = (z^k)^{2006} = (z^{2006})^k = 1$ , so in fact we have $f(z^k) = \frac{2006}{1-z^k}$ . Then $N = \frac{2006^{2005}}{(1-z)(1-z^2) \cdots (1-z^{2005})$ so it remains the evaluate the denominator of that. Considering $g(x) = (x-z)(x-z^2) \cdots (x-z^{2005})$ we are like whoa, has the th roots of unity for its roots except and it has leading coefficient so it must be $g(x) = x^{2005}+x^{2004}+\cdots+1 \Rightarrow g(1) = (1-z)(1-z^2) \cdots (1-z^{2005}) = 2006$ . Hence $N = \frac{2006^{2005}}{g(1)} = 2006^{2004}$ . By Euler’s Totient Theorem, $N \equiv 6^4 \equiv 296 \pmod{1000}$ . QED. ——————– Comment: It didn’t take too much “insight” to reduce to the nicer expression, more like just tedious evaluation of geometric series galore. Seeing the product in the denominator should have been pretty familiar (though I admit I forgot what it came out to at first) and a standard argument allowed you to evaluate it. Possibly the hardest part was Euler’s Totient Theorem, which is invaluable to carry around for the AIME. Also knowing that $\phi(1000) = 400$ . ——————– Practice Problem: Do there exist polynomials and such that ? If so, find them. Posted in AIME, Complex Numbers, Olympiad, Polynomials \|\| 1 Comment »
So Complex, Yet So Plain. Topic: Complex Numbers/Polynomials. Level: AMC/AIME.	October 4th, 2006
Problem: (2006-2007 Warm-Up 3 – #13) What is the area of the shape formed by connecting the solutions to in the complex plane? Solution: Well, let’s start off by finding those solutions. It’s not hard to guess that is a solution, so we have . Using the quadratic formula, we get the other two solutions to be $x = 2 \pm i \sqrt{3}$ . So our points are $1, 2+i\sqrt{3}, 2-i\sqrt{3}$ . This makes an isosceles triangle with base $2 \sqrt{3}$ and height in the complex plane, which has area $\sqrt{3}$ . QED. ——————– Comment: Pretty easy after we guessed that was a solution; a general formula for the area probably gets ugly when the polynomial is irreducible. But in this case, we can draw the triangle and figure out the area without too many tricks. ——————– Practice Problem: What is the area of the shape formed by connecting the solutions to in the complex plane? Posted in AIME, AMC, Complex Numbers, Polynomials \|\| 1 Comment »
Now That’s Efficient. Topic: Algebra/Complex Numbers/Polynomials. Level: Olympiad.	March 22nd, 2006
Problem: (360 Problems For Mathematical Contests – 1.1.53) Let $P(x) = a_0x^n+a_1x^{n-1}+\cdots+a_n$ , $a_n \neq 0$ , be a polynomial with complex coefficients such that there is an integer with $\left\| \frac{a_m}{a_n} \right\| > nCm$ . Prove that the polynomial has at least a zero with absolute value less than . Solution: We will prove the result by contradiction. Assume all the zeros have absolute value (modulus) at least . Let the zeros be $z_1, z_2, \ldots, z_n$ . Our assumption says that $\|z_i\| \ge 1$ for all . By Vieta’s Formulas, we have $(-1)^n z_1z_2 \cdots z_n = \frac{a_n}{a_0}$ so $\|z_1z_2 \cdots z_n\| = \left\| \frac{a_n}{a_0} \right\|$ . Also, $\displaystyle (-1)^m\sum z_1z_2 \cdots z_m = \frac{a_m}{a_0}$ , where the summation is taken over all sets of roots. Then, by the Triangle Inequality for complex numbers, $\displaystyle \left\|\frac{a_m}{a_0}\right\| = \left\| \sum z_1z_2 \cdots z_m \right\| \le \sum \|z_1z_2 \cdots z_m\|$ . But since $\|z_i\| \ge 1$ for all by our assumption, we know $\|z_1z_2 \cdots z_n\| = \|z_1\|\|z_2\|\cdots\|z_n\| \ge \|z_1\|\|z_2\|\cdots\|z_m\| = \|z_1z_2 \cdots z_m\|$ and similarly for all other sets of roots. Since there are precisely sets of roots, we have $\displaystyle \sum \|z_1z_2 \cdots z_m\| \le nCm\|z_1z_2 \cdots z_n\| = nCm\left\| \frac{a_n}{a_0} \right\|$ . Connecting the inequalities, we find that $\left\| \frac{a_m}{a_0} \right\| \le nCm\left\| \frac{a_n}{a_0} \right\|$ , which means $\left\| \frac{a_m}{a_n} \right\| \le nCm$ , giving us a contradiction. Hence our original assumption is false and their exists a root such that as desired. QED. ——————– Comment: Once again, Vieta’s Formulas are extremely important to know. Also, being able to manipulate the norms of complex numbers and knowing the general properties of them is essential to solving this problem. ——————— Practice Problem: (360 Problems For Mathematical Contests – 1.1.58) Consider the equation $a_0x^n+a_1x^{n-1}+\cdots+a_n = 0$ with real coefficients . Prove that if the equation has all of its roots real, then $(n-1)a_1^2 \ge 2na_0a_2$ . Is the reciprocal true? Posted in Algebra, Complex Numbers, Olympiad, Polynomials \|\| No Comments »

free web counters