How to Guard an Art Gallery: And Other Discrete Mathematical Adventures

Preface

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 secondary school students and college students interested in problem solving. The aim is high, but the prerequisites are modest—mostly elementary algebra and geometry. Occasionally, a perspective gained from more advanced subjects is mentioned. A sampling of questions conveys the spirit and scope of the topics.

The art gallery problem. What is the minimum number of stationary guards (or security cameras) needed to protect a given art gallery?

The pizza-cutter’s problem. What is the maximum number of pizza pieces we can make with four straight cuts through a circular pizza? What about n cuts?

The computer line drawing problem. Which pixels should a computer select to represent a given straight line on a monitor?

A quadratic residue question. Is there an integer whose square is 257 more than a multiple of 641? In the jargon of number theory, is 257 a quadratic residue modulo 641?

Our interest extends beyond answers to individual questions, no matter how accessible and enticing. The questions are gateways to deeper mathematical material that can be discussed without a lot of background. For instance, the following puzzle (taken from a memorable scene in the movie Die Hard: With a Vengeance) leads to a discussion of a famous result of Fermat in number theory.

The Bruce Willis problem. We are at a fountain with two unmarked jugs with capacities 3 and 5 gallons. How can we measure exactly 4 gallons of water?

Our goal is to impart a genuine feel for discovery and mature mathematical thinking by attacking problems from several points of view and in various degrees of generality. We also reveal hidden connections between seemingly unrelated topics. For instance, we will discover a relationship between computer line drawing and quadratic residues. You will also likely be surprised to learn that the following two questions are related.

An area question. What is the area of the oddly shaped orchard shown in the figure if the rows and columns of trees are 1 unit apart?

A dollar-changing question. How many ways are there to make change for a dollar with quarters, dimes, and nickels?

Readers inspired to chart their own mathematical adventures can explore the problems at the end of each chapter. The more challenging problems include hints or are broken into smaller steps. The lightly annotated references are a starting point for further reading.

Among the many people who helped and encouraged me as I wrote this book, several deserve special thanks. Amy Myers, Courtney Moen, and Sommer Gentry gave me valuable feedback on all aspects of early drafts and pointed out ways to improve each chapter. I also greatly appreciate the patience and guidance of my editor, Trevor Lipscombe.

Finally, I dedicate this book to Tom Apostol, who set me on the path to mathematical maturity 30 years ago.

How to Guard an Art Gallery

1

How to Count Pizza Pieces

You better cut the pizza in four pieces because I’m not hungry enough to eat six.

YOGI BERRA

1.1 The Pizza-Cutter’s Problem

Three cuts through the center of a circular pizza make six identical pieces of pizza. Displacing one cut slightly gives seven pieces of various sizes and shapes, as in Figure 1.1. A 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?

Figure 1.1: Three cuts through a pizza

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?

The goal is to maximize the number of pieces regardless of size and shape. In this chapter, we serve up several solutions to the pizza-cutter’s problem. Our solutions introduce a host of ideas from discrete mathematics. The first solution is based on a recurrence, which gives the number of pizza pieces with n cuts in terms of the number with n − 1 cuts. The second solution uses a table of differences to guide us to the general form of the answer. Later approaches relate the number of pizza pieces to the number of points where two cuts cross. One solution consists of a single diagram!

Setting the Table: Small Values

Let P(n) denote the maximum number of pieces formed by n straight cuts through a circular pizza. We want to find a formula for P(n). The first order of business is to gather some data by cutting pizzas or drawing lines through circles. It is easy to see that

P(0) = 1, P(1) = 2, and P(2) = 4.

Figures 1.1 and 1.2 help us see that

P(3) = 7, P(4) = 11, and P(5) = 16.

Figure 1.2: Four and five cuts through a pizza

Table 1.1: The maximum number of pizza pieces with n cuts

Optimal configurations become more difficult to draw as the number of cuts increases. It might take you several attempts to make 29 pieces with seven cuts. Table 1.1 lists the values of P(n) for n = 0, 1, …, 7. As you construct the optimal configurations, the following principle becomes clear.

Maximizing principle. The number of pizza pieces is maximized when every cut crosses every other cut, but no three cuts cross at the same point.

Jakob Steiner’s Plane Pizza

