MathDB

9

Part of 2011 Baltic Way

Problems(1)

Which m x n grids have a valid colouring?

Source: Baltic Way 2011

11/6/2011
Given a rectangular grid, split into m×nm\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×22\times 2 square are coloured in the same colour. [*]No four squares forming a 2×22\times 2 square are coloured in such a way that only diagonally touching squares have the same colour. Which grid sizes m×nm\times n (with m,n≥3m,n\ge 3) have a valid colouring?
geometryrectanglecombinatorics proposedcombinatorics