How to Guard an Art Gallery and Other Discrete Mathematical Adventures

Contents

Contents Preface ix 1 How to Count Pizza Pieces 1 1.1 The Pizza-Cutter’s Problem . . . . . . . . . . . 1 1.2 A Recurring Theme . . . . . . . . . . . . . . . . 4 1.3 Make a Difference . . . . . . . . . . . . . . . . . 7 1.4 How Many Toppings? . . . . . . . . . . . . . . . 9 1.5 Proof without Words . . . . . . . . . . . . . . . 12 1.6 Count ’em and Sweep . . . . . . . . . . . . . . . 14 1.7 Euler’s Formula for Plane Graphs . . . . . . . 16 1.8 You Can Look It Up . . . . . . . . . . . . . . . . 20 1.9 Pizza Envy . . . . . . . . . . . . . . . . . . . . . 21 1.10 Notes and References . . . . . . . . . . . . . . . 22 1.11 Problems . . . . . . . . . . . . . . . . . . . . . . 24 2 Count on Pick’s Formula 33 2.1 The Orchard and the Dollar . . . . . . . . . . . 33 2.2 The Area of the Orchard . . . . . . . . . . . . . 34 2.3 Twenty-nine Ways to Change a Dollar . . . . 37 2.4 Lattice Polygons and Pick’s Formula . . . . . 42 2.5 Making Change . . . . . . . . . . . . . . . . . . . 46 2.6 Pick’s Formula: First Proof . . . . . . . . . . . 48 2.7 Pick’s Formula: Second Proof . . . . . . . . . . 53 2.8 Batting Averages and Lattice Points . . . . . . 56 2.9 Three Dimensions and N-largements . . . . . 58 2.10 Notes and References . . . . . . . . . . . . . . . 65 2.11 Problems . . . . . . . . . . . . . . . . . . . . . . 66 3 How to Guard an Art Gallery 73 3.1 The Sunflower Art Gallery . . . . . . . . . . . . 73 v vi C o n t en t s 3.2 Art Gallery Problems . . . . . . . . . . . . . . . 75 3.3 The Art Gallery Theorem . . . . . . . . . . . . 81 3.4 Colorful Consequences . . . . . . . . . . . . . . 83 3.5 Triangular and Chromatic Assumptions . . . 86 3.6 Modern Art Galleries . . . . . . . . . . . . . . . 88 3.7 Art Gallery Sketches . . . . . . . . . . . . . . . 89 3.8 Right-Angled Art Galleries . . . . . . . . . . . . 93 3.9 Guarding the Guards . . . . . . . . . . . . . . . 96 3.10 Three Dimensions and the Octoplex . . . . . 102 3.11 Notes and References . . . . . . . . . . . . . . . 106 3.12 Problems . . . . . . . . . . . . . . . . . . . . . . 107 4 Pixels, Lines, and Leap Years 113 4.1 Pixels and Lines . . . . . . . . . . . . . . . . . . 113 4.2 Lines and Distances . . . . . . . . . . . . . . . . 116 4.3 Arithmetic Arrays . . . . . . . . . . . . . . . . . 118 4.4 Bresenham’s Algorithm . . . . . . . . . . . . . 123 4.5 A Touch of Gray: Antialiasing . . . . . . . . . 124 4.6 Leap Years and Line Drawing . . . . . . . . . . 125 4.7 Diophantine Approximations . . . . . . . . . . 128 4.8 Notes and References . . . . . . . . . . . . . . . 134 4.9 Problems . . . . . . . . . . . . . . . . . . . . . . 135 5 Measure Water with a Vengeance 139 5.1 Simon Says: Measure Water . . . . . . . . . . . 139 5.2 A Recipe for Bruce Willis . . . . . . . . . . . . . 142 5.3 Skew Billiard Tables . . . . . . . . . . . . . . . . 144 5.4 Big Problems . . . . . . . . . . . . . . . . . . . . 147 5.5 How to Measure Water: An Algorithm . . . . 148 5.6 Arithmetic Arrays: Climb the Staircase . . . . 151 5.7 Other Problems to Pour Over . . . . . . . . . . 155 5.8 Number Theory and Fermat’s Congruence . . 160 5.9 Notes and References . . . . . . . . . . . . . . . 164 5.10 Problems . . . . . . . . . . . . . . . . . . . . . . 165 C o n t e n t s vii 6 From Stamps to Sylver Coins 169 6.1 Sylvester’s Stamps . . . . . . . . . . . . . . . . 169 6.2 Addition Tables and Symmetry . . . . . . . . . 173 6.3 Arithmetic Arrays and Sylvester’s Formula . 176 6.4 Beyond Sylvester: The Stamp Theorem . . . . 180 6.5 Chinese Remainders . . . . . . . . . . . . . . . 186 6.6 The Tabular Sieve . . . . . . . . . . . . . . . . . 188 6.7 McNuggets and Coin Exchanges . . . . . . . . 190 6.8 Sylver Coinage . . . . . . . . . . . . . . . . . . . 194 6.9 Notes and References . . . . . . . . . . . . . . . 196 6.10 Problems . . . . . . . . . . . . . . . . . . . . . . 198 7 Primes and Squares: Quadratic Residues 207 7.1 Primes and Squares . . . . . . . . . . . . . . . . 207 7.2 Quadratic Residues Are Squares . . . . . . . . 208 7.3 Errors: Detection amd Correctipn . . . . . . . 212 7.4 Multiplication Tables, Legendre, and Euler . . 216 7.5 Some Square Roots . . . . . . . . . . . . . . . . 221 7.6 Marcia and Greg Flip a Coin . . . . . . . . . . . 224 7.7 Round Up at the Gauss Corral . . . . . . . . . 226 7.8 It’s the Law: Quadratic Reciprocity . . . . . . 232 7.9 Notes and References . . . . . . . . . . . . . . . 239 7.10 Problems . . . . . . . . . . . . . . . . . . . . . . 240 References 245 Index 251 This page intentionally left blank ...