South African Mathematics Olympiad

a. The chessboard contains an odd number of squares and every time a $2\times 1$ tile is placed, the number of open squares decreases by $2$, an even number. Hence the number of remaining squares is always an odd number (odd minus even is odd).

b. Before any tile is placed, there are $13$ black squares and $12$ white squares. Every time a tile is placed, the tile covers one black square and one white square, so the number of open black squares and open white squares both decrease by $1$. Since there is one more black square than white squares at the start, there will be one more black square than white squares at the end.

c. The following arrangement shows $7$ empty $1\times 1$ squares.

Assume for a contradiction that it is possible to have more than $7$ empty squares. Since there must be an odd number, there are at least $9$ empty squares.

Divide the board into four $2\times 3$ rectangles and one $1\times 1$ centre square:

If the top left $2\times 3$ rectangle had $3$ empty squares, then these three empty squares must be touching diagonally, and hence so must the three covered squares. This means that either $A1$ is covered and $B1$ and $A2$ are empty (impossible with $1\times 2$ tiles) or $B1$ is covered and $A1$, $B2$ and $C1$ are empty (again impossible). This means that this rectangle can contain at most $2$ empty squares. A similar argument shows that all of the $2\times 3$ rectangles have maximum two empty squares. However, this means that to get $9$ empty squares in total, all four rectangles must have exactly two empty squares, and in addition the central square must be empty. It follows that the white squares $C2$, $B3$, $D3$ and $C4$ must all be covered.

Now, from part (b) we know that of the $9$ empty squares, $5$ must be black and $4$ white. The only remaining white squares are $A2$, $A4$, $B1$, $B5$, $D1$, $D5$, $E2$, $E4$, of which four must be empty. None of the pairs $(A2,B1)$, $(A4,B5)$, $(D1,E2)$ and $(D5,E4)$ can be empty, since that would force the corner square also empty, a contradiction. Hence exactly one in each of the above mentioned pairs is empty, and hence the three black squares surrounding it must be covered. For the first white square, this forces three black squares to be covered, and for each of the remaining three white squares, at least two additional black squares are covered, leaving at most $13-(3+2+2+2)=4$ black squares empty, which contradicts the fact that $5$ black squares must be empty.