Problem Solving Tactics

About this book......Page 6
Problems......Page 14
Converse......Page 18
If and only if......Page 19
Contrapositive......Page 20
Proof by contradiction......Page 21
Proof by induction......Page 22
Strong induction......Page 24
Proof by exhaustion (case bashing)......Page 25
Pigeonhole principle......Page 26
Advanced pigeonhole principle......Page 28
Extremal principle......Page 29
Telescoping......Page 31
Problems......Page 32
Fundamental theorem of arithmetic......Page 37
Dealing with digits......Page 38
Floor function......Page 39
Square roots and conjugates......Page 40
Powers of two......Page 41
Euclid's algorithm......Page 42
Integers base-n......Page 44
Construction problems......Page 45
Chinese remainder theorem......Page 47
From Fermat to Euler......Page 48
Existence of a generator......Page 50
Problems......Page 52
Monotonicity......Page 56
Bounding arguments......Page 57
Polynomial modulus......Page 58
Modular arithmetic......Page 59
Divisibility and gcds......Page 60
Reduction of variables......Page 61
Infinite descent......Page 62
Vieta jumping......Page 63
Cyclotomic recognition......Page 64
Plane geometry......Page 66
Problems......Page 67
Cyclic quadrilaterals......Page 72
One step at a time......Page 73
Triangle centres......Page 75
Constructions......Page 77
Extend to the circumcircle......Page 79
Reverse reconstruction......Page 81
Trigonometry......Page 82
Areas......Page 83
Relate to known diagrams......Page 85
Create beautiful pictures......Page 86
Important configurations in geometry......Page 88
Angle bisector and perpendicular bisector......Page 89
Pivot theorem......Page 90
Radical axis theorem......Page 91
Similar switch......Page 92
Radical axis bisects common tangent......Page 93
Perpendicularity......Page 94
Alternate segment switch......Page 95
Ratios for collinearity......Page 96
Points of contact of incircle and excircle......Page 97
Circumcircle, incentre and excentre......Page 98
Simson line......Page 99
Pascal's theorem......Page 100
Desargues' theorem......Page 101
Quadrilateral and incircle......Page 102
Nine-point circle......Page 103
Euler line......Page 104
Four lines and four circles......Page 105
Newton–Gauss line......Page 106
Alternative characterisation of symmedian......Page 107
Convex cyclic hexagon and diagonals......Page 108
Quadrilateral, triangles and incircles......Page 109
Median, inradius and chord of incircle......Page 110
Incentre and midpoints......Page 111
Incentre, excentre, midpoint and contact points......Page 112
Incentre and chord of incircle......Page 113
Harmonic quadrilateral......Page 114
Incentre and mixtilinear incircle......Page 115
Butterfly theorem......Page 116
Problems......Page 118
Collinear points......Page 121
Menelaus' theorem......Page 122
Concurrent lines......Page 123
Ceva's theorem......Page 124
Concyclic points......Page 126
Power of a point......Page 130
Radical axes......Page 131
Ellipses......Page 132
Pascal's theorem......Page 135
Transformation geometry......Page 138
Problems......Page 139
Rotations......Page 143
Dilations......Page 144
Spiral symmetries......Page 146
Affine transformations......Page 147
Problems......Page 150
Addition ideas......Page 153
Angles......Page 154
Multiplication ideas......Page 155
Similarity ideas......Page 157
Roots of unity......Page 159
Polynomials......Page 162
Problems......Page 163
Division algorithm......Page 167
Fundamental theorem of algebra......Page 168
Vieta's formulas......Page 169
Integer polynomials......Page 171
Algebraic trickery......Page 173
Irreducibility......Page 175
Polynomials modulo p (upstairs–downstairs)......Page 176
Lagrange interpolation......Page 179
Root focus......Page 180
Problems......Page 182
Cauchy's functional equation......Page 186
Guess and hope......Page 187
Substitutions......Page 188
Injective, surjective and bijective......Page 189
The associative trick......Page 191
Involutions......Page 192
Fixed points......Page 193
Somewhere versus everywhere......Page 195
Completely multiplicative functions......Page 196
Well-ordering of N+......Page 197
Problems......Page 200
Squares are non-negative......Page 203
Rearrangement inequality......Page 204
Cauchy–Schwarz inequality......Page 206
Power means inequality......Page 208
Jensen's inequality......Page 209
Substitutions......Page 210
Addition and multiplication of inequalities......Page 211
Expand and conquer......Page 213
Homogeneous inequalities......Page 214
Muirhead's inequality......Page 215
Weighted inequalities......Page 216
Problems......Page 220
Reflection principle......Page 223
Transformations......Page 226
Trigonometry......Page 227
Parametrisation......Page 228
Ptolemy's inequality......Page 229
Locus and tangency......Page 232
Isoperimetric inequalities......Page 234
Triangle formulas......Page 235
Problems......Page 238
Subtraction and division......Page 241
Binomial identities......Page 242
Bijections......Page 244
The supermarket principle......Page 245
Pigeonhole principle......Page 246
Principle of inclusion–exclusion......Page 247
Double counting......Page 248
Injections......Page 250
Recursion......Page 251
Double counting via tables......Page 253
Combinatorial reciprocal principle......Page 254
Graph theory......Page 256
Problems......Page 257
Degree......Page 260
Connected graphs, cycles and trees......Page 261
Pigeonhole principle......Page 263
Euler trails......Page 264
Paths......Page 266
Extremal principle......Page 267
Count and count again......Page 268
Planar graphs......Page 269
Polyhedra......Page 270
Graph theory and inequalities......Page 271
Problems......Page 274
Number invariants......Page 280
Parity......Page 281
Modular arithmetic invariants......Page 282
Colouring invariants......Page 283
Monovariants......Page 285
Invariants as cost......Page 286
Permutation parity......Page 287
Combinatorial games......Page 288
Position analysis......Page 289
Pairing strategies......Page 290
Strategy stealing......Page 291
Problems......Page 294
Extremal principle......Page 298
Perturbation......Page 300
Discrete intermediate value theorem......Page 301
Convex hull......Page 302
Euler's formula......Page 303
Pigeonhole principle......Page 304
Colouring......Page 305
How do complex numbers work?......Page 306
Function notation......Page 309
Directed angles......Page 310
Some useful triangle formulas......Page 311
Index......Page 312