The Perfect Combinatorics Problem

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?

5 Comments

  1. akismet-457375c2686d2ce6aa9740f00ee2f8f4
    Posted March 5, 2012 at 12:44 am | Permalink | Reply

    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.

  2. Posted March 5, 2012 at 1:45 am | Permalink | Reply

    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

  3. Posted March 5, 2012 at 1:46 am | Permalink | Reply

    59.049 combos instread of 1,024 combos.
    I won’t discuss the order that they are put on, but you could.

  4. Posted March 5, 2012 at 9:55 am | Permalink | Reply

    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. ;^)

  5. Mimi
    Posted March 5, 2012 at 6:35 pm | Permalink | Reply

    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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: