Proofs from THE BOOK

Cover......Page 1
Preface......Page 4
Preface to the Third Edition......Page 5
Table of Contents......Page 6
Number Theory......Page 8
1 Six proofs of the in nity of primes......Page 9
2 Bertrand's postulate......Page 13
3 Binomial coefficients are (almost) never powers......Page 19
4 Representing numbers as sums of two squares......Page 23
5 Every finite division ring is a field......Page 29
6 Some irrational numbers......Page 33
7 Three times π²/6......Page 40
Geometry......Page 48
8 Hilbert's third problem: decomposing polyhedra......Page 49
9 Lines in the plane and decompositions of graphs......Page 56
10 The slope problem......Page 61
11 Three applications of Euler's formula......Page 66
12 Cauchy's rigidity theorem......Page 72
13 Touching simplices......Page 76
14 Every large point set has an obtuse angle......Page 80
15 Borsuk's conjecture......Page 86
Analysis......Page 92
16 Sets, functions, and the continuum hypothesis......Page 93
17 In praise of inequalities......Page 108
18 A theorem of Polya on polynomials......Page 115
19 On a lemma of Littlewood and Offord......Page 121
20 Cotangent and the Herglotz trick......Page 125
21 Buffon's needle problem......Page 131
Combinatorics......Page 135
22 Pigeon-hole and double counting......Page 136
23 Three famous theorems on finite sets......Page 147
24 Shuffling cards......Page 152
25 Lattice paths and determinants......Page 162
26 Cayley's formula for the number of trees......Page 168
27 Completing Latin squares......Page 174
28 The Dinitz problem......Page 180
29 Identities versus bijections......Page 186
Graph Theory......Page 192
30 Five-coloring plane graphs......Page 193
31 How to guard a museum......Page 197
32 Turan's graph theorem......Page 201
33 Communicating without errors......Page 206
34 Of friends and politicians......Page 216
35 Probability makes counting (sometimes) easy......Page 219
Index......Page 227