My friend Sean worked out an elegant and practical solution to the Cheeseburger problem of my previous post. I will try to summarize it here.

There are fifteen toppings. To make things simpler we’ll represent them with the numbers one through fifteen.

1 = Mayo

2 = Relish

3 = Onions

4 = Lettuce

5 = Pickles

6 =Tomatoes

7 = Grilled Onions

8 = Grilled Mushrooms

9 = Ketchup

10 = Mustard

11 = Jalapeno Peppers

12 = Green Peppers

13 = A-1 Sauce

14 = Bar-B-Q Sauce

15 = Hot Sauce

Arrange these numbers around a circle at equal intervals, like the hours of a clock with fifteen rather than twelve hours. Each cheeseburger can be represented on this circle as three points. Think of these three points as the vertices (corners) of a triangle. As has been shown in the comments of the previous post, there are 455 cheeseburgers total. So the totality of cheeseburgers are represented by 455 triangles inscribed in the circle, which is a tangled, nasty mess (but not as big a mess as all 455 cheeseburgers sitting on your kitchen table).

Let’s get a handle on the mess. We need some notation to make it easier to talk about these triangles. If a triangle has vertices at points marked x, y and z, we’ll denote it by (x,y,z). Some of the triangles will have the same shape as each other. Others will be differently shaped. For instance, (1,2,3) has the same shape as (2,3,4), but (1,2,4) has a different shape than (1,2,3).

In fact there are fifteen triangles with the same shape as (1,2,3) (including (1,2,3) itself). They are: (1,2,3), (2,3,4), (3,4,5), (4,5,6), (5,6,7), (6,7,8), (7,8,9), (8,9,10), (9,10,11), (10,11,12), (11,12,13), (12,13,14), (13,14,15), (1,14,15) and (1,2,15). Each of these triangles can be obtained from (1,2,3) by rotating it around the circle. These fifteen triangles together form an *equivalence class*.

Likewise there are fifteen triangles with the same shape as (1,2,4). Said another way (1,2,4) has fifteen triangles in its equivalence class (but we need to be careful here to emphasize that we are considering (1,2,4) and say (1,3,4) to have different shapes: they are *mirror images* of each other, but not *rotations* of each other).

In all, the 455 triangles fall into 31 equivalence classes. 30 of these classes have fifteen triangles. The final equivalence class consists of five triangles. More on that in a moment.

The strategy is this: Pick an equivalence class. Rotate through all of the cheeseburgers in that class. Next move on to another equivalence class.

Let’s list the equivalence classes by writing down a single triangle in each class. OK, I’m not actually going to write all of them out, but I will do the next best thing. You’ll see.

First we have twelve equivalence classes with triangles of the form (1,2,n), where n=3,4,5,…,14. We don’t allow n=15 (i.e. (1,2,15) because that is the same class as (1,2,3). That gives us 180 cheeseburgers.

Then there are nine classes of the form (1,3,n), where n=5,6,7,…,13. (n=15 would give the same class as (1,2,4) and n=14 the same class as (1,3,5)). That’s another 135 cheeseburgers.

Next we get six classes of the form (1,4,n), with n=7,8,9,…,12. Another 90 cheeseburgers.

Similarly there are three classes of the form (1,5,n), with n=9,10,11. 45 more cheeseburgers.

Finally, we have our one strange class with only five cheeseburgers in it. This class is represented by (1,6,11). Let’s list all of the triangles in this class: (1,6,11), (2,7,12), (3,8,13), (4,9,14), (5,10,15). These are the five equilateral triangles in the set. Just for fun let’s list the five cheeseburgers that these triangles represent.

The equilateral cheeseburgers are:

Mayo, Tomatoes, Jalapeno Peppers

Relish, Grilled Onions, Green Peppers

Onions, Grilled Mushrooms, A-1 Sauce

Lettuce, Ketchup, Bar-B-Q Sauce

Pickles, Mustard, Hot Sauce

So go into a burger joint. Ask for an equilateral cheeseburger. See what kind of look you get. Then just tell them you want mayo, tomatoes and jalapeno peppers on it.

OK, seriously, back to the math for a minute. Sean also realised that you can rotate through the classes such that no two burgers in a row have any of the same toppings. Great! That’s what I was asking for in the first place. Let’s use our first equivalence class as an example. We start with the triangle (1,2,3). Now we can rotate one slot by adding one to each number in this triple to get (2,3,4). But that’s not what we want: we would have two burgers in a row where only one topping changed. So instead let’s rotate three slots so that none of the toppings are the same twice in a row. We get (1,2,3) then (4,5,6). Keep going to get: (7,8,9), (10,11,12), (13,14,15). Now when we do the next addition: (13+3,14+3,15+3) we have to be careful to do *clock arithmetic* on a 15-hour clock. That is, counting up one from 15 gives one, rather than 16 (we mathematicians call this modular arithmetic). So (13+3,14+3,15+3)=(1,2,3). That’s a problem because we’ve already visited the triangle (1,2,3), but there are still ten triangles that we haven’t visited in this class. Our problem was moving three slots at a time. 15 is divisible by 3. In fact, what we should do is pick a number that is *relatively prime* to 15, which means a number that is not divisible by three or five (the prime factors of 15). Four will work. So start with (1,2,3). Add four to each slot: (5,6,7). Add four again: (9,10,11). And again: (13,14,15). Again: (2,3,4). Continue in this manner. Here is the list we get for this whole equivalence class:

(1,2,3)

(5,6,7)

(9,10,11)

(13,14,15)

(2,3,4)

(6,7,8)

(10,11,12)

(14,15,1)

(3,4,5)

(7,8,9)

(11,12,13)

(15,1,2)

(4,5,6)

(8,9,10)

(12,13,14)

and we’re done with this class. We will now move on to the next class starting with (1,2,4). For this class rotating four slots will also work:

(1,2,4)

(5,6,8)

(9,10,12)

(13,14,1)

(2,3,5)

(6,7,9)

(10,11,13)

(14,15,2)

(3,4,6)

(7,8,10)

(11,12,14)

(15,1,3)

(4,5,7)

(8,9,11)

(12,13,15)

Done with that class. The next one in line starts with (1,2,5). Now if we rotate by four we will get overlap between successive triangles. Instead, we could choose to rotate by two:

(1,2,5)

(3,4,7)

(5,6,9)

(7,8,11)

(9,10,13)

(11,12,15)

(13,14,2)

(15,1,4)

(2,3,6)

(4,5,8)

(6,7,10)

(8,9,12)

(10,11,14)

(12,13,1)

(14,15,3)

And we’re done with that class. And so the process continues through all 455 cheeseburgers. So the amount we rotate depends on the equivalence class we’re working in, but we can always pick a rotation that is both relatively prime to 15 and doesn’t result in any overlap between consecutive triangles. In fact, it turns out that we can always choose our rotations from the set {1,2,4}.

Notice that my first 15 cheeseburgers will be isoceles. Then I will be eating scalene burgers for quite some time. Not until the very end do I get to the equilateral cheeseburgers. I have decided that I am going to try to do two per month. That way it will take me just under 19 years to finish. Read Mayo, Relish Onions: A Cheeseburger Review for an account of the first trial of this experiment. Bon Appetit!

That is beautiful! I did think about the problem a little bit and never got anywhere. This is exactly what I was trying to find! Kudos to Sean.

I told some Magic players, who were looking bored while waiting for the tournament to begin, about your little cheesburger experiment and they had a blast trying to figure out how many combinations there were.

Jamie, I think this is a very cool experiment. I would like to try the equilateral cheeseburger Onions, Grilled Mushrooms, A-1 Sauce. Yum!