Olympiad Inequalities

Olympiad Inequalities-Free PDF

  • Date:27 Jan 2020
  • Views:99
  • Downloads:4
  • Pages:34
  • Size:291.85 KB

Share Pdf : Olympiad Inequalities

Download and Preview : Olympiad Inequalities


Report CopyRight/DMCA Form For : Olympiad Inequalities


Transcription:

1 The Standard Dozen, Throughout this lecture we refer to convex and concave functions Write I and I 0 for the. intervals a b and a b respectively A function f is said to be convex on I if and only if. f x 1 f y f x 1 y for all x y I and 0 1 Conversely if the. inequality always holds in the opposite direction the function is said to be concave on the. interval A function f that is continuous on I and twice differentiable on I 0 is convex on I. if and only if f 00 x 0 for all x I Concave if the inequality is flipped. Let x1 x2 xn y1 y2 yn be two sequences of real numbers If. x1 xk y1 yk for k 1 2 n with equality where k n then the sequence. xi is said to majorize the sequence yi An equivalent criterion is that for all real numbers. t x1 t x2 t xn t y1 t y2 t yn, We use these definitions to introduce some famous inequalities. Theorem 1 Jensen Let f I R be a convex function Then for any x1 xn I. and any nonnegative reals 1 n,1 f x1 n f xn 1 n f,If f is concave then the inequality is flipped. Theorem 2 Weighted Power Mean If x1 xn are nonnegative reals and 1 n. are nonnegative reals with a postive sum then,1 xr1 n xrn r. is a non decreasing function of r with the convention that r 0 is the weighted geometric. mean f is strictly increasing unless all the xi are equal except possibly for r 0. where if some xi is zero f is identically 0 In particular f 1 f 0 f 1 gives the. AM GM HM inequality, Theorem 3 Ho lder Let a1 an b1 bn z1 zn be sequences of nonnegative.
real numbers and let a b z positive reals which sum to 1 Then. a1 an a b1 bn b z1 zn z a 1 a b 1 b z1 z a nz b nb zn z. This theorem is customarily identified as Cauchy when there are just two sequences. Theorem 4 Rearrangement Let a1 a2 an and b1 b2 bn be two. nondecreasing sequences of real numbers Then for any permutation of 1 2 n we. a1 b1 a2 b2 an bn a1 b 1 a2 b 2 an b n a1 bn a2 bn 1 an b1. with equality on the left and right holding if and only if the sequence 1 n is de. creasing and increasing respectively, Theorem 5 Chebyshev Let a1 a2 an b1 b2 bn be two nondecreas. ing sequences of real numbers Then, a1 b1 a2 b2 an bn a1 a2 an b1 b2 bn a1 bn a2 bn 1 an b1. Theorem 6 Schur Let a b c be nonnegative reals and r 0 Then. ar a b a c br b c b a cr c a c b 0, with equality if and only if a b c or some two of a b c are equal and the other is 0. Remark This can be improved considerably See the problems section However they. are not as well known as of now as this form of Schur and so should be proven whenever. used on a contest, Theorem 7 Newton Let x1 xn be nonnegative real numbers Define the symmetric. polynomials s0 s1 sn by x x1 x,x2 x xn sn x s1 x s0 and define.
the symmetric averages by di si i Then,d2i di 1 di 1. Theorem 8 Maclaurin Let di be defined as above Then. d1 d2 3 d3 n dn, Theorem 9 Majorization Let f I R be a convex on I and suppose that the sequence. x1 xn majorizes the sequence y1 yn where xi yi I Then. f x1 f xn f y1 f yn, Theorem 10 Popoviciu Let f I R be convex on I and let x y z I Then for any. positive reals p q r,pf x qf y rf z p q r f,px qy qy rz rz px. p q f q r f r p f,p q q r r p,Theorem 11 Bernoulli For all r 1 and x 1.
1 x r 1 xr, Theorem 12 Muirhead Suppose the sequence a1 an majorizes the sequence b1 bn. Then for any positive reals x1 xn,xa11 xa22 xann xb11 xb22 xbnn. where the sums are taken over all permutations of n variables. Remark Although Muirhead s theorem is a named theorem it is generally not favor. ably regarded as part of a formal olympiad solution Essentially the majorization criterion. guarantees that Muirhead s inequality can be deduced from a suitable application of AM GM. Hence whenever possible you should use Muirhead s inequality only to deduce the correct. relationship and then explicitly write all of the necessary applications of AM GM For a. particular case this is a simple matter, We now present an array of problems and solutions based primarily on these inequalities. 2 Examples, When solving any kind of problem we should always look for a comparatively easy solu. tion first and only later try medium or hard approaches Although what constitutes this. notoriously indeterminate difficulty varies widely from person to person I usually con. sider Dumbassing AM GM Power Mean Cauchy Chebyshev Rearrangement Jensen. Ho lder in that order before moving to more clever techniques The first technique is de. scribed in remarks after example 1 Weak inequalities will fall to AM GM which blatantly. pins a sum to its smallest term Weighted Jensen and Ho lder are smarter in that the effect. of widely unequal terms does not cost a large degree of sharpness6 observe what happens. when a weight of 0 appears Especially sharp inequalities may be assailable only through. clever algebra, Anyway I have arranged the following with that in mind.
1 Show that for positive reals a b c,a b b2 c c2 a ab2 bc2 ca2 9a2 b2 c2. Solution 1 Simply use AM GM on the terms within each factor obtaining. a b b c c a ab bc ca 3 a b c 3 3 3 a b c 9a2 b2 c2. The sharpness of an inequality generally refers to the extent to which the two sides mimic each other. particularly near equality cases, Solution 2 Rearrange the terms of each factor and apply Cauchy. a b b2 c c2 a bc2 ca2 ab2 a3 b3 c3 a3 b3 c3 a3 b3 c3 9a2 b2 c2. Solution 3 Expand the left hand side then apply AM GM obtaining. a b b2 c c2 a ab2 bc2 ca2 a3 b3 a2 b2 c2 a4 bc,ab4 c b3 c3 a2 b2 c2. a2 b2 c2 abc4 a3 c3,9 a18 b18 c18 9a2 b2 c2, We knew this solution existed by Muirhead since 4 1 1 3 3 0 and 2 2 2 all. majorize 2 2 2 The strategy of multiplying out all polynomial expressions and ap. plying AM GM in conjunction with Schur is generally knowing as dumbassing because. it requires only the calculational fortitude to compute polynomial products and no real. ingenuity As we shall see dumbassing is a valuable technique We also remark that. the AM GM combining all of the terms together was a particularly weak inequality but. the desired was a multiple of a2 b2 c2 s the smallest 6th degree symmetric polynomial. of three variables such a singular AM GM may not always suffice. 2 Let a b c be positive reals such that abc 1 Prove that. a b c a 2 b2 c2, Solution First we homogenize the inequality that is apply the constraint so as.
to make all terms of the same degree Once an inequality is homogenous in degree. d we may scale all of the variables by an arbitrary factor of k causing both sides. of the inequality to scale by the factor k d This is valid in that it does not change. the correctness of an inequality for any positive k and if d is even for any nonzero. k Hence we need consider a nonhomogenous constraint no futher In this case we. multiply the left hand side by 3 abc obtaining,4 1 1 1 4 1 1 1 4. a 3 b 3 c 3 a 3 b 3 c 3 a 3 b 3 c 3 a2 b2 c2, As abc 1 is not homogenous the above inequality must be true for all nonnegative. a b c As 2 0 0 majorizes 4 3 1 3 1 3 we know it is true and the necessary. 2a2 b2 c2 a2 a2 a2 a2 b2 c2,a8 b2 c2 a 3 b 3 c 3, 3 Let P x be a polynomial with positive coefficients Prove that if. holds for x 1 then it holds for all x 0, Solution Let P x an xn an 1 xn 1 a1 x a0 The first thing we notice. that the given is P 1 1 Hence the natural strategy is to combine P x and P x1. into P 1 in some fashion The best way to accomplish this is Cauchy which gives. P x P an x a1 x a0 an n a1 a0,an a1 a0 2 P 1 2 1, as desired This illustrates a useful means of eliminating denominators by introducing.
similar factors weighted by reciprocals and applying Cauchy Ho lder. 4 USAMO 78 1 a b c d e are real numbers such that,a b c d e 8. a b2 c2 d2 e2 16,What is the largest possible value of e. Solution Observe that the givens can be effectively combined by considering squares. a r 2 b r 2 c r 2 d r 2 e r 2 a2 b2 c2 d2 e2,2r a b c d e 5r2. 16 16r 5r2, Since these squares are nonnegative e 5r2 16r 16 r f r for all r Since. equality e f r can be achieved when a b c d r we need only compute the. smallest value f r Since f grows large at either infinity the minimum occurs when. f 0 r 1 2 5r10r 16 6, 2 16r 16 0 The resultant quadratic is easily solved for r 5 and.
r 2 with the latter being an extraneous root introduced by squaring The largest. possible e and greatest lower bound of f r is then f 6 5 16 5 which occurs when. a b c d 6 5 and e 16 5 Alternatively proceed as before except write. a b c d 8 e 4, since the maximum e must occur when the other four variables. are equal The second condition becomes a quadratic and the largest solution is seen. to be e 165, The notion of equating a b c d is closely related to the idea of smoothing and Jensen s. inequality If we are working with S1 f x1 f xn under the constraint of a. fixed sum x1 xn we can decrease S1 by moving several xi in the same interval. I together that is replacing xi1 xi2 with x0i1 xi1 xi2 x0i2 for any. sufficiently small for any I where f is convex S1 can also be decreased by spreading. xi in the same interval where f is concave When seeking the maximum of S1 we. proceed in the opposite fashion pushing xi on the concave intervals of f together and. moving xi on the convex intervals apart,5 Show that for all positive reals a b c d. 1 1 4 16 64,a b c d a b c d, Upon noticing that the numerators are all squares with 1 1 4. 16 64 Cauchy should seem a natural choice Indeed multiplying through by. a b c d and applying Cauchy we have,1 12 22 42,a b c d 1 1 2 4 2 64.
as desired, 6 USAMO 80 5 Show that for all non negative reals a b c 1. 1 a 1 b 1 c 1,b c 1 c a 1 a b 1, Solution Let f a b c denote the left hand side of the inequality Since a 2f. a b 1 3 0 we have that f is convex in each of the three variables hence. the maximum must occur where a b c 0 1 Since f is 1 at each of these 8 points. the inequality follows, Second derivative testing for convexity concavity is one of the few places where the. use of Calculus is not seriously loathed by olympiad graders It is one of the standard. techniques in inequalities and deserves to be in any mental checklist of inequality. solving In this instance it led to an easy solution. 7 USAMO 77 5 If a b c d e are positive reals bounded by p and q with 0 p q. prove that,1 1 1 1 1 p q,a b c d e 25 6,a b c d e q p. and determine when equality holds, Solution As a function f of five variables the left hand side is convex in each of.
a b c d e hence its maximum must occur when a b c d e p q When all five. variables are p or all five are q f is 25 If one is p and the other four are q or vice. versa f becomes 17 4 pq pq and when three are of one value and two of the other. f 13 6 pq pq pq pq 2 with equality if and only if p q Clearly equality. holds where p q Otherwise the largest value assumed by f is 13 6 pq pq which. is obtained only when two of a b c d e are p and the other three are q or vice versa. In such instances f is identically the right hand side. This is a particular case of the Schweitzer inequality which in its weighted form is. sometimes known as the Kantorovich inequality, 8 a b c are non negative reals such that a b c 1 Prove that. a3 b3 c3 6abc, Solution Multiplying by 4 and homogenizing we seek. 4a3 4b3 4c3 24abc a b c 3,a3 b3 c3 3 a2 b c b2 c a c2 a b 6abc. a3 b3 c3 6abc a2 b c b2 c a c2 a b, Recalling that Schur s inequality gives a3 b3 c3 3abc a2 b c b2 c a c2 a b. the inequality follows In particular equality necessitates that the extra 3abc on the. left is 0 Combined with the equality condition of Schur we have equality where two. of a b c are 12 and the third is 0 This is a typical dumbass solution. Solution 2 Without loss of generality take a b c As a b c 1 we have c 31. or 1 3c 0 Write the left hand side as a b 3 3ab a b 2c a b 3 3ab 1 3c. This is minimized for a fixed sum a b where ab is made as large as possible As by. AM GM a b 2 4ab this minimum occurs if and only if a b Hence we need only. consider the one variable inequality 2 1 c 2,c 41 9c3 9c2 3c 1.
Since c 13 3c 9c2 Dropping this term and 9c3 the inequality follows Particularly. 9c3 0 if and only if c 0 and the equality cases are when two variables are 12 and. the third is 0, 9 IMO 74 5 If a b c d are positive reals then determine the possible values of. a b d b c a b c d a c d, Solution We can obtain any real value in 1 2 The lower bound is approached by. a b d a and c 1 The upper bound is approached by a c. b d 1 As the expression is a continuous function of the variables we can obtain. all of the values in between these bounds Finally these bounds are strict because. a b d b c a b c d a c d,a b c d a b c d a b c d a b c d. a b d b c a b c d a c d,a b a b c d c d, Whenever extrema occur for unusual parameterizations we should expect the need for. non classical inequalities such as those of this problem where terms were completely. 10 IMO 95 2 a b c are positive reals with abc 1 Prove that. a3 b c b c a c a b 2, Solution 1 Let x a1 y 1b and z 1c We perform this substitution to move terms.
out of the denominator Since abc xyz 1 we have,1 1 1 x2 y2 z2. a3 b c b3 c a c3 a b y z x z x y,Now multiplying through by x y y z z x we seek. x4 y 4 z 4 x3 y x3 z y 3 z xy 3 xz 3 yz 3 x2 yz xy 2 z xyz 2. 3 2 2 2 2 2 2,xyz 3xyz x y x z y x xy xz yz, which follows immediately by AM GM since x2 yz xy 2 z xyz 2 3 3 x4 y 4 z 4 x y xy3 x z. Olympiad Inequalities Thomas J Mildorf December 22 2005 It is the purpose of this document to familiarize the reader with a wide range of theorems and techniques that can be used to solve inequalities of the variety typically appearing on mathematical olympiads or other elementary proof contests The Standard Dozen is an

Related Books