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

Mass Production. Topic: Inequalities. Level: Olympiad.	February 28th, 2006
Problem: (2000 IMO – #2) Let be positive real numbers so that . Prove that $\left( a-1+\frac 1b \right) \left( b-1+\frac 1c \right) \left( c-1+\frac 1a \right) \leq 1$ . Solution: The standard trick to solve the condition is to substitute $a = \frac{x}{y}$ , $b = \frac{y}{z}$ , $c = \frac{z}{x}$ for positive reals (their existence is guaranteed since it’s a three-variable system with three equations). Our inequality reduces to $\left(\frac{x+z-y}{y}\right)\left(\frac{y+x-z}{z}\right)\left(\frac{z+y-x}{x}\right) \le 1$ . Multiplying through by , expanding, and rearranging everything to the RHS, we have $0 \le x^3+y^3+z^3-x^2y-x^2z-y^2z-y^2x-z^2x-z^2y+3xyz$ or $0 \le x(x-y)(x-z)+y(y-z)(y-x)+z(z-x)(z-y)$ , which is just Schur’s Inequality, so the result is proved. QED. ——————– Comment: The condition almost always calls for the substitution above. It also works with $abc \ge 1$ in which case you simply have another variable multiplied by each of the terms. ——————– Practice Problem: Go take the 2006 Mock AIME 5 below. Posted in Inequalities, Olympiad \|\| No Comments »
Legend of Max. Topic: Inequalities. Level: Olympiad.	February 27th, 2006
Problem: (1999 USAMO – #4) Let $a_{1}, a_{2}, \ldots, a_{n}$ () be real numbers such that $a_{1} + a_{2} + \cdots + a_{n} \geq n \qquad$ and $\qquad a_{1}^{2} + a_{2}^{2} + \cdots + a_{n}^{2} \geq n^{2}$ . Prove that $\max(a_{1}, a_{2}, \ldots, a_{n}) \geq 2$ . Solution: To simply things, let . We wish to show that there exists an $x_i \le 0$ . Our conditions become $(2-x_1)+(2-x_2)+\cdots+(2-x_n) \ge n \Rightarrow x_1+x_2+\cdots+x_n \le n$ . $(2-x_1)^2+(2-x_2^2)+\cdots+(2-x_n)^2 \ge n^2$ . Assume for the sake of contradiction that for all and let $x_1+x_2+\cdots+x_n = k \le n$ . We have $(2-x_1)^2+(2-x_2)^2+\cdots+(2-x_n^2) = (x_1^2+x_2^2+\cdots+x_n^2) – 4(x_1+x_2+\cdots+x_n)+4n \ge n^2$ , or $(x_1^2+x_2^2+\cdots+x_n^2) – 4(x_1+x_2+\cdots+x_n) \ge n^2-4n$ . But we have $x_1^2+x_2^2+\cdots+x_n^2 < (x_1+x_2+\cdots+x_n)^2 = k^2$ , so $(x_1^2+x_2^2+\cdots+x_n^2) - 4(x_1+x_2+\cdots+x_n) < k^2-4k$ . However, since $n \ge k$ and $n \ge 4$ , we have $n^2-4n \ge k^2-4k$ (looking at the parabola it is easy to see; has zeros at ). Therefore $(x_1^2+x_2^2+\cdots+x_n^2) - 4(x_1+x_2+\cdots+x_n) < k^2-4k \le n^2-4n$ . But we also had $(x_1^2+x_2^2+\cdots+x_n^2) - 4(x_1+x_2+\cdots+x_n) \ge n^2-4n$ , so that gives us a contradiction. Hence our assumption must be false and there exists an $x_i \le 0 \Rightarrow a_i \ge 2$ as desired. QED. -------------------- Comment: This wasn't a particularly difficult inequality, but it has some key ideas. Using all parts of the question is important (in this case is actually relevant). Another note is that this didn’t really require any of the classical inequalities, just algebraic manipulation. Lastly, the crucial step was setting converting the real to positive which makes things a whole lot nicer. ——————– Practice Problem: Go take the 2006 Mock AIME 5 below. Posted in Inequalities, Olympiad \|\| No Comments »
2006 Mock AIME 5.	February 27th, 2006
Here’s the 2006 Mock AIME 5, prepared by me. Rules are the same as usual, go to AoPS if you want to discuss the problems. 3 hours, no calculators, all answers are integers from 000-999, inclusive. Have fun! 2006 Mock AIME 5 Posted in AIME \|\| No Comments »
Linkage. Topic: NT/Sequences and Series. Level: Olympiad.	February 26th, 2006
Problem: (2002 USAMO – #5) Let be integers greater than . Prove that there exists a positive integer and a finite sequence $n_1, n_2, \ldots, n_k$ of positive integers such that , and $n_i n_{i+1}$ is divisible by $n_i + n_{i+1}$ for each ( $1 \leq i < k$ ). Solution: Call two integers and "linked" if there exists a sequence as described in the question (note that two integers are always mutually linked; just reverse the sequence). We wish to show that all integers are linked. If we can show that and are linked for any integer in a finite number of terms (links), the problem is solved. Consider the following sequence: , , , , , , , , which can easily be shown to satisfy the property in the question. Thus and are always linked for . Hence, by induction, any integers are linked (assuming WLOG , we have linked to , then , etc.), as desired. QED. ——————– Comment: The proof of this, when presented, is very short. In actuality, this problem took quite a while to solve; first to figure out to try and link consecutive integers and then to actually find the link. Playing around with the numbers eventually gave the right sequence. Posted in Number Theory, Olympiad, Sequences & Series \|\| No Comments »
Power Hungry. Topic: NT/Sequences and Series. Level: Olympiad.	February 25th, 2006
Problem: (2005 IMO – #4) Determine all positive integers relatively prime to all the terms of the infinite sequence $a_n=2^n+3^n+6^n -1,\ n\geq 1$ . Solution: We claim that the only such integer is . Consider any prime and the term $a_{p-2}$ . We have $a_{p-2} = 2^{p-2}+3^{p-2}+6^{p-2}-1 = \frac{2^{p-1}}{2}+\frac{3^{p-1}}{3}+\frac{6^{p-1}}{6}-1$ , which, by taking a common denominator and factoring, becomes $a_{p-2} = \frac{(2^{p-1}+2)(3^{p-1}+3)-12}{6}$ . But by Fermat’s Little Theorem, we have $2^{p-1} \equiv 3^{p-1} \equiv 1 \pmod{p}$ , so $a_{p-2} \equiv \frac{(1+2)(1+3)-12}{6} \equiv 0 \pmod{p}$ . So we have shown that $p\|a_{p-2}$ for all primes . Noting that , which is divisible by both and , we have that every positive integer divisible by a prime is not relatively prime to all terms in the sequence (since at least one term is divisible by every prime). Hence the only possible number is , as claimed. QED. ——————– Comment: The quickest way to find this solution was seeing that $\frac{1}{2}+\frac{1}{3}+\frac{1}{6}-1 = 0$ . And since multiplicative inverses always exist modulo a prime, the term $a_{p-2}$ is divisible by . Posted in Number Theory, Olympiad, Sequences & Series \|\| No Comments »

free web counters