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

Inequalities Revisited. Topic: Inequalities. Level: Olympiad.	November 30th, 2005
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 such that , 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 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 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 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 . 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 and positive reals . Practice Problem #3: Given positive reals , 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}$ . Posted in Inequalities, Olympiad \|\| 4 Comments »
Add Them Up. Topic: Sequences & Series. Level: AIME/Olympiad.	November 29th, 2005
Problem: (1989 USAMO – #1) For each positive integer , 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 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 as sum of the following sequences: $S_2 = 1+\frac{1}{2}$ ... $S_n = 1+\frac{1}{2}+ \cdots +\frac{1}{n}$ . Notice that appears times, $\frac{1}{2}$ appears times, and more generally $\frac{1}{i}$ appears 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 . 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 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 . 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 . Posted in AIME, Algebra, Olympiad, Sequences & Series \|\| 2 Comments »
Circular Reasoning. Topic: Geometry. Level: AMC/AIME.	November 27th, 2005
Problem #1: (2006 Mock AIME 1 – #1) 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 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 . 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 . Let point 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 (first assume ) – we then have the other length . Now think about the possibilities… we want to maintain 1. The minimum distance of . So the arc has to be greater than – . 2. The “center” status of . So the arc has to be greater than so $AC < \frac{1-x}{2}$ for a given . Also, must be less than (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 is on the -axis and is on the -axis following these rules: $0 < AB < \frac{1}{3}$ and $AB < AC < \frac{1-AB}{2}$ . (2) Now recall that we assumed . But could be as well, so we apply the same argument, flipping and . But the graph would be the same, only flipped over the line , 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 we automatically show that our maximum arc length is because it is always greater than the independent lengths ( and – of course this is only when and 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 , $\angle A = 30^{\circ}$ . is the orthocenter and is the midpoint of . On the line , take point such that . Show that . (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 . What is the length of the arc along the bigger circle containing all the points that are within 2 units of ? Posted in AIME, AMC, Geometry \|\| No Comments »
Combina-WHAT? Topic: Combinatorics. Level: AMC/AIME.	November 26th, 2005
Problem #1: Prove that $nC0+nC1+\cdots+nCn = 2^n$ ( denotes choose ). 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 -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 , 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 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 . Practice Problem #3: (1983 AIME #8) Find the largest two-digit prime that divides . Posted in AIME, AMC, Probability & Combinatorics \|\| 6 Comments »
Mix it Up. Topic: Polynomials/Inequalities. Level: Olympiad.	November 25th, 2005
Problem #1: (ACoPS 5.5.22) Let be a polynomial with positive coefficients. Prove that if $P\left(\frac{1}{x}\right) \ge \frac{1}{P(x)}$ holds for then it holds for every . 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 cannot all be real if . 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 with real coefficients, find the condition the polynomial must satisfy such that it has at least one nonreal root (based on ). 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 has real zeros iff $\frac{a_1}{b_1} = \frac{a_2}{b_2} = \cdots = \frac{a_n}{b_n}$ . Posted in Inequalities, Olympiad, Polynomials \|\| 4 Comments »

free web counters