How to Guard an Art Gallery and Other Discrete Mathematical Adventures

1. How to Count Pizza Pieces

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 Figure 1.1: Three cuts through a pizza 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? 1 2 D is c r e t e M a t he m a t ic a l A d v en t u r es 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 H o w t o C o u n t P i z z a P i e c e s 3 Table 1.1: The maximum number of pizza pieces with n cuts n 0 1 2 3 4 5 6 7 P(n) 1 2 4 7 11 16 22 29 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 con- figuration. 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 con- figuration of n cuts that intersect pairwise inside a circular 4 D is c r e t e M a t he m a t ic a l A d v en t u r es 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 Figure 1.3: Pizza-cutting and Steiner’s problem 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...