## Two Problems in Elementary Cheeseburger Theory

A favorite hamburger joint of mine has the following 15 choices for toppings:

Mayo
Relish
Onions
Lettuce
Pickles
Tomatoes
Grilled Onions
Grilled Mushrooms
Ketchup
Mustard
Jalapeno Peppers
Green Peppers
A-1 Sauce
Bar-B-Q Sauce
Hot Sauce

After much experimentation, I’ve decided that three toppings is about the right number to have on any one burger (too many toppings masks the flavor of the burger itself). So, being a mathematician, I’ve decided that I should try all possible combinations of 3 toppings. Here are the problems then:

1) If I visit the burger joint once a week (ordering one burger per visit), how long will it take me to reach my goal?

2) Can you devise an algorithm for working through all combinations that is not too complicated and provides a reasonable amount of variation (for instance, I don’t want to have 13 visits in a row where I have mayo and relish and one other topping. I probably don’t even want that for two or three visits in a row).

This entry was posted in math. Bookmark the permalink.

### 6 Responses to Two Problems in Elementary Cheeseburger Theory

1. Arlynda says:

You are probably going to make fun of me for my attempt at this, but spending the summer doing math with my kids, is reawakening my math brain, and I’m willing to give it a try.
I took statistics, but not probability so, I may be way off base, but here we go:
1) The solution to how long it is going to take you is this
You have 15 possibilities, of which you can only pick three of them. So, you have 15 x 14 x 13 / 3 x 2 x 1 = 455 combinations, which at one per week will take you 8 years and 39 weeks to try all of the combinations.
2) An algorithm, I would assign each topping a number start at the top of your list. Then I would write a computer program to spit out my 455 combinations, print them out and keep it in my wallet, marking off combinations as I went. I would also keep a master copy somewhere so that if I lost my wallet, I wouldn’t have to start over again.

2. toomai says:

Good job. Still I have one question: How do I make my list of burgers?

3. Arlynda says:

My first answer was to answer the randomization concern, not the “how do I make a list of the toppings?” concern. I just thought it was pretty obvious how to make a list, sorry.
I walked my nephew through to the answer and this is how I did it. (Hang on the real answer is coming).
Let’s start with the case of two toppings on each burger. How many burgers do you get with mayo and one other topping? The answer is 14. You might be tempted to say then that the answer if 14 times 15 because there are 15 items and 14 possibilities for each, but there is overlap, take the onions, there are 14 sandwiches with onions, but you have already counted one of those with the mayonaise, so the original burgers you can make with onions is only 13, so you would add 14 + 13 + 12 + ….+ 1 = 105 burgers. So if we take these 105 burgers and add one more topping to them, how many hamburgers will you end up with?
In the case of Mayo and onion, you will end up with 13 burgers. In the case of mayo and relish, you will end up with 12 burgers. Mayo and Lettuce? 11, and so on, so all of the sandwiches with Mayo and two other toppings totals, 13 + 12 + 11 + …. + 1 = 91 burgers.
So what about original burgers with onions? Onions and mayo we have all of, so what about onions with relish? We have onions, relish and mayo already, right, so we are left with 12 burgers original to onions and relish. Then we have 11 burgers original to onions and lettuce, etc. So we end up with 12 + 11 + 10 + …+ 1 = 78
original with relish? 66 burgers
original with lettuce? 55 burgers
with pickles? 45 burgers
with tomatoes? 36
Grilled onions? 28
Grilled mushrooms? 21
Ketchup? 15
Mustard? 10
Jalapeno? 6
Bell peppers? 3
Green peppers? 1
We end up all of the burgers for A-1 sauce, BBQ Sauce and Hot Sauce so we don’t have to consider them separately.

For a total of: 91 + 78 + 66 + 55 + 45 + 36 + 28 + 21 + 15 + 10 + 6 + 3 + 1 = 455 burgers

My guess is that you could tell the computer to do the same thing, assign some variable to each topping, have it find all of the toppings for a two topping burger, skipping all the previous variables as you move along, and then have add the third ingredient systematically in the same way. I’m sure there are little details that I missed.
Randomizing is something that I know nothing about when it comes to computers. But, who needs a computer to randomize things? Nature is better at it anyway, right? The other idea I had was to cut the paper up into slips and pull one out of a bag every time I went and just ordered that. Of course, keeping a master list somewhere is probably a good idea.

