# Mathematical Food for Thought

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

• ## Meta

 Bigger Means Better. Topic: Algebra/Inequalities/Sets. Level: Olympiad. May 12th, 2007 Definition: A set is said to be convex if, for any and , we have . ——————– Definition: Let be a real-valued function defined on a convex set . We say that is convex if, for all and , we have . ——————– Theorem: (Jensen’s Inequality) Let be a real-valued, convex function defined on a convex set . Given and nonnegative reals such that , we have or, more concisely, . Proof: We proceed by induction on . Base Case – , we have which is trivially true. , we have with which is true by the definition of convexity. Induction Step – Suppose . We wish to show for nonnegative reals that sum to . Well, by the definition of convexity. But since , by our inductive hypothesis (the term case) we must have . Combining this into the above inequality, we obtain 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 , where is a natural number, are nonnegative reals that sum to , and . ——————– Definition: A vertex of a set is a point such that for all not equal to and we have . ——————– Theorem: Let 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 , where is the set of vertices of . Proof: We will show that for all . Let where are nonnegative reals that sum to and . This is possible by the preceding theorem. Then by Jensen’s Inequality we get . And since , we have for all . Furthermore, since is a subset of , we know that this maximum is attained, thus 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 and . 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: where are positive reals. Solution: Like the title says, that triangular number looks really fishy… let’s write it as and pair up the terms on the RHS. . We claim that for . We’ll use our good friend AM-GM to show this; in fact, it is quite simple. so 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 . Solution: We play around and guess that because that would be convenient. Indeed, replacing with , this is equivalent to , which is clearly true for . So we get the three inequalities , , . Adding them up, we have the desired . 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 . 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: . In what case does equality hold? Solution: We begin with the trivial inequality, , which has equality at . Rearrange to get . Let be the angle between the sides with lengths . Since (can be proved by combining RHS) with equality at , we know . Recalling the Law of Cosines, we know . Also, , so substituting we obtain as desired. Equality holds when and , 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 . See if you can prove that… ——————– Practice Problem: Let be the sides of a triangle, and its area. Prove: . Posted in AIME, Geometry, Inequalities, Trigonometry || 4 Comments » Log Rolling. Topic: Inequalities. Level: AIME. January 24th, 2007 Problem: Given reals , show that . Solution: Recall the change-of-base identity for logs. We can rewrite the LHS as . Note, however that , so it remains to show that , 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 should clue you in to Nesbitt’s. That led to the inequality , which was easily proven given the conditions of the problem. ——————– Practice Problem: Given reals , find the best constant such that . Posted in AIME, Inequalities || 3 Comments »