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
1. How to Count Pizza Pieces
1.1. The Pizza-Cutter's Problem
1.2. A Recurring Theme
1.3. Make a Difference
1.4. How Many Toppings?
1.5. Proof without Words
1.6. Count 'em and Sweep
1.7. Euler's Formula for Plane Graphs
1.8. You Can Look It Up
1.9. Pizza Envy
1.10. Notes and References
1.11. Problems
2. Count on Pick's Formula
2.1. The Orchard and the Dollar
2.2. The Area of the Orchard
2.3. Twenty-nine Ways to Change a Dollar
2.4. Lattice Polygons and Pick's Formula
2.5. Making Change
2.6. Pick's Formula: First Proof
2.7. Pick's Formula: Second Proof
2.8. Batting Averages and Lattice Points
2.9. Three Dimensions and N-largements
2.10. Notes and References
2.11. Problems
3. How to Guard an Art Gallery
3. The Sunflower ArtGallery
3.1. The Sunflower Art Gallery
3.2. Art Gallery Problems
3.3. The Art Gallery Theorem
3.4. Colorful Consequences
3.5. Triangular and Chromatic Assumptions
3.6. Modern Art Galleries
3.7. Art Gallery Sketches
3.8. Right-Angled Art Galleries
3.9. Guarding the Guards
3.10. Three Dimensions and the Octoplex
3.11. Notes and References
3.12. Problems
4. Pixels, Lines, and Leap Years
4.1. Pixels and Lines
4.2. Lines and Distances
4.3. Arithmetic Arrays
4.4. Bresenham's Algorithm
4.5. A Touch of Gray: Antialiasing
4.6. Leap Years and Line Drawing
4.7. Diophantine Approximations
4.8. Notes and References
4.9. Problems
5. Measure Water with a Vengeance
5.1. Simon Says: Measure Water
5.2. A Recipe for Bruce Willis
5.3. Skew Billiard Tables
5.4. Big Problem
5.5. How to Measure Water: An Algorithm
5.6. Arithmetic Arrays: Climb the Staircase
5.7. Other Problems to Pour Over
5.8. Number Theory and Fermat's Congruence
5.9. Notes and References
5.10. Problems
6. From Stamps to Sylver Coins
6.1. Sylvester's Stamps
6.2. Addition Tables and Symmetry
6.3. Arithmetic Arrays and Sylvester's Formula
6.4. Beyond Sylvester: The Stamp Theorem
6.5. Chinese Remainders
6.6. The Tabular Sieve
6.7. McNuggets and Coin Exchanges
6.8. Sylver Coinage
6.9. Notes and References
6.10. References
7. Primes and Squares: Quadratic Residues
7.1. Primes and Squares
7.2. Quadratic Residues Are Squares
7.3. Errors: Detection amd Correction
7.4. Multiplication Tables, Legendre, and Euler
7.5. Some Square Roots
7.6. Marcia and Greg Flipa Coin
7.7. Round Up at the Gauss Corral
7.8. It's the Law: Quadratic Reciprocity
7.9. Notes and References
7.10. Problems
References
Index
