mathematical olympiad treasures pdf free download

• 9,358,873 books books
• 84,837,646 articles articles
• ZLibrary Home
• Home

Main Mathematical Olympiad Treasures

Mathematical Olympiad Treasures

Titu Andreescu, Bogdan Enescu (auth.)

How much do you like this book?

What's the quality of the file?

Download the book for quality assessment

What's the quality of the downloaded files?

This second edition of Mathematical Olympiad Treasures contains a stimulating collection of problems in geometry and trigonometry, algebra, number theory, and combinatorics. It encourages readers to think creatively about techniques and strategies for solving real-world problems, with new sections, revisions, and many more Olympiad-like problems at various levels of difficulty.

The problems are clustered by topic into three self-contained chapters. The book begins with elementary facts, followed by carefully selected problems and detailed, step-by-step solutions, which then lead to more complicated, challenging problems and their solutions. Reflecting the vast experience of two professors and Mathematical Olympiad coaches, the text will be invaluable to teachers, students, and puzzle enthusiasts. The advanced reader is challenged to find alternative solutions and extensions of the proposed problems.

Publisher:

Birkhäuser Basel

The file will be sent to your email address. It may take up to 1-5 minutes before you receive it.

The file will be sent to your Kindle account. It may takes up to 1-5 minutes before you received it.

Please note: you need to verify every book you want to send to your Kindle. Check your mailbox for the verification email from Amazon Kindle.

You may be interested in Powered by Rec2Me

