BALTIC-WAY 2011 Problem 9

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