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).

Proof of radlam Classification

Enough talk, let’s do some math.

Sketch of proof of the classification theorem given in The Graph Type of a Polyomino. (I defined radlams in the post Raldams.):

First we need some lemmas on how radlams decompose.

Lemma 1 (the Anthony Decomposition): Removing a domino from a radlam leaves radlams as the remaining components (pieces). That is, if R is a radlam containing a domino D then R-D consists of one or more polyominoes, each of which is a radlam.

Proof of Lemma 1: Let P be a component of R-D. Suppose that D’ is a domino in P (if there are none, then P is a monomino, which is a radlam and we are done). Now consider R-D’. Since R is a radlam, at least one component of R-D’ is a monomino. Call this monomino M. The claim is that M is a component of P-D’. There are two things to check: (1) M is contained in P and (2) M is not connected to any other squares in P-D’. I will let you convince yourself of facts (1) and (2).

In fact, the proof of Lemma 1 doesn’t actually use the fact that D is a domino. All it uses is the fact that D is not a monomino. (The problem that you run into when D is a monomino is that M may equal D.) So we have shown:

Lemma 2: If R is a radlam and P is a subpolyomino of R, but P is not a monomino, then R-P is a radlam.

Lemma 3: If P is a polyomino containing a domino D and if the components of P-D are all monominoes, then P has size 6 or smaller.

Proof of Lemma 3: It’s pretty easy to convince yourself of this.

Using these lemmas we can prove:

Lemma 4: If R is a radlam of size 3 or larger, then R decomposes into two radlams P and Q, with Q of size six or smaller and neither P nor Q of size zero

Proof of Lemma 4: Check all radlams up through size 6 by hand. Thus, we assume that R has size 7 or greater. Remove a domino D from R. Since R is of size 7 or greater at least one component of R-D must be larger than a monomino. Call this component Q’. Now P’:=R-Q’ is connected. If Q’ has size 6 or smaller, then we are done. If not, then choose domino D’ in Q’, such that D’ is adjacent to P’. Then Q’-D’ consists of radlams, at least one of which is larger than a monomino (since Q’ was assumed to have at least size 7). Let Q” be one such component of Q’-D’. Let P”=R-Q”. P” is connected because everything in (Q’-D’)-Q” is adjacent to D’, and D’ is adjacent to P’. If Q” has size 6 or smaller we are done. If not, iterate the process.

Now the proof proceeds by induction. Check that the list is complete for radlams up through hexominoes I guess. Assume that the list is complete up through size . To get size you just have to check how you can glue together two radlams P and Q, with Q of size and P of size …and then you’re done!

I’m pretty sure that this proof is correct and I that at some point I checked all the details, but there very well may be holes, so let me know if you find some.

The Graph type of a Polyomino

This is a continuation of the post radlams.

A graph is some dots (called nodes or vertices) and lines between some of them (called edges). It’s not the geometry of the graph that matters, just how the vertices are connected up by edges.

Associated to each polyomino is a graph, called the graph-type of the polyomino. You get it by putting a vertex at the center of each square and then adding edges between the vertices of adjacent squares:

It turns out (my friend Sean, a graph theorist, pointed this out to me) that whether or not a polyomino is a radlam depends only on its graph type.

Radlams can be pretty easily classified by their graph type. Basically they come in two infinite families. The open ones:

And the closed ones:

If you notice, there are no radlams of size for except for , in which case we have the single radlam:

Making it unique.

In a subsequent post I will outline a proof of this classification theorem. (by the way, I’m pretty sure that I got all of them in the above lists. If not please let me know).

Radlams

There are five tetrominoes:

All but one of them decompose into two dominoes:

For the T, no matter which domino you remove, you are left with a pair of monominoes:

There are 12 pentominoes:

All but one of them decomposes as a domino and a triomino:

For the X, you are left with three monominoes no matter which domino you remove.

It is not hard to see that any polyomino of size six or more can be decomposed into two polyominoes neither of which is a monomino (let’s call such a decomposition a nontrivial decomposition). Here is one way to see that: Let be a polyomino of size six or more. Remove a domino, , from . It is not hard to see that consists of at most 4 pieces.

If any one of the pieces of (call that piece ) is any larger than a monomino, then is a nontrivial decomposition of . There are only two cases that this proof does not cover:

Both of which have nontrivial decompositions:

So if we wanted to study polyominoes with only trivial decompositions (which is what I had in mind originally) we are done already. But notice that these polyominoes:

have something in common. If you Remove Any Domino from any of them you Leave A Monomino (at least one monomino) in the resulting decomposition:

I like to call these RADLAMs (well, actually I like to write radlams) which is an acronym for Remove Any Domino, Leave A Monomino. A better name though is probably R2L1, because the definition generalizes:

Definition: An RnLm is a polyomino for which if any -omino is removed, there is an -omino left in the decomposition, where

For instance, we have seen R2L1′s above. Here are some R3L1′s:

Can you think of others?

I’ll have more to say about radlams, or R2L1′s in a future post. Until then, see what you can do with them, and let us know! I haven’t thought much about RnLm’s with n or m large, so even some nice examples of those would be cool.