Most frequently terms

                Titu Andreescu  Bogdan Enescu  Mathematical Olympiad Treasures Second Edition  Titu Andreescu School of Natural Sciences and Mathematics University of Texas at Dallas Richardson, TX 75080 USA titu.andreescu@utdallas.edu  Bogdan Enescu Department of Mathematics "BP Hasdeu" National College Buzau 120218 Romania bogdanenescu@buzau.ro  ISBN 978-0-8176-8252-1 e-ISBN 978-0-8176-8253-8 DOI 10.1007/978-0-8176-8253-8 Springer New York Dordrecht Heidelberg London Library of Congress Control Number: 2011938426 Mathematics Subject Classification (2010): 00A05, 00A07, 05-XX, 11-XX, 51-XX, 97U40 © Springer Science+Business Media, LLC 2004, 2011 All rights reserved. This work may not be translated or copied in whole or in part without the written permission of the publisher (Springer Science+Business Media, LLC, 233 Spring Street, New York, NY 10013, USA), except for brief excerpts in connection with reviews or scholarly analysis. Use in connection with any form of information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology now known or hereafter developed is forbidden. The use in this publication of trade names, trademarks, service marks, and similar terms, even if they are not identified as such, is not to be taken as an expression of opinion as to whether or not they are subject to proprietary rights. Printed on acid-free paper Springer is part of Springer Science+Business Media (www.birkhauser-science.com)  Preface  Mathematical Olympiads have a tradition longer than one hundred years. The first mathematical competitions were organized in Eastern Europe (Hungary and Romania) by the end of the 19th century. In 1959 the first International Mathematical Olympiad was held in Romania. Seven countries, with a total of 52 students, attended that contest. In 2010, the IMO was held in Kazakhstan. The number of participating countries was 97, and the number of students 517. Obviously, the number of young students interested in mathematics and mathematical competitio; ns is nowadays greater than ever. It is sufficient to visit some mathematical forums on the net to see that there are tens of thousands registered users and millions of posts. When we were thinking about writing this book, we asked ourselves to whom it will be addressed. Should it be the beginner student, who is making the first steps in discovering the beauty of mathematical problems, or, maybe, the more advanced reader, already trained in competitions. Or, why not, the teacher who wants to use a good set of problems in helping his/her students prepare for mathematical contests. We have decided to take the hard way and have in mind all these potential readers. Thus, we have selected Olympiad problems of various levels of difficulty. Some are rather easy, but definitely not exercises; some are quite difficult, being a challenge even for Olympiad experts. Most of the problems come from various mathematical competitions (the International Mathematical Olympiad, The Tournament of the Towns, national Olympiads, regional Olympiads). Some problems were created by the authors and some are folklore. The problems are grouped in three chapters: Algebra, Geometry and Trigonometry, and Number Theory and Combinatorics. This is the way problems are classified at the International Mathematical Olympiad. In each chapter, the problems are clustered by topic into self-contained sections. Each section begins with elementary facts, followed by a number of carefully selected problems and an extensive discussion of their solutions. At the end of each section the reader will find a number of proposed problems, whose complete solutions are presented in the second part of the book. v  vi  Preface  We encourage the beginning reader to carefully examine the problems solved at the beginning of each section and try to solve the proposed problems before examining the solutions provided at the end of the book. As for the advanced reader, our advice is to try finding alternative solutions and generalizations of the proposed problems. In the second edition of the book, we added two new sections in Chaps. 1 and 3, and more than 60 new problems with complete solutions. University of Texas at Dallas "B.P. Hasdeu" National College  Titu Andreescu Bogdan Enescu  Contents  Part I  Problems  1  Algebra . . . . . . . . . . . . . . . . . . 1.1 An Algebraic Identity . . . . . . . . 1.2 Cauchy–Schwarz Revisited . . . . . 1.3 Easy Ways Through Absolute Values 1.4 Parameters . . . . . . . . . . . . . . 1.5 Take the Conjugate! . . . . . . . . . 1.6 Inequalities with Convex Functions . 1.7 Induction at Work . . . . . . . . . . 1.8 Roots and Coefficients . . . . . . . . 1.9 The Rearrangements Inequality . . .  . . . . . . . . . .  . . . . . . . . . .  . . . . . . . . . .  . . . . . . . . . .  . . . . . . . . . .  . . . . . . . . . .  . . . . . . . . . .  . . . . . . . . . .  . . . . . . . . . .  . . . . . . . . . .  . . . . . . . . . .  . . . . . . . . . .  . . . . . . . . . .  . . . . . . . . . .  . . . . . . . . . .  . . . . . . . . . .  3 3 7 11 14 17 20 24 27 31  2  Geometry and Trigonometry . . . . . . . 2.1 Geometric Inequalities . . . . . . . . . 2.2 An Interesting Locus . . . . . . . . . . 2.3 Cyclic Quads . . . . . . . . . . . . . . 2.4 Equiangular Polygons . . . . . . . . . 2.5 More on Equilateral Triangles . . . . . 2.6 The "Carpets" Theorem . . . . . . . . 2.7 Quadrilaterals with an Inscribed Circle 2.8 Dr. Trig Learns Complex Numbers . .  . . . . . . . . .  . . . . . . . . .  . . . . . . . . .  . . . . . . . . .  . . . . . . . . .  . . . . . . . . .  . . . . . . . . .  . . . . . . . . .  . . . . . . . . .  . . . . . . . . .  . . . . . . . . .  . . . . . . . . .  . . . . . . . . .  . . . . . . . . .  . . . . . . . . .  37 37 40 45 50 54 58 62 66  3  Number Theory and Combinatorics . . . . 3.1 Arrays of Numbers . . . . . . . . . . . . 3.2 Functions Defined on Sets of Points . . . 3.3 Count Twice! . . . . . . . . . . . . . . . 3.4 Sequences of Integers . . . . . . . . . . 3.5 Equations with Infinitely Many Solutions 3.6 Equations with No Solutions . . . . . . 3.7 Powers of 2 . . . . . . . . . . . . . . . 3.8 Progressions . . . . . . . . . . . . . . .  . . . . . . . . .  . . . . . . . . .  . . . . . . . . .  . . . . . . . . .  . . . . . . . . .  . . . . . . . . .  . . . . . . . . .  . . . . . . . . .  . . . . . . . . .  . . . . . . . . .  . . . . . . . . .  . . . . . . . . .  . . . . . . . . .  . . . . . . . . .  71 71 74 77 81 85 88 90 93 vii  viii  Contents  3.9 The Marriage Lemma . . . . . . . . . . . . . . . . . . . . . . . . Part II  96  Solutions  4  Algebra . . . . . . . . . . . . . . . . . . 4.1 An Algebraic Identity . . . . . . . . 4.2 Cauchy–Schwarz Revisited . . . . . 4.3 Easy Ways Through Absolute Values 4.4 Parameters . . . . . . . . . . . . . . 4.5 Take the Conjugate! . . . . . . . . . 4.6 Inequalities with Convex Functions . 4.7 Induction at Work . . . . . . . . . . 4.8 Roots and Coefficients . . . . . . . . 4.9 The Rearrangements Inequality . . .  . . . . . . . . . .  . . . . . . . . . .  . . . . . . . . . .  . . . . . . . . . .  . . . . . . . . . .  . . . . . . . . . .  . . . . . . . . . .  . . . . . . . . . .  . . . . . . . . . .  . . . . . . . . . .  . . . . . . . . . .  . . . . . . . . . .  . . . . . . . . . .  . . . . . . . . . .  . . . . . . . . . .  . . . . . . . . . .  101 101 109 116 120 124 130 134 138 144  5  Geometry and Trigonometry . . . . . . . 5.1 Geometric Inequalities . . . . . . . . . 5.2 An Interesting Locus . . . . . . . . . . 5.3 Cyclic Quads . . . . . . . . . . . . . . 5.4 Equiangular Polygons . . . . . . . . . 5.5 More on Equilateral Triangles . . . . . 5.6 The "Carpets" Theorem . . . . . . . . 5.7 Quadrilaterals with an Inscribed Circle 5.8 Dr. Trig Learns Complex Numbers . .  . . . . . . . . .  . . . . . . . . .  . . . . . . . . .  . . . . . . . . .  . . . . . . . . .  . . . . . . . . .  . . . . . . . . .  . . . . . . . . .  . . . . . . . . .  . . . . . . . . .  . . . . . . . . .  . . . . . . . . .  . . . . . . . . .  . . . . . . . . .  . . . . . . . . .  149 149 156 163 171 176 181 185 193  6  Number Theory and Combinatorics . . . . 6.1 Arrays of Numbers . . . . . . . . . . . . 6.2 Functions Defined on Sets of Points . . . 6.3 Count Twice! . . . . . . . . . . . . . . . 6.4 Sequences of Integers . . . . . . . . . . 6.5 Equations with Infinitely Many Solutions 6.6 Equations with No Solutions . . . . . . 6.7 Powers of 2 . . . . . . . . . . . . . . . 6.8 Progressions . . . . . . . . . . . . . . . 6.9 The Marriage Lemma . . . . . . . . . .  . . . . . . . . . .  . . . . . . . . . .  . . . . . . . . . .  . . . . . . . . . .  . . . . . . . . . .  . . . . . . . . . .  . . . . . . . . . .  . . . . . . . . . .  . . . . . . . . . .  . . . . . . . . . .  . . . . . . . . . .  . . . . . . . . . .  . . . . . . . . . .  . . . . . . . . . .  197 197 201 205 213 219 224 229 237 244  Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 249 Index of Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 251 Index to the Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253  Part I  Problems  Chapter 1  Algebra  1.1 An Algebraic Identity A very useful algebraic identity is derived by considering the following problem. Problem 1.1 Factor a 3 + b3 + c3 − 3abc. Solution Let P denote the polynomial with roots a, b, c: P (X) = X 3 − (a + b + c)X2 + (ab + bc + ca)X − abc. Because a, b, c satisfy the equation P (x) = 0, we obtain a 3 − (a + b + c)a 2 + (ab + bc + ca)a − abc = 0, b3 − (a + b + c)b2 + (ab + bc + ca)b − abc = 0, c3 − (a + b + c)c2 + (ab + bc + ca)c − abc = 0. Adding up these three equalities yields   a 3 + b3 + c3 − (a + b + c) a 2 + b2 + c2 + (ab + bc + ca)(a + b + c) − 3abc = 0. Hence   a 3 + b3 + c3 − 3abc = (a + b + c) a 2 + b2 + c2 − ab − bc − ca .  (1.1)  Note that the above identity leads to the following result: if a + b + c = 0, then a 3 + b3 + c3 = 3abc. Another way to obtain the identity (1.1) is to consider the determinant:   a b c    D =  c a b  . b c a T. Andreescu, B. Enescu, Mathematical Olympiad Treasures, DOI 10.1007/978-0-8176-8253-8_1, © Springer Science+Business Media, LLC 2011  3  4  1  Algebra    1 a 3 + b3 + c3 − 3abc = (a + b + c) (a − b)2 + (b − c)2 + (c − a)2 . 2  (1.2)  Expanding D, we obtain D = a 3 + b3 + c3 − 3abc. On the other hand, adding all columns to the first one gives     a + b + c b c  1 b c      D =  a + b + c a b  = (a + b + c)  1 a b  a + b + c c a  1 c a    2 = (a + b + c) a + b2 + c2 − ab − bc − ca . Notice that the expression a 2 + b2 + c2 − ab − bc − ca can also be written as  1 (a − b)2 + (b − c)2 + (c − a)2 . 2 We obtain another version of the identity (1.1):  This form leads to a short proof of the AM − GM inequality for three variables. Indeed, from (1.2) it is clear that if a, b, c are positive, then a 3 + b3 + c3 ≥ 3abc. √ √ √ 3 Now, if x, y, z are positive numbers, taking a = x, b = 3 y and c = 3 z yields x +y +z √ ≥ 3 xyz, 3 with equality if and only if x = y = z. Finally, let us regard a 2 + b2 + c2 − ab − bc − ca as a quadratic in a, with parameters b, c. This quadratic has discriminant   Δ = (b + c)2 − 4 b2 + c2 − bc = −3(b − c)2 . Hence its roots are √ √ √ b + c − i(b − c) 3 1−i 3 1+i 3 =b +c a1 = 2 2 2 and  √ √ √ 1+i 3 1−i 3 b + c + i(b − c) 3 a2 = =b +c . 2 2 2  1.1 An Algebraic Identity  Setting ω = √  −1−i 3 , 2  √ −1+i 3 , 2  5  one of the primitive cubic roots of the unity, we have ω2 =  hence a1 = −bω − cω2 and a2 = −bω2 − cω. This gives the factorization    a 2 + b2 + c2 − ab − bc − ca = a + bω + cω2 a + bω2 + cω ,  which leads to the identity    a 3 + b3 + c3 − 3abc = (a + b + c) a + bω + cω2 a + bω2 + cω .  (1.3)  Here are some problems that show how useful the above identities can be. Problem 1.2 Factor (x − y)3 + (y − z)3 + (z − x)3 . Solution Observe that if a +b +c = 0, then it follows from (1.1) that a 3 +b3 +c3 = 3abc. Because (x − y) + (y − z) + (z − x) = 0, we obtain the factorization (x − y)3 + (y − z)3 + (z − x)3 = 3(x − y)(y − z)(z − x). Problem 1.3 Prove that Solution Let x =   3  2+    √ √ 3 3 2 + 5 + 2 − 5 is a rational number.  √ √ 3 5 + 2 − 5. We then have   √ √ 3 3 x − 2 + 5 − 2 − 5 = 0.  As we have seen, a + b + c = 0 implies a 3 + b3 + c3 = 3abc, so we obtain  √   √  √  √   3 x 3 − 2 + 5 − 2 − 5 = 3x 2 + 5 2 − 5 , or x 3 + 3x − 4 = 0. Clearly, one of the roots of this equation is x = 1 and the other two sat roots √ 2 + x + 4 = 0, which has no real solutions. Since 3 2 + 5 + isfy the equation x  √ 3 2 − 5 is a real root, it follows that   √ √ 3 3 2 + 5 + 2 − 5 = 1, which is a rational number. Next come some proposed problems.  6  1  Algebra  Problem 1.4 Factor (a + 2b − 3c)3 + (b + 2c − 3a)3 + (c + 2a − 3b)3 . Problem 1.5 Let x, y, z be integers such that (x − y)2 + (y − z)2 + (z − x)2 = xyz. Prove that x 3 + y 3 + z3 is divisible by x + y + z + 6. Problem 1.6 Let a, b, c be distinct real numbers. Prove that the following equality cannot hold: √ √ √ 3 3 a − b + b − c + 3 c − a = 0. Problem 1.7 Prove that the number   √ √ 3 3 45 + 29 2 + 45 − 29 2 is a rational number. Problem 1.8 Let a, b, c be rational numbers such that √ √ 3 3 a + b 2 + c 4 = 0. Prove that a = b = c = 0. Problem 1.9 Let r be a real number such that √ 1 3 r+√ = 3. 3 r Determine the value of r3 +  1 . r3  Problem 1.10 Find the locus of points (x, y) for which x 3 + y 3 + 3xy = 1. Problem 1.11 Let n be a positive integer. Prove that the number  n n n 33 33 + 1 + 33 +1 − 1. is not a prime. Problem 1.12 Let S be the set of integers x such that x = a 3 + b3 + c3 − 3abc, for some integers a, b, c. Prove that if x, y ∈ S, then xy ∈ S.  1.2 Cauchy–Schwarz Revisited  7  Problem 1.13 Let a, b, c be distinct positive integers and let k be a positive integer such that ab + bc + ca ≥ 3k 2 − 1. Prove that a 3 + b3 + c3 − abc ≥ 3k. 3 Problem 1.14 Let a, b, c be the side lengths of a triangle. Prove that 3  a 3 + b3 + c3 + 3abc ≥ max(a, b, c). 2  Problem 1.15 Find the least real number r such that for each triangle with side lengths a, b, c, max(a, b, c) < r. √ 3 3 a + b3 + c3 + 3abc Problem 1.16 Find all integers that can be represented as a 3 + b3 + c3 − 3abc for some positive integers a, b, and c. Problem 1.17 Find all pairs (x, y) of integers such that xy +  x3 + y3 = 2007. 3  Problem 1.18 Let k be an integer and let     3 3 n = k + k 2 − 1 + k − k 2 − 1 + 1. Prove that n3 − 3n2 is an integer.  1.2 Cauchy–Schwarz Revisited Let a1 , a2 , . . . , an , b1 , b2 , . . . , bn be nonzero real numbers. Then  2   a1 + a22 + · · · + an2 b12 + b22 + · · · + bn2 ≥ (a1 b1 + a2 b2 + · · · + an bn )2 with equality if and only if a1 a2 an = = ··· = . b1 b2 bn  (∗)  8  1  Algebra  This is the well-known Cauchy–Schwarz inequality. The standard elementary proof uses the properties of the quadratic function: consider the function f (x) = (a1 − b1 x)2 + (a2 − b2 x)2 + · · · + (an − bn x)2 . Clearly, f (x) ≥ 0 for all real x, therefore, being a quadratic function, its discriminant Δ must be negative or zero. The inequality follows by observing that    Δ = 4(a1 b1 + a2 b2 + · · · + an bn )2 − 4 a12 + a22 + · · · + an2 b12 + b22 + · · · + bn2 . If we have equality in (∗), then Δ = 0 and the equation f (x) = 0 has a real root x0 . But then (a1 − b1 x0 )2 + (a2 − b2 x0 )2 + · · · + (an − bn x0 )2 = f (x0 ) = 0, so that a1 − b1 x0 = a2 − b2 x0 = · · · = an − bn x0 = 0 and an a1 a2 = = ··· = = x0 . b1 b2 bn Conversely, if an a1 a2 = = ··· = b1 b2 bn then the equation f (x) = 0 has a real root, so Δ ≥ 0. Since Δ cannot be positive, it follows that Δ = 0 and we have equality in (∗). Another proof uses a simple lemma which can also be helpful in proving a large number of algebraic inequalities: If a, b, x, y are real numbers and x, y > 0, then the following inequality holds: a 2 b2 (a + b)2 + ≥ . x y x+y The proof is straightforward. Clearing out denominators yields a 2 y(x + y) + b2 x(x + y) ≥ (a + b)2 xy, which readily simplifies to the obvious (ay − bx)2 ≥ 0. We see that the equality holds if and only if ay = bx, that is, if b a = . x y Applying the lemma twice, we can extend the inequality to three pairs of numbers. Indeed, a 2 b2 c2 (a + b)2 c2 (a + b + c)2 + + ≥ + ≥ , x y z x +y z x +y +z  1.2 Cauchy–Schwarz Revisited  9  and a simple inductive argument shows that a12 a22 a 2 (a1 + a2 + · · · + an )2 + + ··· + n ≥ x1 x2 xn x1 + x2 + · · · + xn for all real numbers a1 , a2 , . . . , an and x1 , x2 , . . . , xn > 0, with equality if and only if an a1 a2 = = ··· = . x1 x2 xn Returning to Cauchy–Schwarz, let us use the lemma in the general case: a12 + a22 + · · · + an2 =  a12 b12 b12  +  a22 b22 b22  + ··· +  an2 bn2 (a1 b1 + a2 b2 + · · · + an bn )2 ≥ . bn2 b12 + b22 + · · · + bn2  This yields    2 a1 + a22 + · · · + an2 b12 + b22 + · · · + bn2 ≥ (a1 b1 + a2 b2 + · · · + an bn )2 and the equality holds if and only if a1 a2 an = = ··· = . b1 b2 bn Let us see our lemma at work! Problem 1.19 Let a, b, c be positive real numbers. Prove that b c 3 a + + ≥ . b+c c+a a+b 2 Solution Observe that a b c a2 b2 c2 (a + b + c)2 + + = + + ≥ , b + c c + a a + b ab + ac bc + ba ca + cb 2(ab + bc + ca) so it suffices to prove 3 (a + b + c)2 ≥ . 2(ab + bc + ca) 2 A short computation shows that this is equivalent to a 2 + b2 + c2 ≥ ab + bc + ca, which yields (a − b)2 + (b − c)2 + (c − a)2 ≥ 0. Problem 1.20 Let a and b be positive real numbers. Prove that   8 a 4 + b4 ≥ (a + b)4 .  10  1  Solution We apply the lemma twice: 2  (a+b) a 4 b4 (a 2 + b2 )2 ( 2 )2 (a + b)4 + ≥ ≥ = . a +b = 1 1 2 2 8 4  4  Try to use the lemma to prove the following inequalities. Problem 1.21 Let x, y, z > 0. Prove that 2 2 2 9 + + ≥ . x +y y +z z+x x +y +z Problem 1.22 Let a, b, x, y, z be positive real numbers. Prove that y z 3 x + + ≥ . ay + bz az + bx ax + by a + b Problem 1.23 Let a, b, c > 0. Prove that a 2 + b 2 b2 + c 2 a 2 + c 2 + + ≥ a + b + c. a+b b+c a+c Problem 1.24 Let a, b, c be positive numbers such that abc = 1. Prove that 1 a 3 (b + c)  +  1 1 3 + 3 ≥ . + c) c (a + b) 2  b3 (a  Problem 1.25 Let x, y, z > 0. Prove that x y z 1 + + ≥ . x + 2y + 3z y + 2z + 3x z + 2x + 3y 2 Problem 1.26 Let x, y, z > 0. Prove that y2 z2 3 x2 + + ≥ . (x + y)(x + z) (y + z)(y + x) (z + x)(z + y) 4 Problem 1.27 Let a, b, c, d, e be positive real numbers. Prove that a b c d e 5 + + + + ≥ . b+c c+d d +e e+a a+b 2 Problem 1.28 Let a, b, c be positive real numbers such that 1 ab + bc + ca = . 3 Prove that a2  b c 1 a . + 2 + 2 ≥ − bc + 1 b − ca + 1 c − ab + 1 a + b + c  Algebra  1.3 Easy Ways Through Absolute Values  11  Problem 1.29 Let a, b, c be positive real numbers such that abc = 1. Prove that b+c+1 c+a+1 a+b+1 (a + 1) (b + 1) (c + 1) + 1 + + ≤ . a + b 2 + c 3 b + c2 + a 3 c + a 2 + b 3 a+b+c Problem 1.30 Let a and b be positive real numbers. Prove that a 4 + b4 a 3 + b3 a + b · ≥ . a 4 + b 4 a 2 + b 2 a 6 + b6 Problem 1.31 Let a, b, c be positive real numbers such that ab +bc +ca ≥ 3. Prove that b c 3 a +√ +√ ≥√ . √ c+a a+b b+c 2 Problem 1.32 Let a, b, c be positive real numbers. Prove that b c 9 a + + ≥ . b(b + c)2 c(c + a)2 a(a + b)2 4(ab + bc + ca) Problem 1.33 Let a, b, c be positive real numbers such that 1 1 1 + + ≥ 1. a 2 + b2 + 1 b 2 + c2 + 1 c2 + a 2 + 1 Prove that ab + bc + ca ≤ 3.  1.3 Easy Ways Through Absolute Values Everybody knows that sometimes solving equations or inequalities with absolute values can be boring. Most of the students facing such problems begin by writing the absolute values in an explicit manner. Let us consider, for instance, the following simple equation: Problem 1.34 Solve the equation |2x − 1| = |x + 3|. Solution We have |2x − 1| =  −2x + 1, 2x − 1,  x ≤ 12 , x>  1 2,  and |x + 3| =  −x − 3, x ≤ −3, x + 3,  x > −3.  If x ≤ −3, the equation becomes −2x + 1 = −x − 3; hence x = 4. But 4 > −3, so we have no solutions in this case. If −3 < x ≤ 12 , we obtain −2x + 1 = x + 3, so  12  1  Algebra  x = − 23 ∈ (−3, 12 ]. Finally, if x > 12 , we obtain x = 4 again. We conclude that the solutions are x = − 23 and x = 4. Nevertheless, there is an easier way to solve the equation by noticing that |a| = |b| if and only if a = ±b, so that it is not necessary to write the absolute values in an explicit form. Here are some properties of the absolute values that might be useful in solving equations and inequalities: |ab| = |a||b|,    a  |a|  =  b  |b| , |a + b| ≤ |a| + |b|, with equality if and only if ab ≥ 0, |a − b| ≤ |a| + |b|, with equality if and only if ab ≤ 0. The last two inequalities can be written in a general form: | ± a1 ± a2 ± · · · ± an | ≤ |a1 | + |a2 | + · · · + |an |. Problem 1.35 Solve the equation |x − 1| + |x − 4| = 2. Solution Observe that   |x − 1| + |x − 4| ≥ (x − 1) − (x − 4) = |3| = 3 > 2, hence the equation has no solutions. Problem 1.36 Solve the equation |x − 1| + |x| + |x + 1| = x + 2. Solution We have   x + 2 = |x − 1| + |x| + |x + 1| ≥ (x − 1) − (x + 1) + |x| = |x| + 2. On the other hand, clearly x ≤ |x|, thus all inequalities must be equalities: that is x + 2 = |x| + 2 and   |x − 1| + |x| + |x + 1| = (x − 1) − (x + 1) + |x|. This implies that x ≥ 0 and the expressions x − 1 and x + 1 are of different sign, so x ∈ [−1, 1]. Finally, the solution is x ∈ [0, 1]. Problem 1.37 Find the minimum value of the expression: E(x) = |x − 1| + |x − 2| + · · · + |x − 100|, where x is a real number.  1.3 Easy Ways Through Absolute Values  13  Solution Observe that for k = 1, 2, . . . , 50, we have   |x − k| + x − (101 − k) ≥ 101 − 2k, with equality if x ∈ [k, 101 − k]. Adding these inequalities yields E(x) ≥ 2500, and the equality holds for all x such that [k, 101 − k] = [50, 51].  x∈ 1≤k≤50  Problem 1.38 Find the values of a for which the equation (x − 1)2 = |x − a| has exactly three solutions. Solution Observe that (x − 1)2 = |x − a| if and only if x − a = ±(x − 1)2 , that is, if and only if a = x ± (x − 1)2 . The number of solutions of the equation is equal to the number of intersection points between the line y = a and the graphs of the functions f (x) = x + (x − 1)2 = x 2 − x + 1 and g(x) = x − (x − 1)2 = −x 2 + 3x − 1. The graph of f is a parabola with vertex B( 12 , 34 ) and the graph of g a parabola with vertex C( 32 , 54 ). Now, since the equation f (x) = g(x) is a quadratic with one real root, it follows that the graphs are tangent to each other at point A(1, 1). We deduce that the line y = a intersects the two graphs at three points if and only is it passes through one of the points A, B, C; that is, if a ∈ { 34 , 1, 54 }. Try to use some of the ideas above in solving the following problems: Problem 1.39 Solve the equation |x − 3| + |x + 1| = 4. Problem 1.40 Show that the equation |2x − 3| + |x + 1| + |5 − x| = 0.99 has no solutions. Problem 1.41 Let a, b > 0. Find the values of m for which the equation |x − a| + |x − b| + |x + a| + |x + b| = m(a + b) has at least one real solution.  14  1  Algebra  Problem 1.42 Find all possible values of the expression E(x, y, z) =  |y + z| |z + x| |x + y| + + , |x| + |y| |y| + |z| |z| + |x|  where x, y, z are nonzero real numbers. Problem 1.43 Find all positive real numbers x, x1 , x2 , . . . , xn such that        log(xx1 ) +  log(xx2 ) + · · · +  log(xxn )         x   x  x    +  log + log + · · · +  log x1   x2  xn  = | log x1 + log x2 + · · · + log xn |. Problem 1.44 Prove that for all real numbers a, b, we have |a + b| |a| |b| ≤ + . 1 + |a + b| 1 + |a| 1 + |b| Problem 1.45 Let n be an odd positive integer and let x1 , x2 , . . . , xn be distinct real numbers. Find all one-to-one functions f : {x1 , x2 , . . . , xn } → {x1 , x2 , . . . , xn } such that        f (x1 ) − x1  = f (x2 ) − x2  = · · · = f (xn ) − xn .  Problem 1.46 Suppose the sequence a1 , a2 , . . . , an satisfies the following conditions: a1 = 0,  |a2 | = |a1 + 1|, . . . ,  |an | = |an−1 + 1|.  Prove that 1 a1 + a2 + · · · + an ≥− . n 2 Problem 1.47 Find real numbers a, b, c such that |ax + by + cz| + |bx + cy + az| + |cx + ay + bz| = |x| + |y| + |z|, for all real numbers x, y, z.  1.4 Parameters We start with the following problem.  1.4 Parameters  15  Problem 1.48 Solve the equation: x 3 (x + 1) = 2(x + a)(x + 2a), where a is a real parameter. Solution The equation is equivalent to x 4 + x 3 − 2x 2 − 6ax − 4a 2 = 0. This fourth degree equation is difficult to solve. We might try to factor the lefthand side, but without some appropriate software, the process would get quite complicated. What if we think of a as the unknown and x as the parameter? In this case, the equation can be written as a quadratic: 4a 2 + 6xa − x 4 − x 3 + 2x 2 = 0, whose discriminant is   36x 2 + 16 x 4 + x 3 − 2x 2 = 4x 2 (2x + 1)2 , fortunately a square. Solving for a, we obtain the solutions a1 = − 12 x 2 − x and a2 = 12 x 2 − 12 x, yielding the factorization 1 1 1 4a 2 + 6ax − x 4 − x 3 + 2x 2 = 4 a + x 2 + x a − x 2 + x 2 2 2    = − x 2 + 2x + 2a x 2 − x − 2a . Finally, we obtain the solutions x1,2 = −1 ± Problem 1.49 Solve the equation  √  √  1 − 2a, x3,4 =  1 2  ±  1 2  √ 1 + 8a.  5 − x = 5 − x2.  √ √ Solution There is no parameter! Note, however, that we must have x ∈ [− 5, 5], since the left-hand side is nonnegative. Squaring both sides, we obtain the equation x 4 − 10x 2 + x + 20 = 0 and, if we are lucky, we might observe the factorization    2 x + x − 5 x 2 − x − 4 = 0. What if we are not √ lucky? Well, let us introduce a parameter ourselves: replace 5 by a, where a > 0: a − x = a − x 2 . Squaring both sides yields the equation x 4 − 2ax 2 + x + a 2 − a = 0.  16  1  Algebra  Consider this as a quadratic in a with x as a parameter:   a 2 − 2x 2 + 1 a + x 4 + x = 0. The discriminant of the quadratic is Δ = (2x − 1)2 and thus the roots are a1 = x 2 + x and a2 = x 2 − x + 1. It follows that      a 2 − 2x 2 + 1 a + x 4 + x = a − x 2 − x a − x 2 + x − 1 . Returning to a = 5, we arrive at the desired factorization. The equations x 2 + x − 5 =√0 and x 2 − x − 4 = 0 have the solutions x1,2 = √ 1 (−1 ± 21) and x = 1 (1 ± 17), respectively. Only two of them belong to the 2 √ √ 3,4 2 interval [− 5, 5], and therefore the solutions of the initial equation are 12 (−1 + √ √ 21) and 12 (1 − 17). Here are some suggested problems. Problem 1.50 Solve the equation  x=  a−  √  a + x,  where a > 0 is a parameter. Problem 1.51 Let a be a nonzero real number. Solve the equation a 3 x 4 + 2a 2 x 2 + x + a + 1 = 0. Problem 1.52 Let a ∈ (0, 14 ). Solve the equation  1 1 2 = −a + a 2 + x − . x + 2ax + 16 16 Problem 1.53 Find the positive solutions of the following system of equations: a2 x2  −  b2 y2  = 8(y 4 − x 4 ),  ax − by = x 4 − y 4 where a, b > 0 are parameters. Problem 1.54 Let a, b, c > 0. Solve the system of equations ⎧ 1 ⎪ = c, ax − by + xy ⎪ ⎨ 1 bz − cx + zx = a, ⎪ ⎪ ⎩ cy − az + 1 = b. yz  1.5 Take the Conjugate!  17  Problem 1.55 Solve the equation x + a3 =  √ 3 a − x,  where a is a real parameter.  1.5 Take the Conjugate! Let a and b be positive numbers. Recall that the AM − GM states that a+b 2 ≥ Can we estimate the difference between the arithmetic and geometric means? Problem 1.56 Prove that if a ≥ b > 0, then (a − b)2 a + b √ (a − b)2 ≤ − ab ≤ . 8a 2 8b Solution By taking the conjugate of the difference above, we obtain 2 ( a+b a+b √ (a − b)2 2 ) − ab − ab = a+b = . √ √ 2 2(a + b + 2 ab) 2 + ab √ Now, the conclusion follows by observing that b ≤ ab ≤ a, and that √   8b ≤ 2 a + b + 2 ab ≤ 8a.  Problem 1.57 Evaluate the integer part of the number 1 1 1 . A = √ + √ + ··· + √ 3 10000 2 Solution Observe that 1 2 2 . √ =√ √ <√ √ k k+ k k+ k−1 Taking the conjugate, we obtain √  √ 1 √ <2 k− k−1 . k Setting k = 2, 3, . . . , 10000 and adding up yields  √ A < 2 10000 − 1 = 198. Similarly, √  √ 1 2 2 √ =√ √ >√ √ =2 k+1− k , k k+ k k+1+ k  √ ab.  18  1  hence A>2  Algebra  √  √ 10001 − 2 > 197.  It follows that the integer part of the number A equals 197. √ Problem 1.58 Let n be a positive integer. Prove that (2 + 3)n is an odd number. Solution Observe that the number √ n  √ n  xn = 2 + 3 + 2 − 3 is an even integer. Indeed, x1 = 4, x2 = 14 and xn+2 = 4xn+1 − xn ,  √ for all n ≥ 1, so the assertion follows inductively. Since 0 < (2 − 3)n < 1, we have √ n   yn = 2 + 3 = xn − 1, hence yn is odd. Problem 1.59 Solve the equation √ √ 1 + mx = x + 1 − mx, where m is a real parameter. Solution We can try squaring both terms, but since it is difficult to control the sign of the right-hand side, we prefer to write the equation as follows: √ √ 1 + mx − 1 − mx = x. Taking the conjugate yields the equivalent form 2mx = x. √ √ 1 + mx + 1 − mx We obtain x = 0 as solution and, for x = 0: √ √ 2m = 1 + mx + 1 − mx. Thus m is necessarily positive. We now square and obtain  2m2 − 1 = 1 − m2 x 2 . We obtain another condition for m, that is 2m2 − 1 ≥ 0, and squaring again we finally obtain the solutions  x = ±2 1 − m2 , where m ∈ [ √1 , 1]. 2  1.5 Take the Conjugate!  19  Take the conjugate in the following problems: Problem 1.60 Let a and b be distinct positive numbers and let A = Prove the inequality B<  a+b 2 ,  B=  √  ab.  (a − b)2 < A. 8(A − B)  Problem 1.61 Let m, n be positive integers with m < n. Find a closed form for the sum 1 1 1 +√ + ··· + √ √ √ √ . √ m+ m+1 m+1+ m+2 n−1+ n Problem 1.62 For any positive integer n, let √ 4n2 − 1 f (n) = √ . √ 2n + 1 + 2n − 1 4n +  Evaluate the sum f (1) + f (2) + · · · + f (40). Problem 1.63 Let a and b be distinct real numbers. Solve the equation   x − b2 − x − a 2 = a − b. Problem 1.64 Solve the following equation, where m is a real parameter:  x+  √  x−    √ x− x=m  x √ . x+ x  Problem 1.65 Prove that for every positive integer k, there exists a positive integer nk such that  √ k √ √ 3 − 2 = nk − nk − 1. Problem 1.66 Let a and b be nonzero integers with |a| ≤ 100, |b| ≤ 100. Prove that √   √ a 2 + b 3 ≥ 1 . 350 Problem 1.67 Let n be a positive integer. Prove that   is a perfect square.  √ 1+ 5 2  4n−2   −1  20  1  Algebra  Problem 1.68 Consider the sequence an =  1+ 1+  1 n  2  +  1+ 1−  1 n  2  ,  n ≥ 1.  Prove that 1 1 1 + + ··· + a1 a2 a20 is an integer. Problem 1.69 Prove that 9999  n=1  1 = 9. √ √ √ √ ( n + n + 1)( 4 n + 4 n + 1)  Problem 1.70 Consider the sequence an = 2 −  Prove that  √  1  , n2 + n4 + 14  a1 +  √  a2 + · · · +  n ≥ 1.  √ a119  is an integer.  1.6 Inequalities with Convex Functions A real-valued function f defined on an interval I ⊂ R is called convex if for all xA , xB ∈ I and for any λ ∈ [0, 1] the following inequality holds:   f λxA + (1 − λ)xB ≤ λf (xA ) + (1 − λ)f (xB ). Although the definition seems complicated, it has a very simple geometrical interpretation. Let us assume that f is a continuous function. Then f is convex on I if and only if no matter how we choose two points on the function's graph, the segment joining these points lies above the graph (see Fig. 1.1). To see why, let A(xA , yA ) and B(xB , yB ) be two points on the graph of f , with xA < xB , and let M(xM , f (xM )) be an arbitrary point on the graph with xA < xM < xB . If N (xM , yN ) is on the segment AB, it suffices to verify that f (xM ) ≤ yN . If we let x B − xM , λ= xB − xA  1.6 Inequalities with Convex Functions  21  Fig. 1.1  then λ ∈ [0, 1] and xM = λxA + (1 − λ)xB . Now it is easy to see that λ=  BN yB − yN , = BA yB − yA  that is, yN = λyA + (1 − λ)yB = λf (xA ) + (1 − λ)f (xB ). Thus the condition f (xM ) ≤ yN is equivalent to the convexity condition   f λxA + (1 − λ)xB ≤ λf (xA ) + (1 − λ)f (xB ). Observe that unless f is linear, the equality holds if and only if xA = xB . Hence, if f is not linear and xA = xB , then the inequality is a strict one. It can be shown that if f is a convex function on the interval I then for any x1 , x2 , . . . , xn ∈ I and any positive numbers λ1 , λ2 , . . . , λn such that λ1 + λ2 + · · · + λn = 1, we have f (λ1 x1 + λ2 x2 + · · · + λn xn ) ≤ λ1 f (x1 ) + λ2 f (x2 ) + · · · + λn f (xn ). A real-valued function f defined on an interval I ⊂ R is called concave if for all xA , xB ∈ I and for any λ ∈ [0, 1] the following inequality holds:   f λxA + (1 − λ)xB ≥ λf (xA ) + (1 − λ)f (xB ). Similar inequalities are valid for concave functions, replacing everywhere ≤ by ≥. It is known that if f is twice differentiable, then f is convex on I if an only if f ≥ 0 on I (and concave if f ≤ 0 on I ).  22  1  Algebra  Problem 1.71 Let f be a convex function on the interval I ⊂ R. Prove that for any a < b < c in I , we have f (a − b + c) ≤ f (a) − f (b) + f (c). Solution Since b ∈ (a, c), there exists λ such that b = λa + (1 − λ)c (take λ = and notice that λ ∈ [0, 1]). Since f is convex, we have  c−b c−a  f (b) ≤ λf (a) + (1 − λ)f (c). On the other hand, we can see that   a − b + c = a − λa + (1 − λ)c + c = (1 − λ)a + λc. Therefore, by convexity f (a − b + c) ≤ (1 − λ)f (a) + λf (c). Adding up the two inequalities, we obtain f (a − b + c) + f (b) ≤ f (a) + f (c), the desired result. A simple induction argument shows that if f is convex and a1 < a2 < · · · < a2n+1 , then f (a1 − a2 + a3 − · · · − a2n + a2n+1 ) ≤ f (a1 ) − f (a2 ) + f (a3 ) − · · · − f (a2n ) + f (a2n+1 ). If f is concave, then the inequality is reversed. Problem 1.72 Let a, b, c > 0. Prove the inequality b c 3 a + + ≥ . b+c a+c a+b 2 Solution This is a classical inequality. Usual solutions use Cauchy–Schwarz inequality or simple algebraic inequalities obtained by denoting b + c = x, etc. Another proof is given in the section "Cauchy–Schwarz Revisited" of this book. Set s = a + b + c. Then the inequality becomes a b c 3 + + ≥ . s −a s −b s −c 2  1.6 Inequalities with Convex Functions  Consider the function f (x) =  x s−x ,  23  defined on (0, s). We have  f (x) =  2s > 0, (s − x)3  so that f is convex on (0, s). We then have a+b+c 3  f  ≤  f (a) + f (b) + f (c) , 3  which means that b c s a + + ≥ 3f s−a s−b s−c 3  =3  s 3  s−  s 3  3 = , 2  as desired. Problem 1.73 Let f : [1, 13] → R be a convex and integrable function. Prove that   3   f (x) dx +  1  13    9  f (x) dx ≥  11  f (x) dx. 5  Solution We have seen that if a < b < c f (a − b + c) + f (b) ≤ f (a) + f (c). Let c = a + 10 and b = a + 4. Then f (a + 6) + f (a + 4) ≤ f (a) + f (a + 10). If we integrate both sides for a ∈ [1, 3], and notice that   3   f (a + 6) da =  3  f (x) dx,  1  and    9 7    3   f (a + 4) da =  1   f (a + 10) da =  1  7  f (x) dx, 5  13  f (x) dx, 11  the result follows. Proposed problems: Problem 1.74 Let a, b > 0 and let n be a positive integer. Prove the inequality a n + bn ≥ 2  a+b 2  n  .  24  1  Algebra  Problem 1.75 Prove that   √ √ √ 3 3 3 3 3 3 − 3 + 3 + 3 < 2 3. Problem 1.76 Prove the AM − GM inequality x1 + x2 + · · · + xn √ ≥ n x1 x2 · · · xn , n for all x1 , x2 , . . . , xn > 0. Problem 1.77 Let a1 < a2 < · · · < a2n+1 be positive real numbers. Prove the inequality  n  a1 − a2 + a3 − · · · − a2n + a2n+1 ≥  √ √ √ n a1 − n a2 + · · · + n a2n+1 .  Problem 1.78 Let x, y, z > 0. Prove that x y z 3 + + ≤ . 2x + y + z x + 2y + z x + y + 2z 4 Problem 1.79 Prove that if a, b, c, d > 0 and a ≤ 1, a + b ≤ 5, a + b + c ≤ 14, a + b + c + d ≤ 30, then √ √ √ √ a + b + c + d ≤ 10.  1.7 Induction at Work A large number of identities, inequalities etc. can be proved by induction. Sometimes induction is helpful in less obvious situations. We will examine several examples. Problem 1.80 Let n be a positive integer. Find the roots of the polynomial Pn (X) = 1 +  X X(X + 1) X(X + 1) · · · (X + n − 1) + + ··· + . 1! 2! n!  Solution For n = 1, the polynomial P1 (X) = 1 + X has the root −1. For n = 2, X(X+1) = 12 (X + 2)(X + 1) has roots −1 and −2. It is natural P2 (X) = 1 + X 1! + 2! to presume that the roots of Pn are −1, −2, . . . , −n. We prove this assertion by induction on n. Suppose it holds true for n. Then Pn factors as Pn (X) = c(X + 1)(X + 2) · · · (X + n),  1.7 Induction at Work  25  the number c being the coefficient of Xn . Checking again the definition of Pn , we 1 , hence see that c = n! Pn (X) =  1 (X + 1)(X + 2) · · · (X + n). n!  Now, observe that Pn+1 (X) = Pn (X) +  X(X + 1) · · · (X + n) (n + 1)!  =  1 X(X + 1) · · · (X + n) (X + 1)(X + 2) · · · (X + n) + n! (n + 1)!  =  1 (X + 1)(X + 2) · · · (X + n)(n + 1 + X), (n + 1)!  hence the roots of Pn+1 are −1, −2, . . . , −n and −(n + 1). Problem 1.81 Let n be a positive integer. Prove the inequality 1+  1 13  1 23  1+  1+  1 1 ··· 1 + 3 33 n  < 3.  Solution Apparently induction does not work here, since when passing from n to n + 1, the left-hand side increases while the right-hand side is constant. We can make induction work by proving a stronger result: 1+  1 13  1+  1 23  1+  1 1 ··· 1 + 3 33 n  1 ≤3− . n  The assertion is clearly true for n = 1. Suppose is true for n and multiply the above 1 inequality by 1 + (n+1) 3 . It suffices to prove that 3−  1 n  1+  1 (n + 1)3  ≤3−  1 . n+1  3−  1 n  1+  1 (n + 1)3  −3+  1 n+1  The difference  factors as −  n2 − n + 2 , n(n + 1)3  hence it is negative. The claim is proved. Problem 1.82 Let p be a prime number. Prove that for any positive integer a the number a p − a is divisible by p (Fermat's little theorem).  26  1  Algebra  Solution We proceed by induction on a. The statement is true for a = 1, so suppose it holds true for some a > 1. We want to prove that (a + 1)p − (a + 1) is divisible by p. The binomial theorem gives (a + 1)p =  p  p p−k a , k k=0  hence (a + 1) − (a + 1) = a − a + p  p  p−1  k=1  p p−k a . k  The conclusion follows  from the induction hypothesis and from the fact that the binomial coefficients pk for k = 1, 2, . . . , p − 1 are divisible by p. Use induction in solving the following problems. Problem 1.83 Let n be a positive integer. Prove the inequality 1+  1 2  1+  1 22  1+  1 1 ··· 1 + n 2 23  5 < . 2  Problem 1.84 Let n be a positive integer. Prove that the number n  22 − 1 has at least n distinct prime divisors. Problem 1.85 Let a and n be positive integers such that a < n!. Prove that a can be represented as a sum of at most n distinct divisors of n!. Problem 1.86 Let x1 , x2 , . . . , xm , y1 , y2 , . . . , yn be positive integers such that the sums x1 + x2 + · · · + xm and y1 + y2 + · · · + yn are equal and less than mn. Prove that in the equality x1 + x2 + · · · + xm = y1 + y2 + · · · + yn one can cancel some terms and obtain another equality. Problem 1.87 The sequence (xn )n≥1 is defined by x1 = 1, x2n = 1 + xn and x2n+1 = x12n for all n ≥ 1. Prove that for any positive rational number r there exists an unique n such that r = xn . Problem 1.88 Let n be a positive   integer and let 0 < a1 < a2 < · · · < an be real numbers. Prove that at least n+1 of the sums ±a1 ± a2 ± · · · ± an are distinct. 2  1.8 Roots and Coefficients  27  Problem 1.89 Prove that for each positive integer n, there are pairwise relatively prime integers k0 , k1 , . . . , kn , all strictly greater than 1, such that k0 k1 · · · kn − 1 is the product of two consecutive integers. n  Problem 1.90 Prove that for every positive integer n, the number 33 + 1 is the product of at least 2n + 1 (not necessarily distinct) primes. Problem 1.91 Prove that for every positive integer n there exists an n-digit number divisible by 5n all of whose digits are odd.  1.8 Roots and Coefficients Let P (X) = a0 + a1 X + · · · + an X n be a polynomial and x1 , x2 , . . . , xn its roots (real or complex). It is known that the following equalities hold: x1 + x2 + · · · + xn = −  an−1 , an  an−2 , an an−3 x1 x2 x3 + x1 x2 x4 + · · · + xn−2 xn−1 xn = − , an .. . a0 x1 x2 · · · xn = (−1)n . an x1 x2 + x1 x3 + · · · + xn−1 xn =  These are usually called Viète's relations. For instance, for a third degree polynomial P (X) = a0 + a1 X + a2 X2 + a3 X 3 , we have x1 + x2 + x3 = −  a2 , a3  a1 , a3 a0 x1 x2 x3 = − . a3  x1 x2 + x1 x3 + x2 x3 =  The Viète's relations can be very useful in solving problems not necessarily involving polynomials. Problem 1.92 Let a, b, c be nonzero real numbers such that (ab + bc + ca)3 = abc(a + b + c)3 . Prove that a, b, c are terms of a geometric sequence.  28  1  Algebra  Solution Consider the monic polynomial P (X) = X 3 + mX 2 + nX + p, with roots a, b, c. Then, by Viète's relations, we have a + b + c = −m, ab + bc + ca = n, abc = −p. The given equality yields n3 = m3 p, hence, if m = 0, the equation P (x) = 0 can be written as x 3 + mx 2 + nx +  n3 = 0, m3  or m3 x 3 + m4 x 2 + nm3 x + n3 = 0. It is not difficult to factor the left-hand side:   (mx + n) m2 x 2 − mnx + n2 + m3 x(mx + n)     = (mx + n) m2 x 2 + m3 − mn x + n2 . n and the other two satisfy the condiIt follows that one of the roots of P is x1 = − m 2  n 2 2 3 tion x2 x3 = m 2 (Viète's relations for the second degree polynomial m X + (m − mn)X + n2 ). We obtained x12 = x2 x3 , thus the roots are the terms of a geometric sequence. If m = 0 then n = 0 but in this case, the polynomial X 3 + p cannot have three real roots.  Observation Using appropriate software, one can obtain the factorization     (ab + bc + ca)3 − abc(a + b + c)3 = a 2 − bc b2 − ac c2 − ab , and the conclusion follows. Problem 1.93 Solve in real numbers the system of equations ⎧ ⎪ ⎨ x + y + z = 4, x 2 + y 2 + z2 = 14, ⎪ ⎩ 3 x + y 3 + z3 = 34. Solution Consider the monic polynomial P (t) = t 3 + at 2 + bt + c, with roots x, y, z.  1.8 Roots and Coefficients  29  Because x + y + z = 4, it follows that a = −4, hence P (t) = t 3 − 4t 2 + bt + c. We have x 2 + y 2 + z2 = (x + y + z)2 − 2(xy + xz + yz). It follows that b = xy + xz + yz = 1. The numbers x, y, z are the roots of P , thus x 3 − 4x 2 + x + c = 0, y 3 − 4y 2 + y + c = 0, z3 − 4z2 + z + c = 0. Adding these equalities and using the equations of the system, we obtain c = 6, hence P (t) = t 3 − 4t 2 + t + 6. We observe that t1 = −1 is a root, so P factors as   P (t) = (t + 1) t 2 − 5t + 6 , the other two roots being t2 = 2 and t3 = 3. It follows that the solutions of the system are the triple (−1, 2, 3) and all of its permutations. Problem 1.94 Let a and b be two of the roots of the polynomial X4 + X 3 − 1. Prove that ab is a root of the polynomial X 6 + X 4 + X 3 − X 2 − 1. Solution Let c and d be the other two roots of X 4 + X 3 − 1. The Viète's relations yield a + b + c + d = −1, ab + ac + ad + bc + bd + cd = 0, abc + abd + acd + bcd = 0, abcd = −1. Write these equalities in terms of s = a + b, s = c + d, p = ab and p = cd (this is often useful) to obtain s + s = −1, p + p + ss = 0,  30  1  Algebra  ps + p s = 0, pp = −1. Substituting p = − p1 and s = −1 − s in the second and in the third equalities yields p−  1 − s2 − s = 0 p  and p(−1 − s) −  s = 0. p  It follows from the second equality that s=−  p2 . +1  p2  Plugging this into the first equality gives p−  p4 1 p2 − 2 = 0. + 2 2 p (p + 1) p +1  A short computation shows that this is equivalent to p 6 + p4 + p 3 − p2 − 1 = 0, hence p = ab is a root of the polynomial X 6 + X 4 + X 3 − X2 − 1. Here are some suggested problems. Problem 1.95 Let a, b, c be nonzero real numbers such that a + b + c = 0 and 1 1 1 1 + + = . a b c a+b+c Prove that for all odd integers n 1 1 1 1 + n+ n= n . n a b c a + bn + cn Problem 1.96 Let a ≤ b ≤ c be real numbers such that a+b+c=2 and ab + bc + ca = 1.  1.9 The Rearrangements Inequality  31  Prove that 0≤a≤  4 1 ≤b≤1≤c≤ . 3 3  Problem 1.97 Prove that two of the four roots of the polynomial X 4 + 12X − 5 add up to 2. Problem 1.98 Find m and solve the following equation, knowing that its roots form a geometrical sequence: X 4 − 15X 3 + 70X2 − 120X + m = 0. Problem 1.99 Let x1 , x2 , . . . , xn be the roots of the polynomial X n + X n−1 + · · · + X + 1. Prove that 1 1 n 1 + + ··· + = . 1 − x1 1 − x2 1 − xn 2 Problem 1.100 Let a, b, c be rational numbers and let x1 , x2 , x3 be the roots of the polynomial P (X) = X3 + aX2 + bX + c. Prove that if xx12 is a rational number, different from 0 and −1, then x1 , x2 , x3 are rational numbers. Problem 1.101 Solve in real numbers the system of equations ⎧ ⎪ ⎨ x + y + z = 0, x 3 + y 3 + z3 = 18, ⎪ ⎩ 7 x + y 7 + z7 = 2058. Problem 1.102 Solve in real numbers the system of equations ⎧ a + b = 8, ⎪ ⎪ ⎪ ⎨ ab + c + d = 23, ⎪ ad + bc = 28, ⎪ ⎪ ⎩ cd = 12.  1.9 The Rearrangements Inequality Let n ≥ 2 be a positive integer and let x1 < x2 < · · · < xn , y1 < y2 < · · · < yn be two ordered sequences of real numbers. The rearrangements inequality states that among all the sums of the form S(σ ) = x1 yσ (1) + x2 yσ (2) + · · · + xn yσ (n) ,  32  1  Algebra  where σ is a permutation of the numbers 1, 2, . . . , n, the maximal one is x1 y1 + x2 y2 + · · · + xn yn , and the minimal one is x1 yn + x2 yn−1 + · · · + xn y1 . Indeed, let σ be a permutation for which S(σ ) is maximal. (Such a permutation exists, since the number of possible sums is finite.) Suppose, by way of contradiction, that one can find i, j , with 1 ≤ i < j ≤ n, such that σ (i) > σ (j ). Now, switch σ (i) and σ (j ) to obtain a new permutation σ . More precisely, ⎧ ⎪ ⎨ σ (k), σ (k) = σ (j ), ⎪ ⎩ σ (i),  for k = i, j, for k = i, for k = j.  Observe that   S σ − S(σ ) = xi yσ (j ) + xj yσ (i) − xi yσ (i) − xj yσ (j ) = (xi − xj )(yσ (j ) − yσ (i) ) > 0, since xi < xj and yσ (j ) < yσ (i) . This implies S(σ ) > S(σ ), contradicting thus the maximality of S(σ ). In a similar manner one can prove that x1 yn + x2 yn−1 + · · · + xn y1 is the minimal sum. Observations 1. If we replace the initial conditions with the less restrictive ones x1 ≤ x2 ≤ · · · ≤ xn , y1 ≤ y2 ≤ · · · ≤ yn , the conclusion still holds, only in this case there might exist more than one maximal (minimal) sum. Just consider the extreme case x1 = x2 = · · · = xn . 2. If the given sequences have opposite monotonies, then the first sum is minimal and the second one maximal. The rearrangements inequality has numerous interesting applications. Let us begin with a very simple one. Problem 1.103 Let a, b, c be real numbers. Prove that a 2 + b2 + c2 ≥ ab + bc + ca.  1.9 The Rearrangements Inequality  33  Solution For symmetry reasons, we can assume that a ≤ b ≤ c. Consider the ordered sequences x1 ≤ x2 ≤ x3 and y1 ≤ y2 ≤ y3 , with x1 = y1 = a, x2 = y2 = b, and x3 = y3 = c. The rearrangements inequality then gives x 1 y1 + x2 y2 + x3 y3 ≥ x 1 y2 + x2 y3 + x 3 y1 , which is exactly what we wanted to prove. Observations In a similar way we can prove the following more general result. Given the real numbers x1 , x2 , . . . , xn , we have x12 + x22 + · · · + xn2 ≥ x1 xσ (1) + x2 xσ (2) + · · · + xn xσ (n) , where σ is an arbitrary permutation of the numbers 1, 2, . . . , n. Problem 1.104 Let a, b, c be positive real numbers. Prove that a 3 + b3 + c3 ≥ 3abc. Solution Although this inequality follows directly from the identity we presented in the first chapter of this book, we will give another proof using rearrangements. Obviously, we can assume with no loss of generality that a ≤ b ≤ c, which also implies a 2 ≤ b2 ≤ c2 . Therefore, a 3 + b 3 + c3 = a · a 2 + b · b2 + c · c 2 ≥ a · b2 + b · c 2 + c · a 2 . Now, observe that a ≤ b ≤ c implies bc ≥ ca ≥ ab, as well. Consequently, 3abc = a · (bc) + b · (ca) + c · (ab) ≤ a · (ca) + b · (ab) + c · (bc) = a · b 2 + b · c2 + c · a 2 . We have thus obtained a 3 + b3 + c3 ≥ ab2 + bc2 + ca 2 ≥ 3abc, as desired. The rearrangements inequality can also be helpful in proving other classical inequalities. Check the following two problems to see alternative proofs of the AM − GM and Cauchy–Schwarz inequalities. Problem 1.105 Let a1 , a2 , . . . , an be positive real numbers. Prove that a1 + a2 + · · · + an √ ≥ n a1 a2 · · · a n . n  34  1  Algebra  Solution Denote by G the geometric mean of the given numbers and consider the sequences x1 =  a1 , G  x2 =  a 1 a2 ,..., G2  xn−1 =  a1 a2 · · · an−1 , Gn−1  xn =  a1 a2 · · · an = 1, Gn  y1 =  G , a1  y2 =  G2 ,..., a1 a2  yn−1 =  Gn−1 , a1 a2 · · · an−1  yn =  Gn = 1. a1 a2 · · · a n  Obviously, if we arrange the xi 's in order: xσ (1) ≤ xσ (2) ≤ · · · ≤ xσ (n) , then yσ (1) ≥ yσ (2) ≥ · · · ≥ yσ (n) , and hence the sum xσ (1) yσ (1) + xσ (2) yσ (2) + · · · + xσ (n) yσ (n) = n is minimal. But then n ≤ x1 yn + x2 y1 + x3 y2 + · · · + xn yn−1 =  an a1 a2 + + ··· + . G G G  Clearly, this is equivalent to a1 + a2 + · · · + an ≥ G, n that is, the AM − GM inequality. Problem 1.106 Let a1 , a2 , . . . , an , and b1 , b2 , . . . , bn be real numbers. Prove that    2 a1 + a22 + · · · + an2 b12 + b22 + · · · + bn2 ≥ (a1 b1 + a2 b2 + · · · + an bn )2 . Solution Set A=   a12 + a22 + · · · + an2 ,  B=   b12 + b22 + · · · + bn2 ,  and a1 , A bn x2n = . B x1 =  x2 =  a2 ,..., A  xn =  an , A  xn+1 =  b1 , B  xn+2 =  (We discarded the obvious case when all ai 's or all bi 's equal zero.)  b2 ,..., B  1.9 The Rearrangements Inequality  35  We have 2n   xk2 ≥  k=1  2n   xk xσ (k) ,  k=1  for any permutation σ . (See the observation at the end of the solution of Problem 1.103.) In particular, 2=  2n   xk2 ≥ x1 xn+1 + x2 xn+2 + · · · + xn x2n + xn+1 x1 + · · · + x2n xn  k=1  =2  a1 b1 + a2 b2 + · · · + an bn . AB  It follows that AB ≥ a1 b1 + a2 b2 + · · · + an bn . Taking instead xn+1 = −  b1 , B  xn+2 = −  b2 ,..., B  x2n = −  bn , B  we obtain in a similar way AB ≥ −(a1 b1 + a2 b2 + · · · + an bn ), hence AB ≥ |a1 b1 + a2 b2 + · · · + an bn |. Squaring the latter gives the Cauchy–Schwarz inequality. Finally, solving the following old IMO problem is not difficult if one uses rearrangements. Problem 1.107 Let a1 , a2 , . . . , an be distinct positive integers. Prove that n  ak k=1  k2  ≥  n  1 k=1  k  .  Solution Rearrange the ai 's in increasing order, as b1 < b2 < · · · < bn . The rearrangements inequality yields n  ak k=1  k2  ≥  n  bk k=1  k2  ,  since 1 1 1 > 2 > ··· > 2. 2 1 2 n  36  1  Algebra  On the other hand, it is not difficult to see that bk ≥ k, for all k, hence n  bk k=1  k2  ≥  n n   k 1 . = k k2 k=1  k=1  Now, rearrange some terms to solve the following problems. Problem 1.108 Let a, b, c be positive real numbers. Prove the inequality a b c 3 + + ≥ . b+c c+a a+b 2 Problem 1.109 Let a, b, c be positive real numbers. Prove the inequality a3 b3 c3 a+b+c + + ≥ . 2 b2 + c2 c 2 + a 2 a 2 + b2 Problem 1.110 Let a, b, c be positive real numbers. Prove that a+b+c≤  c3 a 2 + b 2 b2 + c 2 c 2 + a 2 a 3 b3 + + ≤ + + . 2c 2a 2b bc ca ab  Problem 1.111 Let a, b, c be positive real numbers. Prove the inequality a 2 b(b − c) b2 c(c − a) c2 a(a − b) + + ≥ 0. a+b b+c c+a Problem 1.112 Let a1 ≤ a2 ≤ · · · ≤ an and b1 ≤ b2 ≤ · · · ≤ bn be two ordered sequences of real numbers. Prove Chebyshev's inequality a1 + a2 + · · · + an b1 + b2 + · · · + bn a1 b1 + a2 b2 + · · · + an bn · ≤ . n n n Problem 1.113 Let a1 ≤ a2 ≤ · · · ≤ an and b1 ≤ b2 ≤ · · · ≤ bn be two ordered sequences of positive real numbers. Prove that (a1 + b1 )(a2 + b2 ) · · · (an + bn ) ≤ (a1 + bσ (1) )(a2 + bσ (2) ) · · · (an + bσ (n) ), for any permutation σ .  Chapter 2  Geometry and Trigonometry  2.1 Geometric Inequalities One of the most basic geometric inequalities is the triangle inequality: in every triangle, the length of one side is less than the sum of the two other sides' lengths. More generally, for any three points A, B, C one has AC + BC ≥ AB with equality if and only if C lies on the line segment AB. Many interesting problems can be solved using this simple idea. Problem 2.1 Let ABCD be a convex quadrilateral and let M, N be the midpoints of AD and BC, respectively. Prove that MN =  AB + CD 2  if and only if AB is parallel to CD.  Solution Let P be the midpoint of the diagonal AC (see Fig. 2.1). Then MP and P N are parallel to CD and AB, respectively. Moreover, we have MP = CD 2 and AB P N = 2 . Applying the triangle inequality to MNP gives AB CD + = P N + MP ≥ MN. 2 2 The equality occurs if and only if P lies on the line segment MN ; that is, if the lines MP , P N and MN coincide. Since MP  CD and N P  AB, the latter holds true if and only if AB and CD are parallel. T. Andreescu, B. Enescu, Mathematical Olympiad Treasures, DOI 10.1007/978-0-8176-8253-8_2, © Springer Science+Business Media, LLC 2011  37  38  2  Geometry and Trigonometry  Fig. 2.1  Problem 2.2 Let D be the midpoint of the side BC of triangle ABC. Prove that AD <  AB + AC . 2  Solution Let the point A be such that D is the midpoint of AA . Thus, the quadri  lateral ABA C is a parallelogram and AD = AA 2 . In triangle ABA , we have    AA < AB + BA . The conclusion follows observing that BA = AC. Problem 2.3 Let M be a point inside the triangle ABC. Prove that AB + AC > MB + MC. Solution Let N be the point at which BM intersects AC. Then we successively have AB + AC = AB + AN + NC > BN + NC = BM + MN + N C > BM + MC. Problem 2.4 Let A, B, C and D be four points in space, not in the same plane. Prove that AC · BD < AB · CD + AD · BC. Solution Consider a sphere which passes through the points B, C and D and intersects the segments AB, AC and AD at the points B  , C  and D  . The intersection of the sphere and the plane (ABC) is a circle, thus the quadrilateral BB  C  C is cyclic. It follows that triangles ABC and AC  B  are similar; hence AB  AC  B  C  = = . AC AB BC We obtain BC =  BC · AB  . AC  2.1 Geometric Inequalities  39  Analogously, triangles ABD and AD  B  are similar, so that B  D =  BD · AB  . AD  We deduce that BC · AD BC = . B  D  AC · BD In a similar way, we obtain C  D  AB · CD = . B  D  AC · BD But in triangle A B  C  we have B  C  + C  D  > B  D  , and therefore it follows that BC · AD AB · CD + > 1, AC · BD AC · BD so that AC · BD < AB · CD + AD · BC. Observation If A, B, C, D are coplanar points, then one can prove that AC · BD ≤ AB · CD + AD · BC, with equality if and only if ABCD is a cyclic quadrilateral. The proof is similar, but instead of constructing the sphere, one uses inversion. Here are some proposed problems. Problem 2.5 Let ABCD be a convex quadrilateral. Prove that max(AB + CD, AD + BC) < AC + BD < AB + BC + CD + DA. Problem 2.6 Let M be the midpoint of segment AB. Prove that if O is an arbitrary point, then |OA − OB| ≤ 2OM. Problem 2.7 Prove that in an arbitrary triangle, the sum of the lengths of the altitudes is less than the triangle's perimeter. Problem 2.8 Denote by P the perimeter of triangle ABC. If M is a point in the interior of the triangle, prove that 1 P < MA + MB + MC < P . 2  40  2  Geometry and Trigonometry  Problem 2.9 Prove that if A , B  and C  are the midpoints of the sides BC, CA, and AB, respectively, then 3 P < AA + BB  + CC  < P . 4 Problem 2.10 In the convex quadrilateral ABCD, we have AB + BD ≤ AC + CD. Prove that AB < AC. Problem 2.11 Consider n red and n blue points in the plane, no three of them being collinear. Prove that one can connect each red point to a blue one with a segment such that no two segments intersect. Problem 2.12 Let n be an odd positive integer. On some field, n gunmen are placed such that all pairwise distances between them are different. At a signal, every gunman takes out his gun and shoots the closest gunman. Prove that: (a) at least one gunman survives; (b) no gunman is shot more than five times; (c) the trajectories of the bullets do not intersect. Problem 2.13 Prove that the medians of a given triangle can form a triangle. Problem 2.14 Let A and B be two points situated on the same side of a line XY . Find the position of a point M on the line such that the sum AM + MB is minimal. Problem 2.15 Let ABC be an acute triangle. Find the positions of the points M, N, P on the sides BC, CA, AB, respectively, such that the perimeter of the triangle MNP is minimal. Problem 2.16 Seven real numbers are given in the interval (1, 13). Prove that at least three of them are the lengths of a triangle's sides.  2.2 An Interesting Locus Let us consider a triangle ABC and let D be the midpoint of segment BC. It is not difficult to see that [ABD] = [ACD]. Moreover, for each point M on the line AD we have [ABM] = [ACM].  2.2 An Interesting Locus  41  Fig. 2.2  Fig. 2.3  We want to determine the locus of points M such that [ABM] = [ACM]. The triangles ABM and ACM have the common side AM; hence their areas are equal if and only if the distances from B and C to AM are equal. It is not difficult to see that this happens in two situations: AM passes through the midpoint of BC or AM is parallel to BC (see Fig. 2.2). We derive that the locus of points M in the interior of triangle ABC for which [ABM] = [ACM] is the median AD. Now, let us translate the sides AB and AC to A B and A C and ask a similar question. Find the locus of points M such that      A BM = A CM  (see Fig. 2.3). Let us rephrase this. Problem 2.17 Given the quadrilateral ABCD such that AB and CD are not parallel, find the locus of points M inside ABCD for which [ABM] = [CDM]. Solution We apply other translations. Denote by T the point of intersection of the lines AB and CD. We translate the segment AB to T X and the segment CD to T Y . It is not difficult to see that [ABM] = [T XM] and [CDM] = [T Y M], hence M lies on the median of triangle T XY . We deduce that the desired locus is a segment: the part of the median of T XY lying inside the quadrilateral ABCD (Fig. 2.4).  42  2  Geometry and Trigonometry  Fig. 2.4  Fig. 2.5  Problem 2.18 Prove that in a trapezoid the midpoints of parallel sides, the point of intersection of the diagonals and the point of intersection of the non-parallel sides are collinear. Solution This is an immediate application of the above property. We have (with the notations in Fig. 2.5) [ABP ] = [CDP ],  [ABR] = [CDR],  hence R and P lie on the line through the intersection S of AB and CD found in Problem 2.17. All we have to do is to prove that [ABQ] = [CDQ]. But [ABQ] + [BQC] = [ABC] = [DBC] = [CDQ] + [BQC], and we are done. Problem 2.19 Suppose we are given a positive number k and a quadrilateral ABCD in which AB and CD are not parallel. Find the locus of points M inside ABCD for which [ABM] + [CDM] = k.  2.2 An Interesting Locus  43  Fig. 2.6  Solution Using the construction from Problem 2.17, we obtain [ABM] + [CDM] = [T XMY ] = [T XY ] + [XMY ]. Since X and Y are fixed points, it follows that [XMY ] is a constant; therefore the point M lies on a parallel to the line XY . According to the value of k, the locus is either a segment (or a point) or it is the empty set. Observation If M lies on this parallel, but in the exterior of the quadrilateral, it is not difficult to see that in this case we either have [ABM] − [CDM] = k, or [CDM] − [ABM] = k. Problem 2.20 A circle with center O is inscribed in the convex quadrilateral ABCD. If M and N are the midpoints of the diagonals AC and BD, prove that points O, M, and N are collinear.  Solution Since a circle is inscribed in quadrilateral ABCD (Fig. 2.6), we know that AB + CD = AD + BC. Multiplying the equality by r/2, where r is the radius of the circle, we obtain [OAB] + [OCD] = [OAD] + [OBC]. Thus 1 [OAB] + [OCD] = [ABCD]. 2 On the other hand, 1 1 1 [N AB] + [NCD] = [ABD] + [BCD] = [ABCD]. 2 2 2 Similarly, 1 [MAB] + [MCD] = [ABCD]. 2  44  2  Geometry and Trigonometry  It follows that O, M and N belong to the locus of the points X such that 1 [XAB] + [XCD] = [ABCD], 2 and they lie on the same segment if the opposite sides of ABCD are not parallel. If AB is parallel to CD or AD is parallel to BC, the result is trivial. Let us investigate the following problems: Problem 2.21 Find the locus of points M in plane of triangle ABC such that [ABM] = 2[ACM]. Problem 2.22 Let D be a point on the side BC of triangle ABC and let M be a point on AD. Prove that [ABM] BD = . [ACM] CD Deduce Ceva's theorem: if the segments AD, BE and CF are concurrent then BD CE AF · · = 1. CD AE BF Problem 2.23 Let ABCD be a convex quadrilateral and let M be a point in its interior such that [MAB] = [MBC] = [MCD] = [MDA]. Prove that one of the diagonals of ABCD passes through the midpoint of the other diagonal. Problem 2.24 Let ABCD be a convex quadrilateral. Find the locus of points M in its interior such that [MAB] = 2[MCD]. Problem 2.25 Let ABCD be a convex quadrilateral and let k > 0 be a real number. Find the locus of points M in its interior such that [MAB] + 2[MCD] = k. Problem 2.26 Let d, d  be two non-parallel lines in the plane and let k > 0. Find the locus of points the sum of whose distances to d and d  is equal to k. Problem 2.27 Let ABCD be a convex quadrilateral and let E and F be the points of intersections of the lines AB, CD and AD, BC, respectively. Prove that the midpoints of the segments AC, BD, and EF are collinear.  2.3 Cyclic Quads  45  Fig. 2.7  Fig. 2.8  Problem 2.28 In the interior of a quadrilateral ABCD, consider a variable point P . Prove that if the sum of distances from P to the sides is constant, then ABCD is a parallelogram.  2.3 Cyclic Quads A convex quadrilateral is called cyclic if its vertices lie on a circle. It is not difficult to see that a necessary and sufficient condition for this is that the sum of the opposite angles of the quadrilateral be equal to 180◦ (Fig. 2.7). As a special case, if two opposite angles of the quadrilateral are right angles, then the quadrilateral is cyclic and the diagonal which splits the quadrilateral into two right triangles is a diameter of the circumscribed circle. Another necessary and sufficient condition is that the angle between one side and a diagonal be equal to the angle between the opposite side and the other diagonal (Fig. 2.8). Problem 2.29 Let ABCD be a cyclic quadrilateral. Recall that the incenter of a triangle is the intersection of the angles' bisectors. Prove that the incenters of triangles ABC, BCD, CDA and DAB are the vertices of a rectangle.  46  2  Geometry and Trigonometry  Fig. 2.9  Solution The incenter of a triangle is the intersection of the angle's bisectors. Let K, L, M and N be the four incenters (Fig. 2.9). We then have ∠AKB = 180◦ − ∠BAC/2 − ∠ABC/2 = 90◦ + ∠ACB/2. Similarly, ∠ANB = 90◦ + ∠ADB/2. But since ABCD is cyclic, we have ∠ACB = ∠ADB, hence ∠AKB = ∠ANB. This means that the quadrilateral ANKB is also cyclic, so ∠NKB = 180◦ − ∠BAN = 180◦ − ∠A/2. In the same manner we obtain ∠BKL = 180◦ − ∠C/2, hence ∠N KL = 360◦ − (∠NKB + ∠BKL) = (∠A + ∠C)/2 = 180◦ /2 = 90◦ . Analogously, we prove that the other three angles of KLMN are right angles. Problem 2.30 In the triangle ABC, the altitude, angle bisector and median from C divide the angle ∠C into four equal angles. Find the angles of the triangle. Solution No cyclic quads in the text (Fig. 2.10)! However, a solution using some trigonometry is at hand: with usual notations, from the angle bisector's theorem, we have AC b AE = = , EB CB a  2.3 Cyclic Quads  47  Fig. 2.10  so that AE b = AB a+b and AE =  bc . a+b  Also, BC a FB = = . F E CE b But c FB = , 2  F E = AF − AE =  c bc c(a − b) − = , 2 a + b 2(a + b)  so that we obtain c 2 c(a−b) 2(a+b)  a = , b  which is equivalent to a+b a = , a−b b or b2 + 2ab − a 2 = 0. We get the quadratic equation  2 b b + 2 − 1 = 0, a a from which we deduce that b √ = 2 − 1. a On the other hand, using the formula for the length of an angle bisector we have b = CE =  2ab ∠C cos a+b 2  48  2  Geometry and Trigonometry  Fig. 2.11  hence  √  ∠C a + b 1 1 b 1 1 √ 2 cos 2−1 = = = + = + . 2 2a 2 2a 2 2 2  ◦ ◦ ◦ ◦ We conclude that ∠C 2 = 45 , so ∠C = 90 , ∠A = 67.5 and ∠B = 22.5 . Now, let us try a purely geometric approach. Let D, E and F on AB be the feet of the altitude, angle bisector and median (Fig. 2.11). Drop a perpendicular from E to BC in the point M and let N be the intersection between MD and AC. The quadrilateral CDEM is cyclic, since  ∠CDE = ∠CME = 90◦ . Then ∠CMD = ∠CED = ∠CAD. It follows that triangles CMN and CAB are similar. This implies that CD is the median from C in triangle CMN , hence AMEN is a parallelogram (MN and AE have the same midpoint). Finally, AN  ME and since ME ⊥ BC, it follows that AC ⊥ BC. We conclude that ∠C = 90◦ , ∠A = 67.5◦ and ∠B = 22.5◦ . Observation Another proof using cyclic quads follows from the lemma below: Lemma Let ABC be a triangle inscribed in the circle centered at O such that the angles ∠B and ∠C are acute. If H is its orthocenter, then ∠BAH = ∠CAO (Fig. 2.12). Proof Let A be the point on the circumcircle such that AA is a diameter. Then ABA C is cyclic, hence ∠ABC = ∠AA C. It follows that their complementary angles ∠BAH and ∠CAA are equal as well.   2.3 Cyclic Quads  49  Fig. 2.12  Fig. 2.13  Returning to our problem, note that from the statement it follows that the angles A and B are acute. The orthocenter of the triangle ABC lies on the altitude CD. Because ∠ACD = ∠BCF , it follows from the lemma that the circumcenter of the triangle ABC lies on the line CF . On the other hand, the circumcenter lies on the perpendicular bisector of the segment AB. We deduce that the circumcenter is the point F , hence ∠C = 90◦ . Problem 2.31 Let E and F be two points on the sides BC and CD of the square ABCD, such that ∠EAF = 45◦ . Let M and N be the intersections of the diagonal BD with AE and AF , respectively. Let P be the intersection of MF and N E. Prove that AP is perpendicular to EF (Fig. 2.13).  Solution First, observe that ∠NBE = 45◦ , so ABEN is cyclic. This implies that ∠AEN = ∠ABN = 45◦ ,  50  2  Geometry and Trigonometry  so that triangle ANE is a right isosceles triangle. It follows that EN is perpendicular to AF . Similarly, F M is perpendicular to AE, so P is the orthocenter of triangle AEF . The conclusion is obvious. Look for the cyclic quads in the following problems. Problem 2.32 Let D, E, and F be the feet of the altitudes of the triangle ABC. Prove that the altitudes of ABC are the angle bisectors of the triangle DEF . Problem 2.33 Let ABCD be a convex quadrilateral. Prove that AB · CD + AD · BC = AC · BD if and only if ABCD is cyclic. Problem 2.34 Let A , B  , and C  be points in the interior of the sides BC, CA, and AB of the triangle ABC. Prove that the circumcircles of the triangles AB  C  , BA C  , and CA B  have a common point. Problem 2.35 Let ABCD be a cyclic quadrilateral. Prove that the orthocenters of the triangles ABC, BCD, CDA and DAB are the vertices of a quadrilateral congruent to ABCD and prove that the centroids of the same triangles are the vertices of a cyclic quadrilateral. Problem 2.36 Let K, L, M, N be the midpoints of the sides AB, BC, CD, DA, respectively, of a cyclic quadrilateral ABCD. Prove that the orthocenters of the triangles AKN, BKL, CLM, DMN are the vertices of a parallelogram. Problem 2.37 Prove that the perpendiculars dropped from the midpoints of the sides of a convex quadrilateral to the opposite sides are concurrent. Problem 2.38 In the convex quadrilateral ABCD the diagonals AC and BD intersect at O and are perpendicular. Prove that projections of O on the quadrilateral's sides are the vertices of a cyclic quadrilateral.  2.4 Equiangular Polygons We call a convex polygon equiangular if its angles are congruent. Thus, an equiangular triangle is an equilateral one, an equiangular quadrilateral is a rectangle (or a square). One interesting property of the equiangular polygons is stated in the following problem. Problem 2.39 Let P be a variable point in the interior or on the sides of an equiangular polygon. Prove that the sum of distances from P to the polygon's sides is constant.  2.4 Equiangular Polygons  51  Fig. 2.14  Fig. 2.15  Solution It is not difficult to see that the statement is true for regular polygons. Indeed, connect P to the polygon's vertices and write its area as a sum of areas of the triangles thus obtained (see Fig. 2.14 in the case of a pentagon). If the polygon's sides have length a and the distances from P  to the sides are d1 , d2 , . . . , dn , respectively, then the area A of the polygon equals 12 nk=1 adk hence d1 + d2 + · · · + dn = 2A a is constant. Now, if the polygon is an arbitrary equiangular one, we can always "expand" it to a regular polygon, adding thus to the sum of distances a constant value (the sum of distances between parallel sides) as seen in Fig. 2.15. The converse of the above property is true in the case of a triangle. Indeed, if P is a variable point in the interior or on the sides of triangle ABC and the sum of distances from P to triangle's sides is constant, then ABC is an equilateral triangle. We can see this if we move P to A, P to B and P to C and observe that triangle's altitudes must have the same length. It is not difficult to see that this happens if and only if ABC is equilateral. The converse is not true for a quadrilateral, because a parallelogram has this property and (unless it is a rectangle) it is not an equiangular polygon. Problem 2.40 Let a1 , a2 , . . . , an be positive real numbers and let ε be the primitive 2π nth root of the unity ε = cos 2π n + i sin n . Prove that if the sides of an equiangular  52  2  Geometry and Trigonometry  Fig. 2.16  polygon have lengths a1 , a2 , . . . , an (in counter-clockwise order) then a1 + a2 ε + a3 ε2 + · · · + an εn−1 = 0. Solution We draw a picture for the case n = 6 (the general case is essentially the same). Consider the polygon's sides as vectors, oriented clockwise (see Fig. 2.16). Then the sum of the vectors equals zero. Now, translate all vectors such that they have the same origin O. If we look at the complex numbers corresponding to their extremities, choosing a1 on the positive real axis, we see that these are a1 , a2 ε, a3 ε2 , . . . , and an ε n−1 , respectively. Since the sum of the vectors equals zero, we deduce that a1 + a2 ε + a3 ε2 + · · · + an εn−1 = 0. Observation The converse of the statement is generally not true. For instance, if a, b, c, d are the side lengths of a quadrilateral and a + bi + ci 2 + di 3 = 0, then (a − c) + i(b − d) = 0; this equality is fulfilled if the quadrilateral is a parallelogram (and not necessarily an equiangular quadrilateral, that is, a rectangle). However, from the solution we see that if a1 , a2 , . . . , an are positive numbers and a1 + a2 ε + a3 ε 2 + · · · + an εn−1 = 0, then there exists an equiangular polygon with sides of lengths a1 , a2 , . . . , an . It is worth mentioning that in the case n = 3, there exists another necessary and sufficient condition: if a, b, c are the complex numbers corresponding to the (distinct) points A, B, C, then the triangle ABC is equilateral if and only if a + bε + cε 2 = 0, where ε is one of the (non-real) cubic roots of the unity. Problem 2.41 Prove that if an equiangular hexagon have side lengths a1 , . . . , a6 (in this order) then a1 − a4 = a5 − a2 = a3 − a6 .  2.4 Equiangular Polygons  53  Fig. 2.17  Solution Choose three non-adjacent vertices of the hexagon and draw parallels to the sides through them, as in Fig. 2.17. Suppose that the parallels mutually intersect at the points K, L, M. Thus, the hexagon is partitioned into three parallelograms and a triangle. Since the hexagon is equiangular, triangle KLM is equilateral. Finally, observe that LM = a1 − a4 , KL = a5 − a2 and MK = a3 − a6 . Another solution is possible using the preceding problem. Let ε = cos 2π 6 + 2π i sin 6 be a primitive sixth root of unity. Then a1 + a2 ε + a3 ε2 + a4 ε3 + a5 ε4 + a6 ε5 = 0. But ε3 = cos π + i sin π = −1, so ε4 = −ε and ε5 = −ε2 . We deduce that (a1 − a4 ) + (a2 − a5 )ε + (a3 − a6 )ε2 = 0. On the other hand, since ε 3 = −1 (and ε = −1) we see that ε 2 − ε + 1 = 0. Thus, ε is a common root of the equations (a1 − a4 ) + (a2 − a5 )z + (a3 − a6 )z2 = 0 and / R, it follows that the two z2 − z + 1 = 0, both with real coefficients. Since ε ∈ equations share another common root ε, so the coefficients of the two equations must be proportional; that is, (a1 − a4 ) = −(a2 − a5 ) = (a3 − a6 ), as desired. Try the following problems. Problem 2.42 Let ABCDE be an equiangular pentagon whose side lengths are rational numbers. Prove that the pentagon is regular. Problem 2.43 Prove that p is a prime number if and only if every equiangular polygon with p sides of rational lengths is regular. Problem 2.44 An equiangular polygon with an odd number of sides is inscribed in a circle. Prove that the polygon is regular.  54  2  Geometry and Trigonometry  Fig. 2.18  Problem 2.45 Let a1 , a2 , . . . , an be the side lengths of an equiangular polygon. Prove that if a1 ≥ a2 ≥ · · · ≥ an , then the polygon is regular. Problem 2.46 The side lengths of an equiangular octagon are rational numbers. Prove that the octagon has a symmetry center.  2.5 More on Equilateral Triangles One of the most beautiful problems in geometry is the following one. Problem 2.47 In the exterior of triangle ABC three equilateral triangles ABC  , BCA and CAB  are constructed. Prove that the centroids of these triangles are the vertices of an equilateral triangle. Solution It is said that the problem was discovered by Napoleon. We do not know the proof that he gave to this statement, but surely it was different from the following one. We use complex numbers. Note that if triangle ABC is equilateral and oriented counter-clockwise and its vertices correspond to the complex numbers a, b, c, then a + bε + cε2 = 0, √  (∗)  3 is the cube root of unity which represents a 120◦ counterwhere ε = −1+i 2 clockwise rotation. The converse is also true: suppose (∗) holds. Notice that 1 + ε + ε 2 = 0. Thus ε 2 = −1 − ε and we obtain ε(b − c) = (c − a). Hence segment CA is obtained from segment BC by a 120◦ counter-clockwise rotation. Similarly AB is obtained from CA by a 120◦ counter-clockwise rotation and hence ABC is equilateral and oriented counter-clockwise. Now, let us return to Napoleon's problem. Assume the triangle ABC is oriented counter-clockwise as in Fig. 2.18. Since A CB, B  AC and C  BA are oriented counter-clockwise and are equilateral, we  2.5 More on Equilateral Triangles  55  have a  + cε + bε 2 = 0,  b + aε + cε2 = 0,  c + bε + aε 2 = 0,  respectively. The complex numbers corresponding to the centroids of triangles A BC, AB  C and ABC  are  1  a +b+c , 3  1 b = a + b + c 3  a  =  and c =   1 a + b + c , 3  respectively. We have to check that a  + b ε + c ε2 = 0. Observe that  1    1 −cε − bε2 + b + c = b 1 − ε2 + c(1 − ε) , 3 3       1 1 b ε = a − aε − cε2 + c ε = a ε − ε2 + c(ε − 1) , 3 3      1 1  c ε2 = a + b − bε − aε2 ε2 = a ε 2 − ε + b ε2 − 1 . 3 3 a  =  Adding up the three equalities gives the desired result. The reader who wants a "proof without words" for Napoleon's problem should carefully examine Fig. 2.19 (which may also be of some interest to carpet manufacturers. . .). Problem 2.48 In the exterior of the acute triangle ABC, three equilateral triangles ABC  , BCA and CAB  are constructed. Prove that the segments AA , BB  and CC  are concurrent. Also, prove that the circumcircles of the equilateral triangles pass through the same point (Fig. 2.20).  Solution We start with another problem: find the point T in the interior of triangle ABC for which the sum T A + T B + T C is minimal. Rotate clockwise the points A and T around C with 60◦ , to B  and T  , respectively (see Fig. 2.21). Then B  T  = AT and since triangle CT T  is equilateral, T T  = T C. We deduce that the sum T A + T B + T C is equal to BT + T T  + T  B  , and the latter is minimal when the points B, T , T  and B  are collinear. Thus, the point T for which the sum T A + T B + T C is minimal lies on BB  . Similarly, we can prove that  56  2  Geometry and Trigonometry  Fig. 2.19  Fig. 2.20  T lies on AA and CC  , so the three segments are concurrent. Also (see Fig. 2.22) notice that we have ∠AT C = ∠CT  B  = 180◦ − ∠CT  T = 120◦ and ∠BT C = 180◦ − ∠CT T  = 120◦ .  2.5 More on Equilateral Triangles  57  Fig. 2.21  Fig. 2.22  We deduce that the point T is the point in the interior of the triangle with the property that ∠AT B = ∠BT C = ∠CT A = 120◦ (this point is called Toricelli's point). In this case the quadrilaterals AT CB  , AT BC  and BCT A are cyclic, so the circumcircles of the equilateral triangles pass through T . Here are some more problems. Problem 2.49 Let M be a point in the interior of the equilateral triangle ABC and let A , B  , C  be its projections onto the sides BC, CA and AB, respectively. Prove that the sum of lengths of the inradii of triangles MAC  , MBA and MCB  equals the sum of lengths of the inradii of triangles MAB  , MBC  and MCA (Fig. 2.23). Problem 2.50 Let I be the incenter of triangle ABC. It is known that for every point M ∈ (AB), one can find the points N ∈ (BC) and P ∈ (AC) such that I is the centroid of triangle MNP . Prove that ABC is an equilateral triangle. Problem 2.51 Let ABC be an acute triangle. The interior bisectors of the angles ∠B and ∠C meet the opposite sides in the points L and M, respectively. Prove that there exists a point K in the interior of the side BC such that triangle KLM is equilateral if and only if ∠A = 60◦ .  58  2  Geometry and Trigonometry  Fig. 2.23  Problem 2.52 Let P1 P2 . . . Pn be a convex polygon with the following property: for any two vertices Pi and Pj , there exists a vertex Pk such that ∠Pi Pk Pj = 60◦ . Prove that the polygon is an equilateral triangle. Problem 2.53 From a point on the circumcircle of an equilateral triangle ABC parallels to the sides BC, CA and AB are drawn, intersecting the sides CA, AB and BC at the points M, N, P , respectively. Prove that the points M, N, P are collinear. Problem 2.54 Let P be a point on the circumcircle of an equilateral triangle ABC. Prove that the projections of any point Q on the lines P A, P B and P C are the vertices of an equilateral triangle.  2.6 The "Carpets" Theorem We start with a textbook problem. Problem 2.55 Let M and N be the midpoints of the sides AB and BC of the square ABCD. Let P = AN ∩ DM, Q = AN ∩ CM and R = CM ∩ DN . Prove the equality [AMP ] + [BMQN] + [CNR] = [DP QR].  2.6 The "Carpets" Theorem  59  Fig. 2.24  Solution Let us try brute force (Fig. 2.24). Assume with no loss of generality that the square's area equals 1. Since the figure is symmetric with respect to BD, it suffices to prove that [AMP ] + [BMQ] = [DP Q]. The triangles AQD and NQB are similar, so AQ AD = = 2. QN BN It follows that 1 2 [AQB] = [ABN ] = 3 6 and then [BMQ] =  1 . 12  Let N  = AN ∩ CD. Then triangles AMP and N  DP are also similar and PM 1 AM = . =  PD DN 4 Consequently, 1 1 [AMP ] = [AMD] = . 5 20 Finally, it is easy to see that 4 PQ = , AD 15 and [P QD] =  4 2 [AND] = . 15 15  60  2  Geometry and Trigonometry  Fig. 2.25 Fig. 2.26  Now, 1 2 1 + = 12 20 15 and we are done. However, this is an inelegant solution. Fortunately, there exists a much simpler one, with no computations and that works for arbitrary points M and N on the respective sides! First, let us see the "carpets" theorem. Suppose that the floor of a rectangular room is completely covered by a collection of nonoverlapping carpets. If we move one of the carpets, then clearly the overlapping area is equal to the uncovered area of the floor (see Fig. 2.25). Of course, the shape of the room or the shape of the carpets are irrelevant. Now, let us return to Problem 2.55, taking M and N at arbitrary positions: The "room" is ABCD and the "carpets" are triangles ADN and CDM (Fig. 2.26). Since 1 [ADN ] = [CDM] = [ABCD], 2 the two carpets would completely cover the room if they did not overlap. Hence the area of the overlapping surface, that is, [DP QR], equals the area of the uncovered  2.6 The "Carpets" Theorem  61  Fig. 2.27  Fig. 2.28  surface, i.e. [AMP ] + [BMQN] + [CNR]. Arrange some carpets to solve the following problems. Problem 2.56 Let ABCD be a parallelogram. The points M, N and P are chosen on the segments BD, BC and CD, respectively, such that CNMP is a parallelogram. Let E = AN ∩ BD and F = AP ∩ BD. Prove that [AEF ] = [DF P ] + [BEN]. Problem 2.57 Consider the quadrilateral ABCD. The points M, N, P and Q are the midpoints of the sides AB, BC, CD and DA (Fig. 2.27). Let X = AP ∩ BQ, Y = BQ ∩ CM, Z = CM ∩ DN and T = DN ∩ AP . Prove that [XY ZT ] = [AQX] + [BMY ] + [CNZ] + [DP T ]. Problem 2.58 Through the vertices of the smaller base AB of the trapezoid ABCD two parallel lines are drawn, intersecting the segment CD. These lines and the trapezoid's diagonals divide it into seven triangles and a pentagon (see Fig. 2.28). Show that the area of the pentagon equals the sum of areas of the three triangles sharing a common side with the trapezoid.  62  2  Geometry and Trigonometry  Fig. 2.29  Problem 2.59 Let M be a point in the interior of triangle ABC. Three lines are drawn through M, parallel to triangle's sides, determining three trapezoids. One draws a diagonal in each trapezoid such that they have no common endpoints, dividing thus ABC into seven parts, four of them being triangles (see Fig. 2.29). Prove that the area of one of the four triangles equals the sum of the areas of the other three.  2.7 Quadrilaterals with an Inscribed Circle Everybody knows that in any triangle one can inscribe a circle whose center is at the intersection point of the angles' bisectors. What can we say about a quadrilateral? If there exists a circle touching all the quadrilateral's sides, then its center is equidistant from them, hence it lies on all four angle bisectors. We deduce that a necessary and sufficient condition for the existence of an inscribed circle is that the quadrilateral's angle bisectors are concurrent (in fact, this works for arbitrary convex polygons). This does not happen in every quadrilateral. We can always draw a circle tangent to three of the four sides (its center being the point of intersection of two of the bisectors) (Fig. 2.30). If three of the four angle bisectors meet at one point, it is easy to see that the fourth one will also pass through that point and that a circle can be inscribed in the quadrilateral. Another necessary and sufficient condition for the existence of an inscribed circle in a quadrilateral is given by the following theorem, due to Pithot. Theorem Let ABCD be a convex quadrilateral. There exists a circle inscribed in ABCD if and only if: AB + CD = AD + BC. Proof Suppose there exists a circle inscribed in the quadrilateral, touching the sides AB, BC, CD and DA at the points K, L, M, N , respectively. Then, since the tan-  2.7 Quadrilaterals with an Inscribed Circle  63  Fig. 2.30  Fig. 2.31  gents from a point to a circle have equal lengths, we have AK = AN, BK = BL, CM = CL and DM = DN (Fig. 2.31). If we add up these equalities, we obtain the desired result.  Conversely, suppose AB + CD = AD + BC. Draw a circle tangent to AB, BC and CD. If the circle is not tangent to AD, draw from A the tangent to the circle and let E be the point of intersection with CD. Suppose, for instance, that E lies in the interior of CD (Fig. 2.32). Since the circle is inscribed in the quadrilateral ABCE, we have AB + CE = AE + BC. On the other hand, from the hypothesis, we have AB + CD = AD + BC, or AB + CE + ED = AD + BC. From these, we derive ED + AE = AD, which is impossible. It follows that the circle is also tangent to AD, hence it is inscribed in ABCD. If E lies outside the line segment CD, the proof is almost identical.  64  2  Geometry and Trigonometry  Fig. 2.32  Fig. 2.33  Another nice proof of the converse is the following: if AB = AD then BC = CD and the conclusion is immediate. Suppose, with no loss of generality, that AB < AD, and let X ∈ AD be such that AB = AX. Let Y ∈ CD be such that DX = DY . Since AB + CD = AD + BC, it follows that CY = BC (Fig. 2.33). Thus, the triangles ABX, DXY and CY B are isosceles, so the perpendicular bisectors of the sides BX, XY and Y B of triangle BXY are also the angle bisectors of ∠A, ∠D, and ∠C of the quadrilateral. Since the perpendicular bisectors of the sides of a triangle are concurrent, we obtain the desired conclusion. Problem 2.60 Prove that if in the quadrilateral ABCD is inscribed a circle with center O, then the sum of the angles ∠AOB and ∠COD equals 180◦ . Problem 2.61 Let ABCD be a quadrilateral with an inscribed circle. Prove that the circles inscribed in triangles ABC and ADC are tangent to each other. Problem 2.62 Let ABCD be a convex quadrilateral. Suppose that the lines AB and CD intersect at E and the lines AD and BC intersect at F , such that the points E and F lie on opposite sides of the line AC. Prove that the following statements are equivalent:  2.7 Quadrilaterals with an Inscribed Circle  65  Fig. 2.34  (i) a circle is inscribed in ABCD; (ii) BE + BF = DE + DF ; (iii) AE − AF = CE − CF . Problem 2.63 Let ABCD be a convex quadrilateral. Suppose that the lines AB and CD intersect at E and the lines AD and BC intersect at F . Let M and N be two arbitrary points on the line segments AB and BC, respectively. The line EN intersects AF and MF at P and R. The line MF intersects CE at Q. Prove that if the quadrilaterals AMRP and CNRQ have inscribed circles, then ABCD has an inscribed circle (Fig. 2.34).  Problem 2.64 The points A1 , A2 , C1 and C2 are chosen in the interior of the sides CD, BC, AB and AD of the convex quadrilateral ABCD. Denote by M the point of intersection of the lines AA2 and CC1 and by N the point of intersection of the lines AA1 and CC2 . Prove that if one can inscribe circles in three of the four quadrilaterals ABCD, A2 BC1 M, AMCN and A1 N C2 D, then a circle can be also inscribed in the fourth one. Problem 2.65 A line cuts a quadrilateral with an inscribed circle into two polygons with equal areas and equal perimeters. Prove that the line passes through the center of the inscribed circle. Problem 2.66 In the convex quadrilateral ABCD we have ∠B = ∠C = 120◦ , and AB 2 + BC 2 + CD 2 = AD 2 . Prove that ABCD has an inscribed circle. Problem 2.67 Let ABCD be a quadrilateral circumscribed about a circle, whose interior and exterior angles are at least 60◦ . Prove that 1 AB 3 − AD 3 ≤ BC 3 − CD 3 ≤ 3 AB 3 − AD 3 . 3 When does equality hold?  66  2  Geometry and Trigonometry  2.8 Dr. Trig Learns Complex Numbers It is known that every complex number z = a + bi can be written in the form z = r(cos θ + i sin θ ), √  where r = a 2 + b2 is the absolute value of z and θ is its argument. For instance, √ π π 2 π i = cos 2 + i sin 2 , 1 + i = 2 (cos 4 + i sin π4 ), etc. Also, if z = r(cos θ + i sin θ ), then a simple inductive argument proves that zn = r n (cos nθ + i sin nθ ) (known as de Moivre's formula). Now, if z = cos θ + i sin θ (that is, its absolute value equals 1) then 1 cos θ − i sin θ 1 = cos θ − i sin θ. = = z cos θ + i sin θ cos2 θ + sin2 θ We obtain the useful formulas   1 1 cos θ = z+ , 2 z  sin θ =    1 1 z− . 2i z  Moreover, using de Moivre's formula, we have     1 n 1 1 1 n sin nθ = z + n , z − n . cos nθ = 2 z 2i z These formulas may be very useful in solving a lot of Dr. Trig's problems. We might even forget some of his formulas. For instance, we have       1 2 1 1 2 1 1 1 z + 2 = z+ z+ cos 2θ = −1=2 2 2 z 2 z z  2  − 1 = 2 cos2 θ − 1.  Also   1 1 z+ 2 z  3        1 3 3 1 3 3 1 1 1 = + = z + 3z + + 3 z + 3 z+ . 8 z z 8 z 8 z  We deduce cos3 θ =  1 3 cos 3θ + cos θ, 4 4  a formula sometimes written as cos 3θ = 4 cos3 θ − 3 cos θ. Now, let us put some of this at work.  2.8 Dr. Trig Learns Complex Numbers  67  Problem 2.68 Let a, b, c be real numbers such that cos a + cos b + cos c = sin a + sin b + sin c = 0. Prove that cos 2a + cos 2b + cos 2c = sin 2a + sin 2b + sin 2c = 0. Solution Let x = cos a + i sin a, y = cos b + i sin b and z = cos c + i sin c. From the hypothesis we have x + y + z = 0, and also 1 1 1 + + = (cos a − i sin a) + (cos b − i sin b) + (cos c − i sin c) = 0. x y z It follows that xy + xz + yz = 0 so x 2 + y 2 + z2 = (x + y + z)2 − 2(xy + xz + yz) = 0. But then cos 2a + cos 2b + cos 2c + i(sin 2a + sin 2b + sin 2c) = 0, and we are done. Problem 2.69 Prove the equality cos  3π 5π 1 π + cos + cos = . 7 7 7 2  Solution Let z = cos  π π + i sin . 7 7  Then z7 = cos π + i sin π = −1, hence z7 + 1 = 0. On the other hand, we have       1 1 3π 5π 1 1 1 3 π 1 5 + cos = z+ + z + 3 + z + 5 cos + cos 7 7 7 2 z 2 2 z z =  z10 + z8 + z6 + z4 + z2 + 1 . 2z5  Since z7 + 1 = 0, we have z10 = −z3 and z8 = −z. It follows that z10 + z8 + z6 + z4 + z2 + 1 = z6 + z4 − z 3 + z 2 − z + 1 = z6 − z5 + z 4 − z 3 + z 2 − z + 1 + z 5 =  z7 + 1 + z 5 = z5 , z+1  68  2  Geometry and Trigonometry  hence cos  3π 5π z5 π 1 + cos + cos = 5= . 7 7 7 2 2z  Problem 2.70 Find a closed form for the sum Sn = sin a + sin 2a + · · · + sin na. Solution Let us ask for more: we will find a closed form for both Sn and Cn = cos a + cos 2a + · · · + cos na. Let z = cos a + i sin a. Then Cn + iSn = z + z2 + · · · + zn = z Since cos x − 1 = −2 sin2  x 2  zn − 1 . z−1  and sin x = 2 sin x2 cos x2 , we obtain  na na zn − 1 cos na + i sin na − 1 −2 sin2 na 2 + 2i sin 2 cos 2 = = z−1 cos a + i sin a − 1 −2 sin2 a2 + 2i sin a2 cos a2    na  cos na sin na sin na (n − 1)a (n − 1)a 2 2 + i sin 2 2 = cos = + i sin . sin a2 cos a2 + i sin a2 sin a2 2 2  Thus   sin na (n − 1)a (n − 1)a 2 cos + i sin sin a2 2 2   sin na (n + 1)a (n + 1)a 2 cos = + i sin . sin a2 2 2  Cn + iSn = (cos a + i sin a)  Finally Sn =  (n+1)a sin na 2 sin 2 , sin a2  Cn =  (n+1)a sin na 2 cos 2 . sin a2  Now, help Dr. Trig to solve the following problems. Problem 2.71 Let a, b, c be real numbers such that cos a + cos b + cos c = sin a + sin b + sin c = 0. Prove that 1 cos(a + b + c) = (cos 3a + cos 3b + cos 3c), 3  2.8 Dr. Trig Learns Complex Numbers  1 sin(a + b + c) = (sin 3a + sin 3b + sin 3c). 3 Problem 2.72 Find the value of the product cos 20◦ cos 40◦ cos 80◦ . Problem 2.73 Prove that 1 1 1 1 + + = . ◦ ◦ ◦ cos 6 sin 24 sin 48 sin 12◦ Problem 2.74 Prove that cos  2π 4π 6π 1 + cos + cos + = 0. 7 7 7 2  Problem 2.75 Prove the equality √ n 2π (n − 1)π π · · · sin = n−1 . sin sin n n n 2 Problem 2.76 Solve the equation sin x + sin 2x + sin 3x = cos x + cos 2x + cos 3x. Problem 2.77 Prove that  √ 1+ 5 π . cos = 5 4  69  Chapter 3  Number Theory and Combinatorics  3.1 Arrays of Numbers Many Olympiad problems refer to arrays of numbers. Let us start with some examples. Problem 3.1 The numbers 1, 2, . . . , n2 are arranged in an n × n array in the following way: 1 n+1 .. .  2 n+2  3 n+3  ... ...  n 2n .. .  n2 − n + 1  n2 − n + 2  n2 − n + 3  ...  n2  Pick n numbers from the array such that any two numbers are in different rows and different columns. Find the sum of these numbers. Solution If we denote by aij the number in the ith row and j th column then aij = (i − 1)n + j for all i, j = 1, 2, . . . , n. Because any two numbers are in different rows and different columns, it follows that from each row and each column exactly one number is chosen. Let a1j1 , a2j2 , . . . , anjn be the chosen numbers, where j1 , j2 , . . . , jn is a permutation of indices 1, 2, . . . , n. We have n  k=1  akjk =  n    n n    (k − 1) + jk . (k − 1)n + jk = n  k=1  k=1  k=1  But n  k=1  jk =  n(n + 1) 2  T. Andreescu, B. Enescu, Mathematical Olympiad Treasures, DOI 10.1007/978-0-8176-8253-8_3, © Springer Science+Business Media, LLC 2011  71  72  3  Number Theory and Combinatorics  since j1 , j2 , . . . , jn is a permutation of indices 1, 2, . . . , n. It follows that n   akjk =  k=1  n(n2 + 1) . 2  Problem 3.2 The entries of an n × n array of numbers are denoted by xij , with 1 ≤ i, j ≤ n. For all i, j, k, 1 ≤ i, j, k ≤ n the following equality holds xij + xj k + xki = 0. Prove that there exist numbers t1 , t2 , . . . , tn such that xij = ti − tj for all i, j , 1 ≤ i, j ≤ n. Solution Setting i = j = k in the given condition yields 3xii = 0, hence xii = 0 for all i, 1 ≤ i ≤ n. For k = j we obtain xij + xjj + xj i = 0, hence xij = −xj i , for all i, j . Now fix i and j and add up the equalities xij + xj k + xki = 0 for k = 1, 2, . . . , n. It follows that nxij +  n   n   xj k +  k=1  xki = 0  k=1  or nxij +  n   xj k −  k=1  n   xik = 0.  k=1  If we define 1 xik , n n  ti =  k=1  we obtain xij = ti − tj , for all i, j , as desired.  3.1 Arrays of Numbers  73  Problem 3.3 Prove that among any 10 entries of the table 0 1 2 3 9 0 1 2 8 9 0 1 .. .  ... 9 ... 8 ... 7  1 2 3 4  ... 0  situated in different rows and different columns, at least two are equal. Solution Denote by aij the entries of the table, 1 ≤ i, j ≤ 10 and observe that aij = ahk if and only if i − j ≡ h − k (mod 10). Let aiji , i = 1, 2, . . . , 10 be 10 entries situated in different rows and different columns. If these entries are all different, then the differences i − ji give distinct residues mod 10, hence 10   (i − ji ) ≡ 0 + 1 + · · · + 9 ≡ 5 (mod 10).  i=1  On the other hand, since j1 , j2 , . . . , j10 is a permutation of the indices 1, 2, . . . , 10, we have 10   (i − ji ) =  i=1  10  i=1  i−  10   ji = 0,  i=1  hence 0 ≡ 5 (mod 10), a contradiction. Here are some proposed problems. Problem 3.4 Prove that the sum of any n entries of the table 1 1 2  1 2 1 3  1 3 1 4  ... ...  1 n 1 n+1  1 n+1  1 n+2  ...  1 2n−1  .. . 1 n  situated in different rows and different columns is not less than 1. Problem 3.5 The entries of an n × n array of numbers are denoted by aij , 1≤ i, j ≤ n. The sum of any n entries situated on different rows and different columns is the same. Prove that there exist numbers x1 , x2 , . . . , xn and y1 , y2 , . . . , yn , such that aij = xi + yj , for all i, j .  74  3  Number Theory and Combinatorics  Problem 3.6 In an n × n array of numbers all rows are different (two rows are different if they differ in at least one entry). Prove that there is a column which can be deleted in such a way that the remaining rows are still different. Problem 3.7 The positive integers from 1 to n2 (n ≥ 2) are placed arbitrarily on squares of an n × n chessboard. Prove that there exist two adjacent squares (having a common vertex or a common side) such that the difference of the numbers placed on them is not less than n + 1. Problem 3.8 A positive integer is written in each square of an n2 × n2 chess board. The difference between the numbers in any two adjacent squares (sharing an edge) is less than or equal to n. Prove that at least  n2  + 1 squares contain the same number. Problem 3.9 The numbers 1, 2, . . . , 100 are arranged in the squares of an 10 × 10 table in the following way: the numbers 1, . . . , 10 are in the bottom row in increasing order, numbers 11, . . . , 20 are in the next row in increasing order, and so on. One can choose any number and two of its neighbors in two opposite directions (horizontal, vertical, or diagonal). Then either the number is increased by 2 and its neighbors are decreased by 1, or the number is decreased by 2 and its neighbors are increased by 1. After several such operations the table again contains all the numbers 1, 2, . . . , 100. Prove that they are in the original order. Problem 3.10 Prove that one cannot arrange the numbers from 1 to 81 in a 9 × 9 table such that for each i, 1 ≤ i ≤ 9 the product of the numbers in row i equals the product of the numbers in column i. Problem 3.11 The entries of a matrix are integers. Adding an integer to all entries on a row or on a column is called an operation. It is given that for infinitely many integers N one can obtain, after a finite number of operations, a table with all entries divisible by N . Prove that one can obtain, after a finite number of operations, the zero matrix.  3.2 Functions Defined on Sets of Points Several Olympiad problems deal with functions defined on certain sets of points. These problems are interesting in that they combine both geometrical and algebraic ideas. Problem 3.12 Let n > 2 be an integer and f : P → R a function defined on the set of points in the plane, with the property that for any regular n-gon A1 A2 . . . An , f (A1 ) + f (A2 ) + · · · + f (An ) = 0. Prove that f is the zero function.  3.2 Functions Defined on Sets of Points  75  Solution Let A be an arbitrary point. Consider a regular n-gon AA1 A2 . . . An−1 . Let k be an integer, 0 ≤ k ≤ n − 1. A rotation with center A of angle 2kπ n sends the polygon AA1 A2 . . . An−1 to Ak0 Ak1 . . . Ak,n−1 , where Ak0 = A and Aki is the image of Ai , for all i = 1, 2, . . . , n − 1. From the condition of the statement, we have n−1  n−1   f (Aki ) = 0.  k=0 i=0  Observe that in the sum the number f (A) appears n times, therefore nf (A) +  n−1  n−1   f (Aki ) = 0.  k=0 i=1  On the other hand, we have n−1  n−1   f (Aki ) =  k=0 i=1  n−1  n−1   f (Aki ) = 0,  i=1 k=0  since the polygons A0i A1i . . . An−1,i are all regular n-gons. From the two equalities above we deduce f (A) = 0, hence f is the zero function. Problem 3.13 Let n ≥ 4 be an integer and let p ≥ 2n − 3 be a prime number. Let S be a set of n points in the plane, no three of which are collinear, and let f : S → {0, 1, . . . , p − 1} be a function such that 1. there exists a unique point A ∈ S such that f (A) = 0; 2. if C(X, Y, Z) is the circle determined by the distinct points X, Y, Z ∈ S, then  f (P ) ≡ 0 (mod p). P ∈S∩C(X,Y,Z)  Prove that all points of S lie on a circle. Solution Suppose there exist points B and C such that no other point of S lies on C(A, B, C). We have f (B) + f (C) ≡ 0 (mod p), so, if f (B) = i = 0, then f (C) = p − i. Let  σ= f (X). X∈S  If a number of b circles pass through A, B and other points of S and a number of c circles pass through A, C and other points of S, applying the condition from the  76  3  Number Theory and Combinatorics  Fig. 3.1  hypothesis to all these circles, we obtain σ + (b − 1)i ≡ 0 (mod p), σ + (c − 1)(p − i) ≡ 0 (mod p), hence b + −2 ≡ 0 (mod p). Since 1 ≤ b, c ≤ n − 2, we have 2 ≤ b + c ≤ 2n − 4 < p, hence b = c = 1, which is a contradiction. It follows that for any points B, C ∈ S, there exists at least one more point of S lying on C(A, B, C). This implies the fact that all the points of S lie on a circle. Indeed, consider an inversion I of pole A. The set of points S − {A} is transformed into the set of points I (S − {A}) = N and the circles C(A, X, Y ), with X, Y ∈ S are transformed into lines IX IY through points of N . The above condition then reduces to the following: for any two points IX , IY of N , there exists at least one other point of N lying on the line IX IY . We can prove that all points of N are collinear, whence the points of S lie on a circle. Indeed, suppose the points are not collinear and choose points A, B, C such that the distance from C to the line AB is minimal. Let C be the projection of C on the line AB. From the hypothesis it follows that there exists another point D ∈ N on the line AB. The point C divides the line AB into two half lines and at least two of the points A, B, D lie in one of these half lines. Suppose these points are B and D located as in Fig. 3.1. If B is a point on CD such that BB is parallel to CC and B is the projection of B on CD, it is not difficult to see that BB < BB < CC , contradicting the minimality of CC . Here are more examples. Problem 3.14 Let D be the union of n ≥ 1 concentric circles in the plane. Suppose that the function f : D → D satisfies   d f (A), f (B) ≥ d(A, B) for every A, B ∈ D (d(M, N ) is the distance between the points M and N ). Prove that   d f (A), f (B) = d(A, B) for every A, B ∈ D.  3.3 Count Twice!  77  Problem 3.15 Let S be a set of n ≥ 4 points in the plane, such that no three of them are collinear and not all of them lie on a circle. Find all functions f : S → R with the property that for any circle C containing at least three points of S,  f (P ) = 0. P ∈C∩S  Problem 3.16 Let P be the set of all points in the plane and L be the set of all lines of the plane. Find, with proof, whether there exists a bijective function f : P → L such that for any three collinear points A, B, C, the lines f (A), f (B) and f (C) are either parallel or concurrent. Problem 3.17 Let S be the set of interior points of a sphere and C be the set of interior points of a circle. Find, with proof, whether there exists a function f : S → C such that d(A, B) ≤ d(f (A), f (B)), for any points A, B ∈ S. Problem 3.18 Let S be the set of all polygons in the plane. Prove that there exists a function f : S → (0, +∞) such that 1. f (P ) < 1, for any P ∈ S; 2. If P1 , P2 ∈ S have disjoint interiors and P1 ∪ P2 ∈ S, then f (P1 ∪ P2 ) = f (P1 ) + f (P2 ).  3.3 Count Twice! Many interesting results can be obtained by counting the elements of a set in two different ways. Moreover, counting twice can be a good problem solving strategy. Let us consider the following examples. Problem 3.19 In how many ways can a committee of k persons with a chairman be chosen from a set of n people?   Solution We can choose the k members of the committee in nk ways and then n the chairman in k ways, so that the answer is k k . On the other hand, we can first choose the chairman (this can be done in n ways) and next the rest  of k − 1 members from the remaining n − 1 persons, leading to a total of n n−1 k−1 possibilities. Thus, we obtain the following identity:     n n−1 k =n . k k−1 Problem 3.20 Consider a finite sequence of real numbers the sum of any 7 consecutive terms is negative and the sum of any 11 consecutive terms is positive. Find the greatest number of terms of such a sequence.  78  3  Number Theory and Combinatorics  Solution It is not difficult to see that such a sequence cannot have 77 or more terms. For that, we add up in two ways the first 77 terms, obtaining a contradiction: (x1 + x2 + · · · + x7 ) + (x8 + x9 + · · · + x14 ) + · · · + (x71 + x72 + · · · + x77 ) < 0, (x1 + x2 + · · · + x11 ) + (x12 + x13 + · · · + x22 ) + · · · + (x67 + x68 + · · · + x77 ) > 0. In fact, the number of terms is much less. The sequence cannot contain more than 16 terms. To prove that, we refine our double counting technique. Suppose the sequence has at least 17 terms. We can arrange them in a 7 × 11 table as follows: ⎛ ⎞ x1 x2 . . . x10 x11 ⎜ x2 x3 . . . x11 x12 ⎟ ⎜ ⎟ ⎜ .. .. .. .. ⎟ ⎜ . . . . ⎟ ⎜ ⎟ ⎝ x6 x7 . . . x15 x16 ⎠ x7 x8 . . . x16 x17 Now, add up all the entries in two ways: by rows and by columns. We again reach a contradiction. Finally, there is an example of such a sequence with 16 terms: 5, 5, −13, 5, 5, 5, −13, 5, 5, −13, 5, 5, 5, −13, 5, 5. Problem 3.21 Prove the equality   ϕ(d) = n,  d|n  where ϕ denotes Euler's totient function. Solution The Euler's totient function ϕ(n)              

Posted by: margetlaceye0193723.blogspot.com

Source: https://b-ok.cc/book/1188197/b6c666

Share :