(I made some short lists, if you want to see them, didn’t take very long, probably could have had the entire list written by the time I finished writing this post, but I guess it would be useful if you were looking at changing the number of toppings per time and/or the number of available toppings, then you could just tell the computer what you have and it could spit out a list for you.)

• toomai says:

OK, I like you’re solution (but not quite as much as Sean’s. Sean’s I can essentially do in my head). I just have one more question. If I am picking cheeseburgers at random (or I have the computer randomize them) then how likely is it that I will get two cheeseburgers in a row with at least one topping in common? How about with two toppings in common? You may say that in that case I should re-choose at random. But then how likely will it be that at the end I am forced to have two in a row that share a topping?

4. Sean says:

I figured out a method, but it’s not pretty. I’m sure it could be written more eloquently…

Define some bijective map from the set of cheeseburger toppings into Z/15Z.

Let T be the set of three dimensional vectors over Z/15Z where that no two dimensions are equal.

We wish to find an ordering of T, preferably where at most one value in any element is found as a value in the succeeding element.

For two elements x, y in Z/15Z, define d(x,y) to be the minimum of |x – y| or |x – y – 15|. Intuitively, I’m thinking of the 15 elements as a necklace and I want the distance between two beads to be the fewest number of beads between them plus one. For instance d(0, 1) = 1, d(0, 14) = 1, d(1,8) = 7, d(1, 9) = 7.

Let x, y, and z be distinct elements of Z/15Z such that
(*)d(x,y) <= d(y,z) <= d(x,z).
(**) d(x,y) < d(x,z) unless d(x,y) = d(y,z) = d(x,z) = 5.

Claim: The elements (x,y,z) are exactly the elements of T.
There is probably some justification needed for this statement, but I'll produce the ordering and that should be enough to show this is true.

Let A be the set of three dimensional vectors over Z/15Z satisfying (*) and (**) such that x = 0.

Note that |A| = 31. For fun I'll enumerate the elements of A.
(0,1,2) ,(0,1,3), (0,1,4), …, (0,1,13),
(0,2,4), (0,2,5), …,(0,2,12),
(0,3,6), (0,3,7), …,(0,3,11),
(0,4,8), (0,4,9), (0,4,10)
(0,5,10)

Let A* = A – (0,5,10)

(***) Note that for an element (x,y,z) in A that the set of distances {d(x,y), d(y,z), d(x,z)} is a unique set among the elements of A.

Now for each element of (x,y,z) of A*, there are exactly 15 elements (x+d,y+d,z+d) (mod 15) of T (for 0 <= d <= 14).
Moreover (x1+d1 ,y1+d1,z1+d1) is never equal (x2+d2,y2+d2,z2+d2) over all values of d1, d2 when the two elements of A* are distinct by (***).

Silmilarly there are five such elements of T for the (0,5,10) element of A.
That is 15*30 + 5 =455 elements of T, which is exactly the number that Arlynda said there would be.

For a1 = (x,y,z) in A, let a1 + d = (x+d, y+d, z+d)
So enumerate T by
a1, a1 + d, a1 + 2d, …, a1 + 14d,

a2, a2 + d', a2 + 2d', …, a2 + 14d',

a30, a30 + d'', …., a30 + 14d'',

a31, a31 + d''', …, a31 + 4d'''

The d's need to remain constant across the row but could vary from one row to the next. Also gcd(15, d) = 1.

A suitable d for each ai should exist so that no element is repeated more than once from ai + kd to ai + (k+1)d and so that moving from one row to the next doesn't have repeated elements.

Here is an example

(0,1,2)
(2,3,4)
(4,5,6)
(6,7,8)
(8,9,10)
(10,11,12)
(12,13,14)
(14,0,1)
(1,2,3)

(13,14,0)

(1,2,4)
(2,3,5)
(3,4,6)

(14,0,2)

(0,1,4)
and so on