In this post, I’m going to extol the virtues of my favorite combinatorics problem. You’ve probably heard it, or some version of it, before:
A pizza parlor offers ten different toppings on their pizza. How many different types of pizza are possible to make, given that a pizza can have any number of toppings, or no toppings at all?
Just in case you aren’t familiar with this problem and want to work it out for yourself first, I’m putting most of this post after the jump. First, a shout out: I remember doing this problem with Michigan State Professor Bruce Mitchell, who used to teach Saturday-morning math enrichment classes at my middle school, and whose enthusiasm and humor kept me coming back. Second, some pizza:
You may prefer to pretend you never saw that.
This problem is a great way to move kids from basic-level combinatorics problems to more complicated ones. Here’s why:
It motivates “choose” notation. When students first solve problems like “how many committees of four can you choose from among ten people”, it doesn’t particularly add anything to name your answer “ten choose four.” It’s better to have students focus on using the formula, and concentrate on understanding the role that each factorial plays. Now, however, it adds clarity to write “ten choose zero” plus “ten choose one”, etc, without muddling up the board with formulas. From now on, students can think through harder combinatorics problems without slowing themselves down by having to work out each formula along the way.
Students are rewarded for making up a simpler example. As with all combinatorics problems with any degree of complexity, it’s very easy to blithely use the wrong method. With a problem this big, students have no way of knowing whether their methods are correct or not. But if they think about a pizza parlor that offers just two or three toppings, they can actually count the pizzas. In this combinatorics problem, making up a simpler example has the added bonus that students are more likely to discover the really elegant way to solve this problem: noticing that each topping can be present or absent, and that the number of pizzas must therefore be a power of two.
It’s a convenient way to have students notice patterns in Pascal’s Triangle. The last time I did this problem with a class, I deliberately neglected to erase the computations we’d done. When I later started writing Pascal’s Triangle on an adjacent board, they slowly recognized the tenth row as the very numbers we’d added together in order to solve the pizza problem. One student’s reaction: “that’s not okay.” Once students accept this fact, they have a quick way to solve the pizza problem for any number of pizzas. They are also in a good position to understand why the numbers in each of the rows of Pascal’s Triangle must add up to a power of two.
The richness of this problem qualifies it as a “Hall-of-Famer” for me. Which other problems deserve this honor?
acohen77
acohenher
Anand
Angela
btabrisky
Mimi
Tony
Park School Math 
5 Comments
Smells like power sets to me, assuming that we’re not allowing for repetition of ingredients on a single pizza, in which case there’d be no end of possibilities.
Very nice problem indeed. Hadn’t thought about it from the binary perspective, though that does make sense, too.
Yeah, once you notice that the “ten choose n” possibilities are just the entries on the 10th row of Pasca’s trianlge, you realize that it’s a waste of time to calculate all of the “choose” entries.
Plus, there is a simpler way:
for each topping, it can either exist, or not. Two cases.
Two the tenth power.
Now the previous commentor said that you could allow repetition of ingredients.OK, but let us say that you can only have mango slices (say) doubled, or singled, or not at all. But not three or four or five layers of mango slices on your pizza.
In that case, it’s three to the tenth power, not two to the tenth power.
Guy
59.049 combos instread of 1,024 combos.
I won’t discuss the order that they are put on, but you could.
Guy, that’s a very, um, disturbing avatar.
As for my layers/repetition comment above (should have logged in with Facebook), just trying to avoid opening the limit of n^n as n -> infinity issue.I had enough trouble eating a slice of the La Orchidia special pie, back in the ’70s, which probably had about a dozen toppings. Took a fork-lift to get a large pie to the car. ;^)
Yes, you can vary the problem so that the order of the toppings matters, or where toppings can be repeated, but I’d prefer to save those conditions for other, simpler problems. The beauty of this problem is, as both commenters have pointed out, that it it admits of two different, simple solutions. For many students, this is the first time they have ever seen a combinatorial identity.