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

Leftovers. Topic: Algebra/Polynomials. Level: AIME.	December 22nd, 2006
Problem: (Stanford Putnam Practice) Find the remainder when you divide $x^{81}+x^{49}+x^{25}+x^9+x$ by . Solution: Since they’re both divisible by , we first divide that out, and just remember to multiply the remainder by at the end. Let be the first polynomial and be the second. we have for some polynomials with $\deg(r) < deg(Q) = 2$ . We want to find . Consider the two roots of . Plugging them into the equation, we obtain and . Evaluating at those two values, we find that and . But since has degree less than , the only possible is the constant polynomial . Then the remainder is . QED. ——————– Comment: This is a super important technique when it comes to polynomial division. Using the $\deg(Q)$ roots of and the fact that , we can hypothetically always determine this way, without dividing. This usually comes up when has nice roots, so if it doesn’t, look for a better way. ——————– Practice Problem: (Stanford Putnam Practice) How can the quadratic equation $\frac{(x-a)(x-b)}{(c-a)(c-b)}+\frac{(x-b)(x-c)}{(a-b)(a-c)}+\frac{(x-c)(x-a)}{(b-c)(b-a)} = 1$ have three roots ? [Reworded] Posted in AIME, Algebra, Polynomials \|\| 1 Comment »
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 »
Yay! Putnam! Topic: Algebra/Polynomials. Level: AIME.	December 3rd, 2006
Problem: (2006 Putnam – B1) Show that the curve $x^{3}+3xy+y^{3}=1$ contains only one set of three distinct points, , , and , which are the vertices of an equilateral triangle, and find its area. Solution: Well, this is a cubic in two variables, but let’s remember the awesome technique of writing it as a polynomial in just one variable, say . Then . Well, testing out a bit (looking at the factorization of ), we get is always a solution, so factor it out to get . Looking at the second term, we’re like let’s hope it has not many solutions, so we take the discriminant and find . But this is always negative unless so that means this is the only case in which this factor can be zero. This gives us the point as a solution. Whoa, that means we have categorized the entire solution set: (1) the line and (2) the point . If we have three vertices of an equilateral triangle, they most definitely can’t be collinear, so one point must be . Suppose we choose two points on the line , say and . Since they have to be equidistant from , we know one must be the reflection of the other over the line through perpendicular to , which is . So if the first point is then the other is . Now setting the squares of the side lengths equal to each other, we know so $x_0 = \frac{1}{2} \pm \frac{\sqrt{3}}{2}$ . This gives the -coordinate of both the other two vertices of the triangle, so the only one is the equilateral triangle with vertices $(-1, -1); \left(\frac{1}{2}+\frac{\sqrt{3}}{2}, \frac{1}{2}-\frac{\sqrt{3}}{2}\right); \left(\frac{1}{2}-\frac{\sqrt{3}}{2}, \frac{1}{2}+\frac{\sqrt{3}}{2}\right)$ . The side length is $\sqrt{6}$ , so the area is $\frac{6\sqrt{3}}{4} = \frac{3\sqrt{3}}{2}$ . QED. ——————– Comment: Slightly difficult if your algebraic intuition wasn’t working well, but after you realized the factorization it wasn’t hard to convince yourself that a line and a point can have the vertices of at most one equilateral triangle. A solid B1 problem on the Putnam, quite a bit more difficult than the A1, imo. ——————– Practice Problem: (2006 Putnam – A1) Find the volume of the region of points such that $(x^2+y^2+z^2+8)^2 \le 36(x^2+y^2)$ . Posted in AIME, Algebra, Polynomials \|\| 3 Comments »
Balance Those p’s. Topic: Algebra/Polynomials/S&S. Level: Olympiad.	November 29th, 2006
Problem: (Stanford Putnam Practice) A finite sequence $a_1, a_2, \ldots, a_n$ is called -balanced if any sum of the form $a_k+a_{k+p}+a_{k+2p}+\cdots$ is the same for $k = 1, 2, \ldots, p$ . Prove that if a sequence with members is -balanced for , then all its members are equal to zero. Solution: Let $P(x) = a_{50}x^{49}+a_{49}x^{48}+\cdots+a_2x+a_1$ . Recall the strategy of isolating certain terms in a polynomial. Denoting $\omega_p$ by the th root of unity, we have $\displaystyle a_1+a_{1+p}+a_{1+2p}+\cdots = \frac{1}{p} \sum_{i=0}^{p-1} P(\omega_p^i)$ because all of the terms will cancel out by the identity $1+\omega_p+\omega_p^2+\cdots+\omega_p^{p-1} = 0$ except for the terms in which the power of the exponent is divisible by , in which case $\omega_p^p = 1$ . Similarly, using the polynomials $xP(x), x^2P(x), \ldots, x^{p-1}P(x)$ we obtain $\displaystyle a_k+a_{k+p}+a_{k+2p}+\cdots = \frac{1}{p} \sum_{i=0}^{p-1} \omega_p^{i(p+1-k)}P(\omega_p^i)$ from $x^{p+1-k}P(x)$ and $k = 2, 3, \ldots, p$ . Hence we have a system of equations in the variables $P(1), P(\omega_p), \ldots, P(\omega_p^{p-1})$ . But if we have a system of equations for , we have a total of equations. Since the only repeated value in the polynomial was and it showed up times, once for each prime, there are distinct points on the polynomial that we now know. However, since a polynomial of degree is defined by at most points, it must be the zero polynomial, which means $a_1 = a_2 = \cdots = a_{50} = 0$ , as desired. QED. ——————– Comment: This is an example of generating functions showing up when you least expect it, well not exactly, but it was cool anyway. The proof above is not completely rigorous because we would need to show that a polynomial of degree actually cannot pass through all of the points, but it’s almost there. ——————– Practice Problem: Let denote the number of ways you can partition into parts. Show that $\displaystyle \sum_{k=1}^n p(n, k) = p(2n, n)$ . Also show that the number of ways can be partitioned into unequal parts is equal to the number of ways can be partitioned into odd parts. Posted in Algebra, Olympiad, Polynomials, Sequences & Series \|\| No Comments »
Square Sum Stuff. Topic: Polynomials/S&S. Level: AMC/AIME.	October 27th, 2006
Problem: Evaluate the summation $\displaystyle \sum_{k=1}^{\infty} \frac{k^2}{2^k} = \frac{1^2}{2^1}+\frac{2^2}{2^2}+\frac{3^2}{2^3}+\frac{4^2}{2^4}+\cdots$ . Solution: Here’s a technique that will help you evaluate infinite series that are of the form polynomial over exponential. It’s based on the idea of finite differences: If is a polynomial with integer coefficients of degree then is a polynomial of degree (not hard to show; just think about it). So let $S = \frac{1^2}{2^1}+\frac{2^2}{2^2}+\frac{3^2}{2^3}+\frac{4^2}{2^4}+\cdots$ . Then consider by simply multiplying each term by : $2S = 1^2+\frac{2^2}{2^1}+\frac{3^2}{2^2}+\frac{4^2}{2^3}+\cdots$ . And now find the difference by subtracting the terms with equal denominators. We get $S = 2S-S = 1+\frac{2^2-1^2}{2^1}+\frac{3^2-2^2}{2^2}+\frac{4^2-3^2}{2^3}+\cdots$ $S = 1+\frac{3}{2^1}+\frac{5}{2^2}+\frac{7}{2^3}+\cdots$ . Notice that the numerator is now a polynomial of degree instead of . Repeating this, we have $2S = 2+3+\frac{5}{2^1}+\frac{7}{2^2}+\cdots$ and $S = 2S-S = 2 + 2 + \frac{5-3}{2^1}+\frac{7-5}{2^2}+\cdots$ $S = 2 + (2 + 1+\frac{1}{2}+\cdots)$ . Notice that the latter part is just a geometric series which sums to $2 + 1 + \frac{1}{2} + \cdots = 4$ so . QED. ——————– Comment: The method of finite differences is extremely useful and is basically a simplified version of calculus – $P(x+1)-P(x) \approx P^{\prime}(x)$ in a very approximating sense. It’s a good thing to know, though, because then you have a better understanding of how polynomials work. ——————– Practice Problem: Let be a polynomial with integer coefficients. Using the method of finite differences, predict the degree of . $P(1) = 1 \mbox{ } P(2) = 9 \mbox{ } P(3) = 20 \mbox{ } P(4) = 36 \mbox{ } P(5) = 59 \mbox{ } P(6) = 91$ . Posted in AIME, AMC, Polynomials, Sequences & Series \|\| 2 Comments »

free web counters