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? 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. 

 A: 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.
A: Hint: 
If $m>3$ and an $m\times n$-grid has a valid coloring, then so does an $(m+2)\times n$ grid; simply split the grid between a pair of rows not at the edge, and then insert this pair of rows in reverse order.
From here it suffices to show that a few small grids have a valid coloring, and a few small grids do not.

Details:
Without loss of generality $n\geq m$. If $m\leq2$ then there is only one coloring, which is valid for $m=0$ and $m=1$ and invalid for $m=2$. For $m=3$ it is easy to see that every $3\times n$ grid has a valid coloring, where $n\geq3$. It remains to determine for which $m,n\geq4$ the $m\times n$-grid admits a valid coloring.
Proposition: If $m\geq4$ and the $m\times n$-grid has a valid coloring, then the $m\times(n+2)$-grid has a valid coloring.
Proof.
Let $m\geq4$ and suppose the $m\times n$-grid has a valid coloring. Split the grid in two between the second and third columns, and insert the third and second columns in between. This yields a valid coloring of the $m\times(n+2)$-grid. After all, validity can be checked by checking every adjacent pair of columns, and there are pairs of columns in the new $m\times(n+2)$-grid that are not already in the valid coloring of the $m\times n$-grid.$\qquad\square$
Example: The $4\times8$-grid has a valid coloring because the $4\times6$-grid does:

Result: The $m\times n$-grid admits a valid coloring if $m,n\geq4$, except if $m=n=4$.
Proof. There is only one coloring of the $4\times 4$-grid, and it is invalid. There are valid colorings of the $4\times5$-, $4\times6$- and $5\times 5$-grids. Repeated application of the proposition then yields the result.$\quad\square$
