Answer to October 11, 2004 Problem

The Subway Advertisement Problem

An advertisement on TV last summer claims that you can dine five nights a week at Subway for the rest of your life and not have the same sandwich twice.
How many different sandwiches are possible?

The Subway website lists seventeen different subs, which can be ordered in one of three ways: (1) as a six-inch sub, (2) as a twelve-inch sub, or (3) as a wrap. There are three additional wraps listed which can only be ordered as wraps. We will consider each of these to be a different sandwich (a six-inch meatball sub is different from a twelve-inch meatball sub which is different from a meatball wrap).

For the subs, you have a choice of six different types of bread (wheat, white, etc.).

Once you have selected your basic sandwich, then there are thirteen different toppings from which you may choose (cheese, pickles, onions, etc.), but you may select any number of these (or none of them).

Finally, there are nine sauces from which to choose (mustard, mayonaise, vinegar, etc.). Most people probably just choose one of these items, so let's suppose that only one of these is chosen (or you may choose to have none of them).

Click here for the Subway menu

I saw a similar ad on a Metro Train in Washington, DC this past summer. It read, "To see everything the Smithsonian has to offer, you'd have to view 4,348 items every day until you were ninety. Luckily, we've extended our hours this summer."

While eating at Bintliff's American Cafe Restaurant in Portland, Maine, which is famous for its breakfasts, the menu stated that you can choose from over 25,600 different omelettes and fritatas. You are allowed to choose 4 items from the following: 10 different Meats, 19 different vegetables, and 10 different cheeses.

 


Solution to the Problem:

There are 18,350,080 different sandwiches. You could dine 5 nights a week for 70,577 years and not eat the same sandwich twice!

The total number of different sandwiches can be computed by multiplying the number of basic sandwiches times the number of toppings times the number of sauces.

To compute the number of basic sandwiches, compute the number of subs and the number of wraps separately and then add them together. The number of subs = 17 x 2 x 6 = 204 (17 is the number of subs listed in the menu, 2 is for six-inch or twelve-inch, 6 is the number of bread choices). The number of wraps is 17 + 3 = 20 (17 is the number of six-inch subs that can be ordered as wraps, 3 is for the three additional wraps listed). So, the total number of basic sandwiches is 204 + 20 = 224.

To figure the number of ways that the toppings can be selected, you must consider every possible combination of toppings and add them together. You must add together the following:
the number of ways in which 1 topping can be selected (13)
the number of ways in which 2 toppings can be selected (78)
the number of ways in which 3 toppings can be selected (286)
the number of ways in which 4 toppings can be selected (715)
the number of ways in which 5 toppings can be selected (1287)
the number of ways in which 6 toppings can be selected (1716)
the number of ways in which 7 toppings can be selected (1716)
the number of ways in which 8 toppings can be selected (1287)
the number of ways in which 9 toppings can be selected (715)
the number of ways in which 10 toppings can be selected (286)
the number of ways in which 11 toppings can be selected (78)
the number of ways in which 12 toppings can be selected (13)
the number of ways in which 13 toppings can be selected (1)
the number of ways in which no topping can be selected (1)
The sum is 8,192 different ways!

The number of choices for sauces is ten (any one of the nine sauces or none of them).

Therefore, the total number of different sandwiches is 224 x 8,192 x 10 = 18,350,080.
I don't believe this is what Subway meant. They probably calculated the number of different sandwiches by multiplying 224 x 13 x 9 = 26,208 different sandwiches. You could then dine five nights a week for 100 years before you would have the same sandwich again. But this calculation doesn't take into account having more than one topping and it doesn't allow for not selecting a topping or sauce.

I contacted Subway about their advertisement but they did not respond.

After re-reading the problem, I realized that it is not clear that wraps can only be ordered one way. You don't get a choice for the six breads, so I counted it correct for those who figured the answer to be 26,542,080.

Confession time: Actually, when I initially worked out the problem, I used only 11 toppings for some reason. It was only when I noticed three of you with the same answer that I decided to recheck my work!


Correctly solved by:

1. Larry Schwartz Trumbull, Connecticut
2. David & Judy Dixon Bennettsille, South Carolina
3. Jeffrey Gaither Winchester, Virginia
4. James Alarie University of Michigan -- Flint,
Flint, Michigan
5. Dave Smith Toledo, Ohio
6. Misty Carlisle Winchester, Virginia
7. Arin Smith Winchester, Virginia