The Art and Craft of Problem Solving

Appealing to everyone from college-level majors to independent learners, The Art and Craft of Problem Solving, 3rd Edition introduces a problem-solving approach to mathematics, as opposed to the traditional exercises approach. The goal of The Art and Craft of Problem Solving is to develop strong problem solving skills, which it achieves by encouraging students to do math rather than just study it. Paul Zeitz draws upon his experience as a coach for the international mathematics Olympiad to give students an enhanced sense of mathematics and the ability to investigate and solve problems.

1 What This Book Is About and How to Read It 1 1.1 “Exercises” vs. “Problems” 1 1.2 The Three Levels of Problem Solving 3 1.3 A Problem Sampler 6 1.4 How to Read This Book 9 2 Strategies for Investigating Problems 12 2.1 Psychological Strategies 12 Mental Toughness: Learn from Pólya’s Mouse 13 Creativity 15 2.2 Strategies for Getting Started 23 The First Step: Orientation 23 I’m Oriented. Now What? 24 2.3 Methods of Argument 37 Common Abbreviations and Stylistic Conventions 37 Deduction and Symbolic Logic 38 Argument by Contradiction 39 Mathematical Induction 42 2.4 Other Important Strategies 49 Draw a Picture! 49 Pictures Don’t Help? Recast the Problem in Other Ways! 51 Change Your Point of View 55 3 Tactics for Solving Problems 58 3.1 Symmetry 59 Geometric Symmetry 60 Algebraic Symmetry 64 3.2 The Extreme Principle 70 3.3 The Pigeonhole Principle 80 Basic Pigeonhole 80 Intermediate Pigeonhole 82 Advanced Pigeonhole 83 3.4 Invariants 88 Parity 90 Modular Arithmetic and Coloring 95 Monovariants 97 4 Three Important Crossover Tactics 105 4.1 Graph Theory 105 Connectivity and Cycles 107 Eulerian and Hamiltonian Walks 108 The Two Men of Tibet 111 4.2 Complex Numbers 116 Basic Operations 116 Roots of Unity 122 Some Applications 123 4.3 Generating Functions 128 Introductory Examples 129 Recurrence Relations 130 Partitions 132 4.4 Interlude: A few Mathematical Games 138 5 Algebra 143 5.1 Sets, Numbers, and Functions 143 Sets 143 Functions 145 5.2 Algebraic Manipulation Revisited 147 The Factor Tactic 148 Manipulating Squares 149 Substitutions and Simplifications 150 5.3 Sums and Products 157 Notation 157 Arithmetic Series 158 Geometric Series and the Telescope Tool 158 Infinite Series 161 5.4 Polynomials 164 Polynomial Operations 165 The Zeros of a Polynomial 165 5.5 Inequalities 174 Fundamental Ideas 174 The AM-GM Inequality 177 Massage, Cauchy-Schwarz, and Chebyshev 181 6 Combinatorics 189 6.1 Introduction to Counting 189 Permutations and Combinations 189 Combinatorial Arguments 192 Pascal’s Triangle and the Binomial Theorem 193 Strategies and Tactics of Counting 195 6.2 Partitions and Bijections 197 Counting Subsets 197 Information Management 200 Balls in Urns and Other Classic Encodings 203 6.3 The Principle of Inclusion-Exclusion 207 Count the Complement 207 PIE with Sets 208 PIE with Indicator Functions 212 6.4 Recurrence 215 Tiling and the Fibonacci Recurrence 215 The Catalan Recurrence 217 7 Number Theory 224 7.1 Primes and Divisibility 224 The Fundamental Theorem of Arithmetic 224 GCD, LCM, and the Division Algorithm 226 7.2 Congruence 232 What’s So Good About Primes? 233 Fermat’s Little Theorem 234 7.3 Number Theoretic Functions 236 Divisor Sums 237 Phi and Mu 238 7.4 Diophantine Equations 242 General Strategy and Tactics 242 7.5 Miscellaneous Instructive Examples 249 Can a Polynomial Always Output Primes? 249 If You Can Count It, It’s an Integer 250 A Combinatorial Proof of Fermat’s Little Theorem 250 Sums of Two Squares 251 8 Geometry for Americans 258 8.1 Three “Easy” Problems 258 8.2 Survival Geometry I 259 Points, Lines, Angles, and Triangles 260 Parallel Lines 262 Circles and Angles 265 Circles and Triangles 267 8.3 Survival Geometry II 271 Area 271 Similar Triangles 275 Solutions to the Three “Easy” Problems 277 8.4 The Power of Elementary Geometry 283 Concyclic Points 284 Area, Cevians, and Concurrent Lines 287 Similar Triangles and Collinear Points 290 Phantom Points and Concurrent Lines 293 8.5 Transformations 297 Symmetry Revisited 297 Rigid Motions and Vectors 299 Homothety 306 Inversion 308 9 Calculus 316 9.1 The Fundamental Theorem of Calculus 316 9.2 Convergence and Continuity 318 Convergence 319 Continuity 324 Uniform Continuity 325 9.3 Differentiation and Integration 329 Approximation and Curve Sketching 329 The Mean Value Theorem 332 A Useful Tool 335 Integration 336 Symmetry and Transformations 338 9.4 Power Series and Eulerian Mathematics 342 Don’t Worry! 342 Taylor Series with Remainder 344 Eulerian Mathematics 347 Beauty, Simplicity, and Symmetry: The Quest for a Moving Curtain 350 References 355 Index 357