MathLabs

Problem 3

Define a hook to be a figure made up of six unit squares consisting of a row of three squares and a column of four squares sharing a corner square, together with one further square attached at the far end of the row (or any figure obtained from this one by rotations and reflections). Determine all m×nm\times n rectangles that can be covered without gaps and without overlaps by such hooks, with no part of a hook covering area outside the rectangle.
Step 5 of 6: A coloring argument on the two tile types
Previous stepNext step
color every 4th column red:#red cells covered by a type-1 tile is odd, by a type-2 tile is even  ⟹  #type-1 tiles is even\text{color every 4th column red}: \#\text{red cells covered by a type-1 tile is odd, by a type-2 tile is even} \implies \#\text{type-1 tiles is even}
Detailed analysis

In type 11, the two hooks together occupy four consecutive columns, with exactly 33 cells in each column; every row met by the tile contains 22 or 44 cells. In type 22 these roles are transposed: it occupies four consecutive rows with 33 cells in each, and every column met contains 22 or 44 cells. Color columns whose indices are multiples of 44. In the case needed below, both side lengths are even, so the rectangle contains an even number of red cells. A type-11 tile meets exactly one column in each block of four and therefore covers exactly 33 red cells, an odd number. A type-22 tile covers either 22 or 44 cells in any red column that it meets, hence an even number of red cells. Since the tiles partition the rectangle, the number of type-11 tiles is even. Exchanging rows and columns gives the same conclusion for type-22 tiles.