OR

# How to Guard an Art Gallery and Other Discrete Mathematical Adventures

Publication Year: 2009

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.

pp. v-vii

#### Preface

pp. ix-xi

The adventures in this book are launched by easily understood questions from the realm of discrete mathematics, a wide-ranging subject that studies fundamental properties of the counting numbers 1, 2, 3, . . . and arrangements of finite sets The book grew from talks for mathematically inclined ...

#### 1. How to Count Pizza Pieces

pp. 1-32

little experimentation should convince you that seven pieces is the most you can make with three cuts. But how many pizza pieces can you make with more cuts? The pizza-cutter’s problem. What is the largest number of pieces of pizza we can make with n straight cuts through a circular pizza? ...

#### 2. Count on Pick’s Formula

pp. 33-72

Counting questions. How many ways are there to make change for a dollar from a supply of quarters, dimes, and nickels? What about change for D dollars? Although the questions we have posed appear entirely unrelated, a remarkable formula discovered by the Austrian ...

#### 3. How to Guard an Art Gallery

pp. 73-112

Figure 3.1 shows the unusual floor plan of the Sunflower Art Gallery and the locations of four guards. Each guard is stationary but can rotate in place to scan the surroundings in all directions. Guards cannot see through walls or around corners. Every point in the gallery is visible to at least one ...

#### 4. Pixels, Lines, and Leap Years

pp. 113-138

A computer monitor has a rectangular array of thousands of tiny square cells called , each of which is light or dark at any time. In the field of computer graphics, we confront the problem of rendering continuous geometric shapes on the array of discrete pixels in an accurate and pleasing manner ...

#### 5. Measure Water with a Vengeance

pp. 139-168

In the 1995 action movie Die Hard: With a Vengeance, Bruce Willis plays a maverick law enforcement officer who must solve a series of fiendish puzzles posed by Simon Gruber, the mastermind of a diabolical bank heist. In one memorable scene, Simon directs Willis and his reluctant sidekick to a fountain in a public park, where they find two empty, ...

#### 6. From Stamps to Sylver Coins

pp. 169-206

Question. We have a large supply of 5- and 8-cent stamps. Can we make exact postage for a 27-cent postcard? A bit of trial and error should convince you the answer is no. A methodical approach involves some algebra. The question asks whether there is a solution (x, y) to the equation ...

#### 7. Primes and Squares:Quadratic Residues

pp. 207-244

The blocks of eleven repeat, and the only nonzero remainders are 1, 3, 4, 5, and 9. These five numbers are the quadratic residues modulo 11. Our goal in this chapter is to discover and explain properties of quadratic residues. Our discussion culminates in the beautiful Law of Quadratic Reciprocity. We will also find ...

pp. 245-250

#### Index

pp. 251-257

E-ISBN-13: 9780801897047
E-ISBN-10: 0801897041
Print-ISBN-13: 9780801892998
Print-ISBN-10: 0801892996

Page Count: 272
Illustrations: 103 line drawings
Publication Year: 2009