The pizza-cutter’s problem was first studied and solved in an equivalent form by the prominent Swiss geometer Jakob Steiner (1796–1863). Steiner’s pizza was infinitely large—occupying the whole plane—and his cuts were infinitely long straight lines.

Steiner’s plane-cutting problem. What is the maximum number of regions formed by n lines in the plane?

Every line intersects every other line in an optimal configuration. Note that some of the regions will be infinitely large.

Figure 1.3 shows why Steiner’s plane-cutting problem is equivalent to the pizza-cutter’s problem. Start with a configuration of n cuts that intersect pairwise inside a circular pizza to form P(n) pieces. Then extend the cuts indefinitely in both directions and delete the circular boundary of the pizza. The resulting configuration of n straight lines partitions the entire plane into P(n) regions, as shown in the figure. The crusty pizza pieces (those touching the circular boundary) become regions that extend infinitely far, but no regions are created or destroyed. The process works in reverse, too. If n lines form a certain number of regions in the plane, then adding a suitably large boundary circle gives the same number of finite pizza pieces.

Figure 1.3: Pizza-cutting and Steiner’s problem

We find it more convenient to work in the pizza-cutting scenario than in Steiner’s purely geometric setting.

1.2 A Recurring Theme

Perhaps you noticed a pattern among the numbers

1, 2, 4, 7, 11, 16, 22, 29, …

in Table 1.1. The differences between successive values are

1, 2, 3, 4, 5, 6, 7, ….

This pattern can be expressed as an equation giving P(n) in terms of P(n − 1), that is, as a recurrence.

Pizza-cutter’s recurrence. The maximum number of pizza pieces formed by n cuts satisfies

P(n) = P(n − 1) + n    for n = 1, 2, 3, ….

The recurrence lets us extend our table of values for P(n) without actually cutting pizzas or drawing pictures. For instance, with eight cuts the maximum number of pizza pieces is

P(8) =P(7) + 8 = 29 + 8 = 37.

Such computations assume our recurrence is valid in general. Even though it holds for the first few values of n, it could fail for larger n. Discrete mathematics is rife with patterns that fall apart after several terms. For instance, Problem 7 at the end of this chapter deals with a geometric problem giving rise to a sequence that starts 1, 2, 4, 8, 16. But the next term is 31, not 32.

New Pizza Pieces from Old

Here is why the pizza-cutter’s recurrence is true. Start with n−1 cuts that form P(n−1) pieces of pizza. Slowly make the n-th cut (the dotted line in Figure 1.4) to form P(n) pieces. When the new cut meets one of the n − 1 previous ones, a pizza piece is cut in two. Also, a piece is cut in two when the new cut finishes on the opposite side of the pizza. So the total number of pieces of pizza increases by n when we pass from n − 1 cuts to n cuts, which is exactly what the recurrence says.

Figure 1.4: The n-th cut produces n more pieces of pizza

The Pizza-Cutter’s Formula

We can replace n by n − 1 in our recurrence to write P(n−1) in terms of P(n − 2):

P(n− 1) = P(n −2) + (n− 1).

In general, we can write P(k) in terms of P(k − 1) for k = n all the way down to k = 1:

P(n) = P(n − 1) + n

P(n − 1) = P(n − 2) + (n − 1)

P(n − 2) = P(n −3) + (n − 2)

⋮

P(3) = P(2) + 3

P(2) = P(1) + 2

P(1) = P(0) + 1.

Add all n equations and cancel the common terms from both sides to obtain

P(n) = P(0) + 1 + 2 + … + (n − 2) + (n − 1) + n.

Now we recall a well-known formula for the sum of the first n positive integers:

Therefore,

We have solved the pizza-cutter’s problem by essentially the same method Steiner used.

Pizza-cutter’s formula. The maximum number of pieces we can make with n straight cuts through a circular pizza is

If you dislike recurrences, or if formula (1.1) is not familiar to you, then our first solution to the pizza-cutter’s problem might be unsatisfying. Perhaps one of the other solutions in this chapter is more to your taste. In any case, the alternative solutions provide more insight and suggest different generalizations.

1.3 Make a Difference

The calculus of finite differences is a powerful tool that uses tables of numbers to explore patterns in sequences of numbers. Table 1.2 is the difference table for the pizza-cutting sequence P(0), P(1), P(2), …. The top row is the sequence itself, and each successive row is obtained by subtracting consecutive terms from the row above. The pizza-cutter’s recurrence guarantees that the row of first differences is correct, and it follows that all rows in the table are correct.

