Most of my previous polyform coloring explorations involve map colorings of complete polyforms, i.e. colorings that adhere to the rule that no two adjacent shapes have the same color. We can color the cells of a grid instead; for example, a checkerboard is a two-coloring of the regular square tessellation, and checkered polyomino tiling problems have a long history. But for this post I want to look at problems where finding a coloring is part of the solution, rather than the coloring being given in advance.
Quite a while back, I used cell colorings for a couple of minimal common superform problems. Below, the cells of the figure on the left have been colored so that each of the 12 pentominoes occurs exactly once containing cells of all five colors. (For the common superform problems in this post, I am copying out the individual pentominoes on the right, to make it easier to see that they have a valid coloring for the problem.)
In the following figure, three colors are used. If a pentomino contains cells of two of those colors, there are 12 different color proportions possible. The figure contains each pentomino exactly once containing two cell colors, and each color proportion occurs once.
Both of these are solutions I found manually, so you may be able to find smaller figures with the desired properties.
With four colors, there are 12 ways to combine them in a 2:2:1 proportion. We could try to find a 4-colored pentomino tiling where we could overlay a second pentomino tiling so that each color combination occurs in one pentomino. The graphic below is the result of a little exploratory noodling. I just picked a tiling at random, and then tried to see how far I could get with overlaying a second tiling without repeating a color combination or using one that is not 2:2:1. Getting 8 on my first try makes me optimistic about a solution existing.
There’s nothing special about 2:2:1, either. Any proportions of the form a:a:b:c will give 12 combinations. (Zeros being implied.) So 3:1:1, or even 3:2 or 4:1 might be possible.
Problem 55: Find a pair of overlapping pentomino tilings of a rectangle where the first is 4-colored, and the second is cell-colored so that all color combinations with given color proportions are present in a single pentomino. And if that’s too easy, is it ever possible to take a solution to this problem, and then 4-color the second tiling so that the first has all of the color combinations?
We can also apply the complete set of color combinations concept to a cell-colored minimal common superform problem. Here’s a 23 cell superform of the pentominoes where each pentomino appears with a unique 2:2:1 color combination. Can you find a smaller one?
And that’s all I have for cell colorings for now. Coloring problems more generally are something I have come back to a number of times, and I expect to have another post or two to say on the subject as I plow through my as yet unblogged polyform material from the last year.
