Given a rectangular grid, split into 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 should be coloured black.
* No four squares forming a -square should be coloured in the same colour.
* No four squares forming a -square should be coloured in such a way that only the diagonally touching squares have the same colour.
For which grid sizes (with ) does there exist a valid colouring?
, 2011
Solution
There exist a valid colouring iff or is odd.
Proof. If, without loss of generality, the number of rows is odd, colour every second row black, as well as the boundary, and all other squares white. It is easy to check that this coloring is valid.
If both and are even, there is no valid coloring. To prove this, consider the following graph : The vertices are the squares, and edges are drawn between two diagonally adjacent squares and iff the two other squares touching both and at a side have the same color.
This graph of a valid coloring has the following properties:
* The corner squares have degree 1.
* Squares at a side of the grid have degree 0 or 2.
* Squares in the middle have degree 0, 2 or 4.
* The "forbidden patterns" are equivalent to the statement that no two edges of the graph are intersecting.
* If you put a checkboard pattern on the grid, no edge connects squares of different colours.
* Hence, if and are even, the corner squares sharing a side of the grid are in different connected components of the graph.
* Since the sum of degrees in each connected component is even, the opposing corner-squares have to be in the same connected component.
* Hence, there is a path from each corner to the opposing one.
But those two paths can not exist without intersecting, thus some forbidden pattern exists always, i.e. there is no valid colouring.
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.