Tag: component coloring

Component Colorings II: Diamonds and Triamonds

~ munizao ~ 2 Comments

Here’s a nice coincidence: the numbers of tri-diamonds and di-triamonds are both 9, which is the right amount to tile a regular hexagon of side length 3. And both sets can! Behold the di-triamonds:

3-coloring the triamonds here isn’t hard. The tiling seems to want to have a bunch of points where four triamonds meet, which disrupts chains of forced colors. The challenge is adding more challenges on top of 3-coloring. I suspect that there is no strict 3-coloring of the triamonds. One possibility is a sort of meta-coloring of the di-triamonds where no two di-triamonds with the same color pair may be adjacent. The above diagram doesn’t qualify because there are blue-red di-triamonds touching each other. Problem #60: Find such a meta-coloring.

The diamonds in the tri-diamonds are even easier to 3-color. Enough so that 3-coloring them so each tri-diamond has all three colors (the equivalent of the poorly thought out problem #58 with the tri-dominoes) was no challenge at all. Perhaps there is something to be done with symmetry. Notice that, ignoring color and the tri-diamond outlines, the diamonds in the figure below have an an axis of reflection symmetry. I wonder if, for some tiling, some form of symmetry on the diamonds is possible where colors are included.

The meta-coloring idea above suggests a way to salvage Problem #58. Instead of a three coloring of the dominoes in a tri-domino tiling, we could look for a 4-coloring of the dominoes where every tri-domino contains 3 of the 4 colors, and there is simultaneously a meta-4-coloring of the tri-dominoes where no two adjacent tri-dominoes are missing the same color.

Component Colorings

~ munizao ~ 1 Comment

Previously, I looked at problems concerning colorings of individual cells of polyominoes. These were not map coloring problems, (i. e., problems of giving a set of shapes a limited number of colors so no two adjacent shapes share the same color.) Map coloring the cells of a square grid isn’t very interesting, beyond noting that the grid is 2-colorable, with a checker pattern being the 2-coloring.

But suppose our polyform components are more complicated than individual cells. For example, the components could themselves be polyominoes. Now component-wise map coloring can be a source of interesting problems.

Since 4-coloring is always possible, 3-coloring is the usual place to go to when we want a challenge. Given three colors, the di-dominoes can be component colored in 15 ways. (There are 4 di-dominoes, and because the L-tetromino is asymmetrical, there are two ways to color it for each color pair.) Here is a tiling with 3-colored components:

Moving up to the tri-dominoes, there are 26, which can tile a 12 × 13 rectangle. Problem #58: Find a 3-coloring of the dominoes in such a tiling where each tri-domino contains all three colors. Edit: As Bryce Herdt pointed out in a comment, this is impossible, because there are tri-dominoes where all three dominoes surround a square that could not then take any of the three colors.

Four-coloring can be a worthwhile problem, provided that we can find a good additional restriction on color usage. With the 11 heterogeneous di-trominoes, we can restrict ourselves to two colors each for the I and L trominoes. Then we can find a component-wise 4-coloring of the set using those colors:

Notice that this is a “non-strict” coloring, since two red L’s meet at a vertex. Problem #59: find a strict 4-coloring of the components of the heterogeneous di-trominoes in a 6 × 11 rectangle.

There are undoubtedly other fruitful directions to take component coloring. Perhaps there is something to do with poly-polyiamonds, or poly-polyhexes. I would be delighted to see what you can find!