[Math] Given a grid of $m \times n$ squares in black and white. Given a rule, which grid sizes $m \times n$ (with $m,n \ge 3$) have a valid colouring

Question

Given a rectangular grid, split into $m \times n$ squares, a colouring of the squares in two colours (black and white) is called valid if it satisfies the following conditions:

• All squares touching the border of the grid are coloured black.
• No four squares forming a $2 \times 2$ − square are coloured in the same colour.
• No four squares forming a $2 \times 2$ − square are coloured in such way that only diagonally touching squares have the same colour.

Which grid sizes $m \times n$ (with $m,n \ge 3$) have a valid colouring?

---

Attempt:

I noticed that for $3 \times 3$, $5 \times 5$, there is a valid colouring. For $4 \times 4$ there is no valid colouring. Here is the image of $2\times2$ sub-squares that violate the rule:

So we cannot have a subsquare as one of the four above.

---

Answer 1

Let's say $m$ is the number of rows and $n$ is the number of columns.

If $m$ is odd, then we can find a simple valid coloring by coloring alternate rows black and white (except for the black borders of course). If $n$ is odd, we can do the same thing with the columns to find a valid coloring.

The case remains where $m$ and $n$ are both even. Claim: there is no valid coloring in this case.

Proof: Assume the claim is false, i.e. there is a valid coloring when $m$ and $n$ are both even.

Consider the interior corners of the grid, and color them red and blue in a checkerboard pattern as in the image below. Now construct a graph using these corners as vertices, connecting two corners along a grid edge if and only if the edge separates a black square and a white square.

Now for each vertex of this graph, the colouring rules enforce that exactly two edges are incident to this vertex. Furthermore, every edge connects a red vertex with a blue vertex.

So the number of edges is exactly twice the number of red vertices (there are two edges for each red vertex), and the number of edges is also exactly twice the number of blue vertices. That means there are as many red vertices as blue vertices, so the total number of vertices is even.

But wait, that's impossible! Because the total number of vertices is exactly $(m-1)(n-1)$, which is a product of two odd numbers and therefore odd. We have a contradiction, so our last assumption is false, therefore the claim is true.

Alternate contradiction: Ignoring the vertex colors, if there are two vertices incident to each edge and two edges incident to each vertex, then the number of vertices and edges is the same. There's an odd number of vertices, so there's an odd number of edges.

However, in each column of squares, there's an even number of horizontal edges, since the squares change between black and white an even number of times in the row. Similarly, in each row of squares, there's an even number of vertical edges. Summing all these even numbers, we count each edge exactly once, so the total number of edges must be even. That's a contradiction.