Table 1.2: The difference table for P(n)

The row of third differences in Table 1.2 consists of 0’s, and the theory tells us that P(n) must be a quadratic function¹ of n, say,

P(n) = An² + Bn + C,                (1.2)

for some constants A, B, and C. Our known values of P(0), P(1), and P(2) lead to the system

which we solve to find

A = 1/2, B = 1/2, and C = 1.

Now our quadratic function in (1.2) becomes our pizza-cutter’s formula

If you want to try your hand with difference tables, use Table 1.3 to confirm formula (1.1) for the sum S(n) = 0 + 1 + 2 + … + n.

Table 1.3: The difference table for S(n) = 0 + 1 + 2 + … + n

1.4 How Many Toppings?

The argument that produced our basic recurrence (see Figure 1.4) hints at a relationship between the number of pizza pieces and the number of intersection points formed by the cuts. This relationship is the key to another solution to the pizza-cutter’s problem.

Figure 1.5: The top vertex of each pizza piece is either an interior vertex or an upper boundary vertex (u)

Figure 1.5 illustrates the main idea. We have temporarily dropped the requirement that every pair of cuts intersect. But we continue to assume that no three cuts intersect at the same point and that no two cuts intersect at a boundary point. An interior vertex occurs where two cuts intersect. Also, each of the n cuts determines an upper boundary vertex, as labeled in the figure. We rotate the pizza if necessary so that no cut is horizontal, guaranteeing that each pizza piece has a unique top vertex.

The tails suspended from some vertices in the figure match each piece of pizza to its top vertex. Every upper boundary vertex is matched with one pizza piece, except for the highest boundary vertex, which is matched with two pieces. Also, every interior vertex is matched with one piece. Our matches give a formula to count pizza pieces:

number of pizza pieces = 1 + number of cuts + number of interior vertices.

There are five cuts and six interior vertices in Figure 1.5, and so the formula tells us that the number of pizza pieces is 1 + 5 + 6 = 12, which is easy to verify.

To maximize the number of pizza pieces, each pair of cuts must cross at a unique interior vertex. In this case, we have

maximum number of pizza pieces = 1 + number of cuts + number of pairs of cuts.

This brings us to a new way to write the pizza-cutting formula using the choose function ("n choose k"), defined by

= the number of ways to choose a subset of k elements from a set of n elements.

Pizza-cutter’s formula (new version). The maximum number of pieces we can make with n straight cuts through a circular pizza is

Let us see why the new version is equivalent to the original pizza-cutter’s formula. From a set of n cuts, there is 1 way to choose 0 cuts (namely, do nothing) and n ways to choose 1 cut. Also, in choosing a pair of cuts, there are n choices for the first cut and n − 1 choices for the second cut, giving n(n − 1)/2 pairs of cuts altogether. We divide by 2 because the two cuts can be chosen in either order. Therefore,

which is our original pizza-cutter’s expression.

From Pizza to Grapefruit and Beyond

The new version of the pizza-cutter’s formula reveals its place within a hierarchy of similar formulas in other dimensions. Here is the three-dimensional case, which was also discovered by Steiner.

Grapefruit cutter’s formula. The maximum number of pieces of fruit we can make with n straight cuts through a spherical grapefruit is

Each cut is a plane that passes completely through the grapefruit. One way to establish the formula relies on a difference table. See Problem 17.

Even if you are unable to visualize a solid d-dimensional sphere being sliced by (d − 1)-dimensional cuts, you will not be surprised to learn that the number of pieces formed by n cuts is

Challenge 1. Explain why the formula makes sense when d = 1. A one-dimensional sphere is just a line segment, and each cut is a point on the segment.

We remark that the choose function can be computed with the formula

where m! (m factorial) is defined by

m! = 1 × 2 × 3 × … × (m − 1) × m for m = 1, 2, 3, …

and 0! = 1.

1.5 Proof without Words

We now return to our two-dimensional pizza. Figure 1.6 encapsulates in a single picture our earlier vertex-counting argument. The figure by itself constitutes a visual proof—a proof without words—of the pizza-cutter’s formula. In case this type of demonstration is unfamiliar to you, we include some words of explanation.

The figure illustrates the case n = 6, but it will be apparent that the idea works generally.