A W-polyomino is a polyomino with 2 cells in each row (except possibly the last, which may have one cell), and each row offset once cell to the right.
Below are the first few W polyominoes.
How many colors are necessary to color the plane, so that no matter how we place the polyomino, it never covers two cells of the same color?
For even $n$, we need $n$ colors: a coloring is given by
$C_n(x, y) = (x + yn/2) \bmod n$. This is a coloring with $n$ colors that repeat in each row, and each second row is offset by half $n$. For example, this is the coloring $C_6$.
For odd $n$, we can use $C_{n+1}$ to show that we need at most $n + 1$ colors. The missing piece is to prove that $n$ colors is not enough. (This is my question.)
So far:
(We ignore the monomino, which is an exception.)
- For $n = 3$, we need 4 (we can cover any two cells of a $2\times 2$ square).
- For $n = 5$, we need 6 (a bookkeeping proof is given in Polyominoes on a Multicolored Infinite Grid).
The proof used for $n = 5$ is not very difficult, but it is not clear how it can be generalized.
Background: I am looking at the general case for polyominoes. From the paper I linked above I could devise some general techniques. I recently asked the same question for rectangles, which is very relevant as we can often reduce the problem to that, or at least establish a range.
Here follows some of the general principles. $H(P)$ is the rectangular hull of polyomino $P$, and $C(P)$ the number of colors we need to color $P$, and $|P|$ is the number of cells in $P$.
- $|P| \leq C(P) \leq C(H(P))$. (The number of colors is between the number of cells and the number of colors we need for the hull).
- If $P$ covers any two cells of $Q$, then $C(P) \geq C(Q)$.
- If $Q \subset P$, then $C(P) \geq C(Q)$. (This follows from above and is usually more convenient.)
- If $P$ is an L shape (a rectangle with a rectangle removed at the corner), then $C(P) = C(H(P))$.
- If $P$ can fit inside $Q$ in all orientations, and $Q$ tiles the plane, $C(P) \leq |Q|$.
A typical scenario: Consider this polyomino $P$:
# ##
###
It has the L-tetromino as subset, so we need at least the same as the hull of the L, which is $R(3, 2)$, which has been shown to need 8 colors. Since the hull of $P$ is $R(4, 2)$, which also requires 8 colors, we know we need 8 colors for $P$ too.
The W-pentomino is the first polyomino that cannot be handled by the above. (It is enough for all other polyominoes with 5 or less cells, and all but 6 hexominoes, of which one is also a W-polyomino.)
Best Answer
Here is an proof that for odd $n$, $n$ colors is not enough, from which it follows that we need $n+ 1$ colors.
Lets assume we need only $n$ colors. Place the W-polyomino anywhere, and color the cells that it covers from $0$ to $n - 1$.
Now place the W-polyomino so that it covers all the same cells except the one with color 0. The uncolored cell must be of color 0 (since we have only $n$ colors and all the other colors are used already).
Repeat with color 1.
We can continue in this way, but for this proof we need to go only this far.
Now put the W-polyomino so that it covers the first few cells with even color, but none with odd colors. The cells that are not colored yet must be colored with the odd colors, one of each (again, because we only have $n$ colors). In particular, one of the cells must be color 1. It cannot be the cell next to color 0, since it lies in the same W shape as the cell below which also has color 1. Therefor, one of the remaining cells must be color one. Those cells are marked orange in the figure below.
Finally, move the W-polyomino one cell down and one to the right. It now covers all three orange cells (one of which must be color 1), and another cell with color 1. This violates the condition of this being a legal coloring, which means, we cannot get away with only $n$ colors.
It is worth seeing how this proof fails for when the number of cells is even, and for other polyominoes resembling W-polyominoes, such as these:
There are two possible extensions that may be worth looking at.
The first is polyominoes similar to W-polyominoes (scaled copies of W-polyominoes).
My suspicion is that for $W_n$ scaled by $r$, we need $r^2(n+1)$ colors if $n$ is odd. The proof above does not work directly, but if we keep careful track of the extra colors, and analyse the cases, it works. What is interesting about this specific example is that it is usually easy to prove that if we need $C(P)$ colors for $P$, we need $r^2C(P)$ colors for a copy of P scaled by $r$ (provided it holds for rectangles, which is the other case where it is not always easy to prove).
The second is this type of polyomino:
L-polyominoes are interesting because they require so much colors compared to their area (the same as their bounding box); W-polyominoes are interesting because they can be quite large without having large Ls as sub-polyominoes. The type of polyomino shown above is a nice combination of these two properties.