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

Bigger Means Better. Topic: Algebra/Inequalities/Sets. Level: Olympiad.	May 12th, 2007
Definition: A set is said to be convex if, for any $X, Y \in S$ and $\lambda \in [0,1]$ , we have $\lambda X+(1-\lambda)Y \in S$ . ——————– Definition: Let $f: D \rightarrow \mathbb{R}$ be a real-valued function defined on a convex set . We say that is convex if, for all $X, Y \in D$ and $\lambda \in [0, 1]$ , we have $\lambda f(X) + (1-\lambda) f(Y) \ge f(\lambda X+(1-\lambda)Y)$ . ——————– Theorem: (Jensen’s Inequality) Let be a real-valued, convex function defined on a convex set . Given $x_1, x_2, \ldots, x_n \in D$ and nonnegative reals $w_1, w_2, \ldots, w_n$ such that $w_1+w_2+\cdots+w_n = 1$ , we have $w_1f(x_1)+w_2f(x_2)+\cdots+w_nf(x_n) \ge f(w_1x_1+w_2x_2+\cdots+w_nx_n)$ or, more concisely, $\displaystyle \sum_{i=1}^n w_if(x_i) \ge f\left(\sum_{i=1}^n w_ix_i\right)$ . Proof: We proceed by induction on . Base Case – , we have $f(x_1) \ge f(x_1)$ which is trivially true. , we have $\lambda_1 f(x_1)+\lambda_2 f(x_2) \ge f(\lambda_1 x_1+\lambda_2 x_2)$ with $\lambda_1+\lambda_2 = 1$ which is true by the definition of convexity. Induction Step – Suppose $\displaystyle \sum_{i=1}^k w_if(x_i) \ge f\left(\sum_{i=1}^k w_ix_i\right)$ . We wish to show $\displaystyle \sum_{i=1}^{k+1} u_if(x_i) \ge f\left(\sum_{i=1}^{k+1} u_ix_i\right)$ for nonnegative reals $u_1, u_2, \ldots, u_{k+1}$ that sum to . Well, $\displaystyle f\left(\sum_{i=1}^{k+1} u_ix_i\right) \le u_{k+1}f(x_{k+1})+(1-u_{k+1})f\left(\frac{1}{1-u_{k+1}} \sum_{i=1}^k u_ix_i\right)$ by the definition of convexity. But since $\displaystyle \frac{1}{1-u_{k+1}} \sum_{i=1}^k u_i = \sum_{i=1}^k \frac{u_i}{1-u_{k+1}} = 1$ , by our inductive hypothesis (the term case) we must have $\displaystyle f\left(\frac{1}{1-u_{k+1}} \sum_{i=1}^k u_ix_i\right) \le \sum_{i=1}^k \frac{u_i}{1-u_{k+1}} f(x_i)$ . Combining this into the above inequality, we obtain $\displaystyle f\left(\sum_{i=1}^{k+1} u_ix_i\right) \le u_{k+1}f(x_{k+1})+(1-u_{k+1})\sum_{i=1}^k \frac{u_i}{1-u_{k+1}} f(x_i) = \sum_{i=1}^{k+1} u_if(x_i)$ as desired, completing the induction. QED. ——————– Definition: The convex hull of a set is defined to be the smallest convex set containing . It is the set of all points that can be written as $\displaystyle \sum_{i=1}^n a_ix_i$ , where is a natural number, $a_1, a_2, \ldots, a_n$ are nonnegative reals that sum to , and $x_1, x_2, \ldots, x_n \in S$ . ——————– Definition: A vertex of a set is a point $v \in D$ such that for all $x \in D$ not equal to and $\lambda > 1$ we have $\lambda v+(1-\lambda)x \not\in D$ . ——————– Theorem: Let $V_D = \{v_1, v_2, \ldots, v_k\}$ be the set of vertices of a compact convex set . The convex hull of is . Example: The set of vertices of a convex polygon is, in fact, its vertices as traditionally defined in geometry. Any point inside the polygon can be written as a convex combination of its vertices. ——————– Theorem: If is a real-valued, convex function defined on a compact convex set , then $\displaystyle \max_{x \in D} f(x) = \max_{x \in V_D} f(x)$ , where is the set of vertices of . Proof: We will show that $\displaystyle f(x) \le \max_{x \in V_D} f(x)$ for all $x \in D$ . Let $\displaystyle x = \sum_{i=1}^k \lambda_i v_i$ where $\lambda_1, \lambda_2, \ldots, \lambda_k$ are nonnegative reals that sum to and $V_D = \{v_1, v_2, \ldots, v_k\}$ . This is possible by the preceding theorem. Then by Jensen’s Inequality we get $\displaystyle \sum_{i=1}^k \lambda_i f(v_i) \ge f\left(\sum_{i=1}^k \lambda_i v_i\right) = f(x)$ . And since $\displaystyle \max_{x \in V_D} f(x) \ge \sum_{i=1}^k \lambda_i f(v_i)$ , we have $\displaystyle \max_{x \in V_D} f(x) \ge f(x)$ for all $x \in D$ . Furthermore, since is a subset of , we know that this maximum is attained, thus $\displaystyle \max_{x \in D} f(x) = \max_{x \in V_D} f(x)$ as desired. QED. ——————– Comment: This is a very useful result, as it allows us to limit our search for the maximum of a function to its set of vertices, which is usually a considerably smaller set, though it may still be infinite (think sphere). In any case, this works well for constrained optimization problems in which the domain is limited to a polygon, the easiest application of this theorem. ——————– Practice Problem: Let and be real numbers satisfying $\|2x-y\| \le 3$ and $\|y-3x\| \le 1$ . Find the maximum value of . Posted in Algebra, Inequalities, Olympiad, Sets \|\| 3 Comments »
Fishy Triangular Number. Topic: Inequalities. Level: AIME.	April 12th, 2007
Problem: (2001 Poland Finals – #1) Prove the following inequality: $x_1+2x_2+3x_3+\cdots+nx_n \le \frac{n(n-1)}{2}+x_1+x_2^2+x_3^3+\cdots+x_n^n$ where are positive reals. Solution: Like the title says, that triangular number looks really fishy… let’s write it as $1+2+\cdots+(n-1)$ and pair up the terms on the RHS. $\frac{n(n-1)}{2}+x_1+x_2^2+x_3^3+\cdots+x_n^n = x_1+(x_2^2+1)+(x_3^3+2)+\cdots+(x_n^n+n-1)$ . We claim that $x_i^i+i-1 \ge ix_i$ for $i = 1, 2, \ldots, n$ . We’ll use our good friend AM-GM to show this; in fact, it is quite simple. $\frac{x_i+1+1+\cdots+1 \text{(i-1 times)}}{i} \ge \sqrt[i]{x_i^i} = x_i$ so $x_i^i+i-1 \ge ix_i$ as desired. Sum them up to get our inequality. QED. ——————– Comment: Just a clever little application of AM-GM; apparantly not a strong inequality at all, and the only equality case is for all . Nevertheless, slightly on the tricky side which makes it sufficiently satisfying to solve. ——————– Practice Problem: (2006 Poland Finals – #1) Solve in reals: . Posted in AIME, Inequalities \|\| 4 Comments »
Hey Now. Topic: Inequalities. Level: AIME.	March 26th, 2007
Problem: Let be positive reals such that . Prove that $\sqrt{a}+\sqrt{b}+\sqrt{c} \ge ab+bc+ca$ . Solution: We play around and guess that $\sqrt{a} \ge \frac{ab+ac}{2}$ because that would be convenient. Indeed, replacing with , this is equivalent to $\sqrt{a} \ge \frac{a(3-a)}{2} \Leftrightarrow 4a \ge a^2(3-a)^2 \Leftrightarrow (a-1)^2(4-a) \ge 0$ , which is clearly true for . So we get the three inequalities $\sqrt{a} \ge \frac{ab+ac}{2}$ , $\sqrt{b} \ge \frac{bc+ba}{2}$ , $\sqrt{c} \ge \frac{ca+cb}{2}$ . Adding them up, we have the desired $\sqrt{a}+\sqrt{b}+\sqrt{c} \ge ab+bc+ca$ . QED. ——————– Comment: I found this solution to be pretty clever, as the initial “guess” is not trivially true. But the whole thing works out quite nicely with symmetry so it’s all good. Inequality problems usually require several random ideas and inspiration before finding the crux step. ——————– Practice Problem: Let be positive reals such that . Prove that $(a+b)(b+c)(c+a) \ge 2(1+a+b+c)$ . Posted in AIME, Inequalities \|\| 2 Comments »
Return Of The Triangle. Topic: Geometry/Inequalities/Trigonometry. Level: AIME.	February 11th, 2007
Problem: (1961 IMO – #2) Let be the sides of a triangle, and its area. Prove: $a^2+b^2+c^2 \ge 4T\sqrt{3}$ . In what case does equality hold? Solution: We begin with the trivial inequality, $(a-b)^2 \ge 0$ , which has equality at . Rearrange to get $a^2+b^2 \ge 2ab$ . Let $\theta$ be the angle between the sides with lengths . Since $2 \ge \cos{\theta}+\sqrt{3}\sin{\theta}$ (can be proved by combining RHS) with equality at $\theta = \frac{\pi}{3}$ , we know $a^2+b^2 \ge ab(\cos{\theta}+\sqrt{3}\sin{\theta})$ $2(a^2+b^2) \ge 2ab(\cos{\theta}+\sqrt{3}\sin{\theta})$ $a^2+b^2+(a^2+b^2-2ab\cos{\theta}) \ge 2\sqrt{3} \cdot ab\sin{\theta}$ . Recalling the Law of Cosines, we know $c^2 = a^2+b^2-2ab\cos{\theta}$ . Also, $T = \frac{1}{2}ab\sin{\theta}$ , so substituting we obtain $a^2+b^2+c^2 \ge 4T\sqrt{3}$ as desired. Equality holds when and $\theta = \frac{\pi}{3}$ , which means the triangle must be equilateral. QED. ——————– Comment: There are lots of ways to prove this, but this is one of the more elementary ones, requiring only basic knowledge of inequalities and trigonometry. Which is always good because I don’t know any geometry. We see that this inequality is in general pretty weak, with equality only when the triangle is equilateral – there is a stronger version that states $a^2+b^2+c^2 \ge 4T\sqrt{3}+(a-b)^2+(b-c)^2+(c-a)^2$ . See if you can prove that… ——————– Practice Problem: Let be the sides of a triangle, and its area. Prove: $a^2+b^2+c^2 \ge 4T\sqrt{3}+(a-b)^2+(b-c)^2+(c-a)^2$ . Posted in AIME, Geometry, Inequalities, Trigonometry \|\| 4 Comments »
Log Rolling. Topic: Inequalities. Level: AIME.	January 24th, 2007
Problem: Given reals $a, b, c \ge 2$ , show that $\log_{a+b}(c)+\log_{b+c}(a)+\log_{c+a}(b) \ge \frac{3}{2}$ . Solution: Recall the change-of-base identity for logs. We can rewrite the LHS as $\frac{\log{c}}{\log{(a+b)}}+\frac{\log{a}}{\log{(b+c)}}+\frac{\log{b}}{\log{(c+a)}}$ . Note, however that $(a-1)(b-1) \ge 1 \Rightarrow ab \ge a+b \Rightarrow \log{a}+\log{b} = \log{(ab)} \ge \log{(a+b)}$ , so it remains to show that $\frac{\log{c}}{\log{a}+\log{b}}+\frac{\log{a}}{\log{b}+\log{c}}+\frac{\log{b}}{\log{c}+\log{a}} \ge \frac{3}{2}$ , which is true by Nesbitt’s Inequality. QED. ——————– Comment: A good exercise in using log identities and properties to achieve a relatively simple result. Once we made the change-of-base substitution, seeing the $\frac{3}{2}$ should clue you in to Nesbitt’s. That led to the inequality $\log{a}+\log{b} \ge \log{(a+b)}$ , which was easily proven given the conditions of the problem. ——————– Practice Problem: Given reals $a, b, c \ge 2$ , find the best constant such that $\log_{a+b+c}(a)+\log_{a+b+c}(b)+\log_{a+b+c}(c) \ge k$ . Posted in AIME, Inequalities \|\| 3 Comments »

free web counters