Top This — And Prove It!
Dan King can’t help identifying math challenges everywhere. Once, he says, he walked into a pizzeria that advertised that with 10 toppings the patron could make over 1,000 different pizzas. Instantly up for the challenge, King summoned a branch of mathematics called combinatorics—the mathematical study of counting. Here’s his proof:
Question: How many different pizzas can be made with 10 available toppings-or, more generally, how many pizzas can be made with n available toppings? (Let’s say two pizzas are different if they have different toppings and let’s assume all pizzas have dough, sauce and cheese. Sorry, vegans!)
Answer: The key to answering this culinary question is in thinking about the construction of a pizza mathematically as a sequence of topping selections.
If there is only one topping available, say pepperoni, you have to ask yourself, “Do I want pepperoni added to a plain pizza?” If the answer is yes, you get a pepperoni pizza, and if no, a plain one. Two different pizzas are possible with exactly one topping available.
Now suppose there are exactly two toppings available, say pepperoni and peppers. Onto each of the two pizzas we’ve already imagined above, we ask, “Do I want to add peppers?” There are now four possible pizzas (as pictured). Four or 2x2 different pizzas are possible with exactly two toppings available-that’s double the number before.
Now suppose there are exactly three toppings available, say pepperoni, peppers and anchovies. Onto each of the four pizzas we’ve already made above, we can ask, “Do I want to add anchovies?” From the diagram, we see that for each of the four pizzas we created above, we get two new types of pizza. We have eight or 2x2x2 pizzas possibilities with three available topping.
Generalizing, we conclude that we can make 2n different pizzas with n available toppings. Finally, if n is 10, we see we can make 210 or exactly 1,024 pizzas...enough to feed every current, on-campus SLC undergraduate with a different type of pizza!
Postscript: Those readers familiar with binary representation of numbers might recognize the number of possible pizzas with n available toppings to be equal to the number of whole numbers representable in binary with exactly n digits (or bits).