Putnam-and-beyond.pdf

216930

Putnam and Beyond

Rùazvan Gelca

Titu Andreescu

Putnam and Beyond

Rùazvan Gelca

Texas Tech University

Department of Mathematics and Statistics

MA 229

Lubbock, TX 79409

USA rgelca@gmail.com

Titu Andreescu

University of Texas at Dallas

School of Natural Sciences and Mathematics

2601 North Floyd Road

Richardson, TX 75080

USA titu.andreescu@utdallas.edu

Cover design by Mary Burgess.

Library of Congress Control Number:2007923582

ISBN-13: 978-0-387-25765-5 e-ISBN-13: 978-0-387-68445-1

Printed on acid-free paper.

c?2007 Springer Science+Business Media, LLC

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) and the

author, 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 identiÞed

as such, is not to be taken as an expression of opinion as to whether or not they are subject to proprietary rights.

987654321

springer.com(JLS/HP)

Life is good for only two things, discovering

mathematics and teaching mathematics.

SimÈon Poisson

Contents

Preface............................................................xi AStudy Guide......................................................xv

1 Methods of Proof................................................1

1.1 Argument by Contradiction...................................... 1

1.2 Mathematical Induction......................................... 3

1.3 The Pigeonhole Principle........................................ 11

1.4 Ordered Sets and Extremal Elements.............................. 14

1.5 Invariants and Semi-Invariants................................... 19

2 Algebra........................................................25

2.1 Identities and Inequalities....................................... 25

2.1.1 Algebraic Identities....................................... 25

2.1.2x

2 ?0.................................................. 28

2.1.3 The Cauchy-Schwarz Inequality............................ 32

2.1.4 The Triangle Inequality................................... 36

2.1.5 TheArithmetic Mean-Geometric Mean Inequality............. 39

2.1.6 Sturm's Principle......................................... 42

2.1.7 Other Inequalities........................................ 45

2.2 Polynomials................................................... 45

2.2.1 AWarmup.............................................. 45

2.2.2 Viète's Relations......................................... 47

2.2.3 The Derivative of a Polynomial............................. 52

2.2.4 The Location of the Zeros of a Polynomial................... 54

2.2.5 Irreducible Polynomials................................... 56

2.2.6 Chebyshev Polynomials................................... 58

viii Contents

2.3 LinearAlgebra................................................. 61

2.3.1 Operations with Matrices.................................. 61

2.3.2 Determinants............................................ 63

Putnam and Beyond

Rùazvan Gelca

Titu Andreescu

Putnam and Beyond

Rùazvan Gelca

Texas Tech University

Department of Mathematics and Statistics

MA 229

Lubbock, TX 79409

USA rgelca@gmail.com

Titu Andreescu

University of Texas at Dallas

School of Natural Sciences and Mathematics

2601 North Floyd Road

Richardson, TX 75080

USA titu.andreescu@utdallas.edu

Cover design by Mary Burgess.

Library of Congress Control Number:2007923582

ISBN-13: 978-0-387-25765-5 e-ISBN-13: 978-0-387-68445-1

Printed on acid-free paper.

c?2007 Springer Science+Business Media, LLC

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) and the

author, 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 identiÞed

as such, is not to be taken as an expression of opinion as to whether or not they are subject to proprietary rights.

987654321

springer.com(JLS/HP)

Life is good for only two things, discovering

mathematics and teaching mathematics.

SimÈon Poisson

Contents

Preface............................................................xi AStudy Guide......................................................xv

1 Methods of Proof................................................1

1.1 Argument by Contradiction...................................... 1

1.2 Mathematical Induction......................................... 3

1.3 The Pigeonhole Principle........................................ 11

1.4 Ordered Sets and Extremal Elements.............................. 14

1.5 Invariants and Semi-Invariants................................... 19

2 Algebra........................................................25

2.1 Identities and Inequalities....................................... 25

2.1.1 Algebraic Identities....................................... 25

2.1.2x

2 ?0.................................................. 28

2.1.3 The Cauchy-Schwarz Inequality............................ 32

2.1.4 The Triangle Inequality................................... 36

2.1.5 TheArithmetic Mean-Geometric Mean Inequality............. 39

2.1.6 Sturm's Principle......................................... 42

2.1.7 Other Inequalities........................................ 45

2.2 Polynomials................................................... 45

2.2.1 AWarmup.............................................. 45

2.2.2 Viète's Relations......................................... 47

2.2.3 The Derivative of a Polynomial............................. 52

2.2.4 The Location of the Zeros of a Polynomial................... 54

2.2.5 Irreducible Polynomials................................... 56

2.2.6 Chebyshev Polynomials................................... 58

viii Contents

2.3 LinearAlgebra................................................. 61

2.3.1 Operations with Matrices.................................. 61

2.3.2 Determinants............................................ 63