How to Guard an Art Gallery and Other Discrete Mathematical Adventures
Search in google:
What is the maximum number of pizza slices one can get by making four straight cuts through a circular pizza? How does a computer determine the best set of pixels to represent a straight line on a computer screen? How many people at a minimum does it take to guard an art gallery?Discrete mathematics has the answer to these-and many other-questions of picking, choosing, and shuffling. T. S. Michael's gem of a book brings this vital but tough-to-teach subject to life using examples from real life and popular culture. Each chapter uses one problem-such as slicing a pizza-to detail key concepts about counting numbers and arranging finite sets. Michael takes a different perspective in tackling each of eight problems and explains them in differing degrees of generality, showing in the process how the same mathematical concepts appear in varied guises and contexts. In doing so, he imparts a broader understanding of the ideas underlying discrete mathematics and helps readers appreciate and understand mathematical thinking and discovery.This book explains the basic concepts of discrete mathematics and demonstrates how to apply them in largely nontechnical language. The explanations and formulas can be grasped with a basic understanding of linear equations.
Preface ix1 How to Count Pizza Pieces 11.1 The Pizza-Cutter's Problem 11.2 A Recurring Theme 41.3 Make a Difference 71.4 How Many Toppings? 91.5 Proof without Words 121.6 Count 'em and Sweep 141.7 Euler's Formula for Plane Graphs 161.8 You Can Look It Up 201.9 Pizza Envy 211.10 Notes and References 221.11 Problems 242 Count on Pick's Formula 332.1 The Orchard and the Dollar 332.2 The Area of the Orchard 342.3 Twenty-nine Ways to Change a Dollar 372.4 Lattice Polygons and Pick's Formula 422.5 Making Change 462.6 Pick's Formula: First Proof 482.7 Pick's Formula: Second Proof 532.8 Batting Averages and Lattice Points 562.9 Three Dimensions and N-largements 582.10 Notes and References 652.11 Problems 663 How to Guard an Art Gallery 733.1 The Sunflower Art Gallery 733.2 Art Gallery Problems 753.3 The Art Gallery Theorem 813.4 Colorful Consequences 833.5 Triangular and Chromatic Assumptions 863.6 Modern Art Galleries 883.7 Art Gallery Sketches 893.8 Right-Angled Art Galleries 933.9 Guarding the Guards 963.10 Three Dimensions and the Octoplex 1023.11 Notes and References 1063.12 Problems 1074 Pixels, Lines, and Leap Years 1134.1 Pixels and Lines 1134.2 Lines and Distances 1164.3 Arithmetic Arrays 1184.4 Bresenham's Algorithm 1234.5 A Touch of Gray: Antialiasing 1244.6 Leap Years and Line Drawing 1254.7 Diophantine Approximations 1284.8 Notes and References 1344.9 Problems 1355 Measure Water with a Vengeance 1395.1 Simon Says: Measure Water 1395.2 A Recipe for Bruce Willis 1425.3 Skew Billiard Tables 1445.4 Big Problems1475.5 How to Measure Water: An Algorithm 1485.6 Arithmetic Arrays: Climb the Staircase 1515.7 Other Problems to Pour Over 1555.8 Number Theory and Fermat's Congruence 1605.9 Notes and References 1645.10 Problems 1656 From Stamps to Sylver Coins 1696.1 Sylvester's Stamps 1696.2 Addition Tables and Symmetry 1736.3 Arithmetic Arrays and Sylvester's Formula 1766.4 Beyond Sylvester: The Stamp Theorem 1806.5 Chinese Remainders 1866.6 The Tabular Sieve 1886.7 McNuggets and Coin Exchanges 1906.8 Sylver Coinage 1946.9 Notes and References 1966.10 Problems 1987 Primes and Squares: Quadratic Residues 2077.1 Primes and Squares 2077.2 Quadratic Residues Are Squares 2087.3 Errors: Detection and Correction 2127.4 Multiplication Tables, Legendre, and Euler 2167.5 Some Square Roots 2217.6 Marcia and Greg Flip a Coin 2247.7 Round Up at the Gauss Corral 2267.8 It's the Law: Quadratic Reciprocity 2327.9 Notes and References 2397.10 Problems 240References 245Index 251
