(Tagging under “A Polyformist’s Toolkit”, as I feel that series ought to have an entry on coloring, and this more or less says what I have to say about that.)

At Gathering for Gardner 11 in 2014, I gave a talk about crossed stick puzzles. It was the obvious thing to talk about, since I had been making a lot of interesting discoveries in that area. Unfortunately there was too much good stuff, and I couldn’t bear to trim very much of it out, so I made the classic mistake of going over on time and having to rush the last slides. (G4G talks are generally limited to 6 minutes.) When I was looking for a subject for this year’s talk, there was nothing I felt an urgent desire to talk about. This would be the 12th Gathering for Gardner, and there is a tradition that using the number of the current Gathering, either in your talk or your exchange gift, is worth a few style points. Since I’m a polyformist, and Gardner famously popularized the twelve pentominoes, revisiting some of my pentomino coloring material seemed reasonable.

Finding interesting map colorings is a nice puzzle that we can layer on top of a tiling problem. A famous theorem states that all planar maps can be colored with four colors so no two regions of the same color touch. Since this can always be done, and fairly easily for small maps like pentomino tilings, we’ll want some properties of colorings that are more of a challenge to find. I know of three good ones:

1. Three-colorability. Sometimes we only need three colors rather than four. For sufficiently contrived sets of tiles we might only need two, but for typical problems that won’t work.
2. Strict coloring. For most purposes, (like the Four Color Theorem) we allow regions of the same color to touch at a vertex. If we do not allow same colored regions to touch at a vertex, we call the legal colorings strict. Notice that a 3-coloring of polyominoes is strict if and only if it contains no “crossroads”, i.e. corners where four pieces meet.
3. Color balance. If the number of regions of each color is equal, a coloring may be considered balanced. Conveniently, 3 and 4 are both divisors of 12, so we can have balanced 3-colorings and 4-colorings of pentomino tilings.

The above information would make up the introduction to my talk. It would also, suitably unpacked and with examples, take up most of the alloted time. That left little enough room to show off nifty discoveries. So whatever nifty discoveries I did show would serve the talk best if they could illustrate the above concepts without adding too many new ones. One that stood out was this simultaneous 3- and 4-coloring with a complete set of color combinations, discovered by Günter Stertenbrink in 2001 in response to a query I made on the Polyforms list:

This is the unique pentomino tiling of a 6×10 rectangle with this property where the colorings are strict. I used it to illustrate 3- vs. 4-coloring by showing the component colorings first, before showing how they combine. To my astonishment, the audience at G4G12 applauded the slide with the combined colorings. I mean I think it’s pretty cool, but I consider it rather old material.

I still wanted one more nifty thing to show off, and while my page on pentomino colorings had several more nifty things, none of them hewed close to the introductory material, and the clever problem involving overlapping colored tilings that I was looking at didn’t seem very promising. Setting that aside, I wrote some code to get counts of the tilings of the 6×10 rectangle with various types of colorings. That gave me the following table:

What stood out to me was the 2338 tilings with balanced colorings. Since there are 2339 tilings in total, that meant that there was exactly one tiling with no balanced coloring:

Notice that the F pentomino on the left borders eight of the other pentominoes, and the remaining three border each other, so there can be at most two pentominoes with the color chosen for the F, and no balanced coloring can exist. A unique saddest tiling balancing out the unique happiest tiling was exactly what my talk needed. Now it had symmetry, and a cohesive shape. Having important examples all using the 6×10 rectangle removed the extraneous consideration of what different tiling problems were out there, and helped to narrow the focus to just the coloring problem. Anyway, I don’t want to go on any more about how awesome of a talk it was, (especially because video of it may eventually go up on the internet, which would show how non-awesome my delivery was) but it was my first G4G talk that I was actually proud of. The slides for the talk are here.

One thing I’m curious about that I didn’t mention in the talk: has anyone else found the saddest tiling before me? Looking through old Polyform list emails, I found that Mr. Stertenbrink enumerated the 3-colorable tilings of various types (essentially, the bottom half of the table above) but not the 4-colorable tilings. From the perspective of looking for the “best” colorings, it makes sense to focus on the 3-colorable tilings, but it meant missing an interesting “worst” coloring.