How to Guard an Art Gallery and Other Discrete Mathematical Adventures

Cover

Download PDF (191.0 KB)
 

Title Page, Copyright

Download PDF (24.1 KB)
 

Contents

Download PDF (91.1 KB)
pp. v-vii

Preface

Download PDF (103.0 KB)
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

Download PDF (257.0 KB)
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

Download PDF (305.7 KB)
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

Download PDF (316.7 KB)
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

Download PDF (243.0 KB)
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

Download PDF (271.9 KB)
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

Download PDF (300.5 KB)
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

Download PDF (279.4 KB)
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 ...

References

Download PDF (88.9 KB)
pp. 245-250

Index

Download PDF (345.4 KB)
pp. 251-257