A Case of Accidental Symmetry

The other day I was thinking about putting dominoes onto a 4-by-4 grid without any of the dominoes contacting each others’ sides. I wanted to know how many dominoes you could fit onto the 4-by-4 grid in this way, and what the different configurations looked like. I was pretty sure that the answer to the first question was that four dominoes could be fit onto the grid. I was less sure that I had found all of the configurations allowed. (I had three configurations.)

So, I started from square one: I found all of the ways (up to symmetry) of putting one domino on the grid (there are four). Then combining those I found all of the ways of putting two dominoes on (there are 20). Then by taking all of my configurations of two dominoes and adding one I found all of the ways of putting three dominoes on (there are 20). Finally I used my 3-domino configurations and found all of the 4-domino configurations by adding one to the ones that allowed it. I discovered that I had missed a 4-domino configuration! So there are four 4-domino configurations. And since I couldn’t legally add a domino to any of those, I knew there were no 5-domino configurations. Cool.

But wait…4, 20, 20, 4. There’s symmetry there! Could it be that this is a general thing? Is there a way to transform the four 1-domino configurations into the four 4-domino configurations? Likewise, did the same (or a similar) transformation change the 20 2-domino configurations into the 20 3-domino configurations? It might be something like the binomial coefficients: the number of ways to choose two people out of a group of five is the same as the number of ways to choose three people out of a group of five.

Then, my heart sank…I thought of this fact: there is exactly one configuration with no dominoes (just an empty grid), but there are zero 5-domino configurations. The symmetry is broken. There apparently is no such transformation.

Still, the 4, 20, 20, 4 pattern is fascinating (even if the pattern is really 1, 4, 20, 20, 4). I shared this with Jason Lee, a mathematical friend. Jason thought (as I had originally) that there was some transformation that we were missing. He suggested we look at larger grids to see if we see similar patterns. I bet him a bottle of rootbeer that we wouldn’t. He accepted the bet, and proceeded to code up an algorithm for enumerating domino configurations with grid-size as a parameter. The algorithm didn’t find any such nice symmetries for larger grids. I wish I could be more specific about the details, but I don’t have them in front of me right now. In the next couple of days I’ll talk to Jason about sharing his Python code here on my blog, along with specifics of numbers of configurations for larger grids. In any case, I got my rootbeer!

Above I’ve posted a drawing of the 4, 20, 20, 4 configurations mentioned (click on it to see it enlarged). Do you see a reason for the symmetry? Is there some transformation we’re missing? In any case, I think it makes for a nice picture.

By the way, the original impetus for thinking about this was the December 2012 IBM Ponder This puzzle. There we are asked to place numbers in a 6-by-6 grid. The highest numbers that we can place are fives, and the rules given there imply that any fives come as dominoes of four-five pairs lying in the central 4-by-4 grid with our no-contact constraint.

Latin Squares, Squared Squares, and Legoed Squares

I introduced my kids to Latin Squares the other day. If you know Sudoku then you have seen examples of Latin squares. The idea is to fill in a grid of squares with colors or numbers or some other symbols, such that each symbol appears exactly once in each row and each column. (see also the Wikipedia Latin square entry). I handed them graph paper and let them loose. This is what my eight-year-old produced:
Note that she produced some Latin squares, but also explored other ideas.

I wasn’t sure initially how long my kids would be content to explore Latin squares, so I also planned to tell them about squared squares. A squared square is just a square made up of smaller squares (this is easy to accomplish). A perfect squared square is much more difficult, consisting of squares each of different sizes. For a long time it was thought that perfect squared squares didn’t exist, but they do! Here is the smallest (in some sense) one:
We got excited about it and decided to make one for our wall:

Next, the ten-year-old wanted to produce some squared squares of his own, but found the perfect ones difficult (they were thought to be completely non-existent for a long time after all). He settled for producing imperfect ones. After making an imperfect squared square on graph paper, he decided to reproduce it with Legos. Here is the result: This led us to considered perfect Legoed squares. That is to say, squares made up of some number of Lego pieces, each piece having a unique size. Here is one of our first examples: It’s a 3×3 made up of a 1×1, a 1×2, and a 2×3. Here’s another, somewhat larger: We found a bunch more (maybe ten or so total). I’m not sure that we got all of them. How many can you find?

Look for up-coming posts on: 1) further progress in building our marble computer, and 2) teaching my five-year-old to count (which required some deep thought about just what counting is).

How to Eat an Equilateral Cheeseburger

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!