The Nonlinear Classroom

With 5 cuts there are 16 pieces of pizza.

If we generalize to n cuts, the number of pieces p is given by p(n) = \frac{1}{2}n^2 + \frac{1}{2}n + 1.

Below is a proof of this problem. If you are less interested in rigor, maybe you simply drew out the first few cases and produced the pattern, then great! Feel free to skim the proof and move on to the commentary or teacher resources sections.

Alright, let’s do this. To produce a solution we need to:

1. Identify the rules for making the maximum number of pieces on a given number of cuts
2. Figure out how to count the number of pieces

Maxing out on Pizza

Imagine that a pizza is already cut up into pieces and you need to make another cut to maximize the number of pieces. Where do you make the new cut?

Any cut through a piece of pizza creates a new piece. One piece becomes two pieces. Thus, the new cut needs to pass through as many pieces as possible.

The image below shows an optimal cut (dotted black line) for a pizza that has already been cut twice:

Notice that the third cut makes a separate intersection point with each of the existing cut lines. It turns out that this is the defining characteristic of optimal cuttings. Any configuration that produces fewer than 7 pieces (the max) on 3 cuts does not have this property, and falls into one of the two cases shown below.

The higher level math jargon for such a configuration of lines is general position^*

For God’s Sake, Justify Your Work

For 3 cuts it’s easy to draw out all possibilities and see that cut lines in general position achieve the maximum number of pieces. But suppose there are more than 3 cuts and we add a new cut in general position. Does this still achieve the maximum?

Since two lines either intersect in a point or they don’t, the new line either makes a unique intersection point with each existing line or it doesn’t.

If it doesn’t, then either it misses one or more lines entirely (so no intersection point), or it runs through an existing intersection point (so the intersection is not unique). But (locally) those two cases are the exact same sub-optimal cases that we produced for three cuts.

Provided that you accept^** that any two cuttings made by lines in general position yield the same number of pieces, then we are good to go.

---

*General position is the jargon used in higher level math to describe configurations of geometric objects that are… well as general as possible. For configurations of lines it means that every pair of lines intersect uniquely. That is, in exactly one point, with no more than two lines running through the same point.

**The number of pieces is a topological invariant, and any two cuttings made by lines in general position are isomorphic (say as planar graphs).

Awkward Plus Ones

Have you ever been the awkward plus one in a social situation? If so, you will sympathize with the math here.

We need to count how many pieces are made by n cuts in general position to finish off this problem. Let’s proceed inductively.

Suppose the pizza is cut by n – 1 lines in general position, and we are going to add an nth cut line also in general position.

The nth cut uniquely intersects each of the n – 1 cuts, which actually produces n new pieces of pizza.

The awkward plus one, that n – 1 intersections make n pieces, is because each intersection point marks the spot where the new cut crosses the boundary between pieces, and we need to count the extra piece on the other side of the boundary.

Yuck, enough awkwardness. Let’s finish this thing.

Square Pizza

We’ve established that cut lines in general position yield the maximum number of pieces, and that the n th cut produces n new pieces of pizza. That is, p(n) = p(n – 1) + n,\; \; p(0) = 1.

From the recurrence relation, we see that the max number of pieces sequence starts as 1, 2, 4, 7, 11, 16, \ldots,

Because the finite differences are growing linearly, that means that this sequence is modelled by a quadratic. This is the discrete version of the calculus fact that the integral of a linear function is quadratic.

You might find that quadratic by some brute force algebra. Start with p(n) = a n^2 + bn + c , and plug in values for n and p to back solve for the coefficients.

Or, you might notice that the sequence is a translated version of the triangular numbers, and go from there.

Whatever the case, you should end up with this pleasant looking quadratic: p(n) = \frac{1}{2}n^2 + \frac{1}{2}n + 1. 

Problem Extensions

The cutesy idea to make this a problem about pizza cutting was suggested to me by a professor friend of mine. At first I used a slightly different, but equivalent, problem formulation:

The only difference is that the circle (pizza) is replaced by the whole plane. This is equivalent because we only care about counting the regions formed by the lines. If your lines happen to intersect outside of the circle, just pick a bigger circle and the count is the same.

My friend also pointed out an extension question:

How many regions are formed by n planes in general position in 3 dimensional space? The answer should still be polynomial, a cubic I believe.

But why stop there? How many regions are formed in m dimensional space by n hyper-planes?

I’m told that there is a nice inductive way to go about this, but I haven’t had a chance to work it out yet. Let me know how it goes for you in the comments!

There are many more problems like this one but more general (how to count the ways to dissect a space by geometric objects like lines, planes, spheres, etc.)

The mathematician Thomas Zaslavsky seems to be responsible for much of this work in the 1970’s. But I’m not an expert here.

---

Students should come away from your class armed with a host of mental models for problem solving. Use this problem in class so your students see for themselves how to use math and logical thinking as problem solving tools.

Worksheets

Here are two worksheets demonstrating how you might vary this problem for different ability levels in class

• The first is formatted as a guided discovery learning activity
• The second is open-ended with less guidance.

Don’t Prove It

This may go without saying, but the amount of rigor provided in the solution above is unnecessary for a typical high school student. However you decide to implement this problem, the problem solving should be focused around drawing out lots of test cases, finding patterns, and/or matching the data to the algebra.

7 Reasons This Problem is Great for your Class

Let me count the ways I love this problem for class:

1. The solution for the max number of pieces in any number of cuts is given by a quadratic function. So this shows students an example of a polynomial that actually does something.
   
   
2. It’s a low floor high ceiling problem that can be adapted in a number of ways to meet the needs of your students.
   
   For some students, simply finding the pattern is a huge win. For others, being able to connect the pattern to the algebra is a huge win. Heck, even being able to get the answer right with 5 cuts is a huge win.

3. A crucial part of problem solving is drawing the right picture/model, and in this problem students develop and test hypotheses by drawing lots of pictures! I love when a math classroom is full of pictures.
   
   
4. Students work with numbers (it’s a counting problem) and the counting process naturally motivates the algebra.
   
   
5. Algebra, geometry, and combinatorics all in one problem
   
   
6. There is a recursive solution. Read more about why I think recursion is one of the most criminally underutilized ideas in math education. 
   
   
7. If you already use the handshake problem or triangular numbers in class, the solution of this problem is closely related which makes for some great discussions. The more connections students make/ the more mental models they form for how algebra can be used to solve real problems model, the better.

This is a well known combinatorial problem. Here it is on Wolfram’s Mathworld.