How Many Possible Pizza Topping Combinations?
Date: 12/21/2004 at 05:47:47 From: Ryan Subject: Dominos Pizza - How Many Topping Combinations? I work at Domino's Pizza and would like to tell customers how many topping combinations we have. It's tricky because you can get single-layers, double-layers, or triple-layers of ANY topping, and mix single, double, and triple-layered toppings on each pizza. There are 13 different toppings. You can get a pizza with 1 or up to 39 toppings (triple everything.) The fact that you can have a pizza with double pepperoni, triple sausage, and normal amount of green peppers makes it much harder. I took (39^13 + 26^13 + 13^13 and got 485,362,204,315,790,908,548)... that seems like a lot though, so I thought I had better ask an expert.
Date: 12/21/2004 at 08:57:11 From: Doctor Edwin Subject: Re: Dominos Pizza - How Many Topping Combinations? Hi, Ryan. I love this question. You're right, it's a lot more interesting because of the possibility of single, double, or triple doses of each topping. There are a couple of ways to think about the problem. I'll start with the one that I think is the simplest, and then we can talk about the one I think is the coolest. Suppose you had one topping, let's say mushrooms. How many different possible pizzas would there be? If I understand your setup right, there would be 4: no topping, single mushrooms, double mushrooms, or triple mushrooms. Now imagine that there are two toppings, mushrooms and sausage. How many possible combinations are there? Well, if a customer doesn't want mushrooms, there are 4, right? And if the customer wants 1x mushrooms, that's 4 more, and so on for 2x and 3x mushrooms. In other words, there are 4 x 4 = 16 different combinations with two items. We could continue this for a long time. If you have only sausage, mushroom, and onion, that's 16 combinations with no onion, 16 with 1x onion, and so on, for a total of 4 x 4 x 4 = 64 combinations. So it looks like the number of combinations is: (# of choices for item 1) X (# of choices for item 2) X ....etc. Now we have the same number of choices for each item, so that simplifies things a bit. Can you take it from there? Write back and tell me what you get. Now on to the cool part. Let's represent a pizza choice numerically. I can represent each topping with a number zero through three representing no topping through triple topping. If you're taking orders and calling them back to the cook, and there is only one topping (sausage) available and someone wants triple sausage, you could yell back, "Gimme a 3." Now suppose again that there are sausage and mushroom available, and someone wants double sausage and single mushrooms. You could work out a system with the cook where you always list the ingredients in the same order. So then you could yell, "Gimme a 21." So you could represent every possible pizza as a 13-digit number, where every digit was 0, 1, 2, or 3. I don't know how much you remember from math class (some, obviously, judging from your question), but you may have learned at some point to do math in different bases. Every pizza can be represented by a 13-digit number in base 4, and every possible number in base 4 represents a pizza. So the question then becomes, how high can you count in base 4 with only 13 digits? 0000000000000 0000000000001 0000000000002 0000000000003 0000000000010 0000000000011 0000000000012 0000000000013 0000000000020 0000000000021 ... and so on If that's unfamiliar or confusing, go back to thinking of them as toppings: 0x sausage, 0x mushrooms 0x sausage, 1x mushrooms 0x sausage, 2x mushrooms 0x sausage, 3x mushrooms 1x sausage, 0x mushrooms 1x sausage, 1x mushrooms 1x sausage, 2x mushrooms 1x sausage, 3x mushrooms 2x sausage, 0x mushrooms 2x sausage, 1x mushrooms So, how high can you count in base 4 with 13 digits? Let me know what you come up with. Thanks for writing. You owe me a 121 (1x sausage, 2x mushroom, 1x onion). - Doctor Edwin, The Math Forum http://mathforum.org/dr.math/
Date: 12/22/2004 at 05:56:19 From: Ryan Subject: Dominos Pizza - How Many Topping Combinations? Hey Doctor Edwin! Thanks for the help (and quick response!) I may have found the answer, but I'm not sure. I found the number of combinations for a 1-topping (39) and then the number of combinations for a 2-topping (741) and 3-topping (9139) and so on up to a 39-topping pizza (1 combination, [all the toppings]). I then added all the final numbers together and got "549,755,813,879". Is that correct? If so, I can happily tell people we have over half a trillion topping combinations, haha! Ryan
Date: 12/22/2004 at 09:00:22 From: Doctor Edwin Subject: Re: Dominos Pizza - How Many Topping Combinations? Hi, Ryan. I think it's going to be a lot less than half a trillion. I think you and I are using a couple of words differently. When I said imagine you could only have one topping, I meant, imagine there was only one topping to choose from. You meant that you could only pick one topping, but you could pick any of the ones that are available in real life. The problem with your approach (and it can be solved that way, it's just more complicated) is that for my first choice I've got 40 possibilities (including plain). For my second choice I can't choose from 40 possibilities, because I've already used one of them. That is, suppose I choose sausage for my first topping. I can't choose 1x sausage or 2x sausage or 3x sausage for my second choice, can I? So instead of thinking of it that way (how many could I get if I pick only one, how many if I pick only one or two, etc.), let's think of it the other way (how many could I get if there is only one topping to choose from, how many if there are only two toppings to choose from?). In that case, for each of my 13 toppings, I've got 4 possibilities: zero, 1x, 2x, or 3x. With only one topping to choose from, I've got 4 pizzas I could order. With two toppings to choose from, I've got 4 choices for my first topping. For each of those, I've got 4 choices for my second topping, for a total of 4 x 4 = 16 choices. Let's try that out and count them. We'll use M for mushrooms and S for sausage: 0M 0S 0M 1S 0M 2S 0M 3S 1M 0S 1M 1S 1M 2S 1M 3S 2M 0S 2M 1S 2M 2S 2M 3S 3M 0S 3M 1S 3M 2S 3M 3S That's every combination we can make if we only have two ingredients to play with. Let's say we add onions to the menu. If someone wants no onions, they've got 16 choices. If they want 1x onions, that's another 16 possible pizzas they could order. 16 more for 2x onions, and 16 more for 3x onions. In other words, with three toppings on the menu, there are 4 x 16 = 4 x 4 x 4 = 64 possible toppings to choose from. So a general formula would be (number of ways to use a single topping) ^ (number of toppings) where the number of ways to use a single topping includes not using any. So for your example, the total number of possible pizzas to choose from is 4 ^ 13 Not anywhere near a half-trillion, but it's a heck of a big number, isn't it? I'm surprised I ever manage to order a pizza at all. - Doctor Edwin, The Math Forum http://mathforum.org/dr.math/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.