09 Colouring

Consider the following problem.

Example 9.1

An 8 by 8 checkerboard has it top-left and bottom-right squares removed. Can 31 dominoes (1 by 2) can be placed over the remaining 62 squares?

Discussion

At first sight this can seem a tantalising problem with the student trying for some time to show an arrangement. However, as with the chameleon problem (Example 8.2 in the Invariance chapter), a solution is not reached and the student is left wondering why not. In the end, the reason is obvious.

Solution 9.1

Each domino necessarily has one of each colour in the normal checkerboard coloring scheme. However the two squares removed are of the same colour, leaving an imbalance.

A little lift in difficulty

The following problem, taken from the International Mathematics Tournament of Towns, is an extension of this idea.

Example 9.2

A 7 by 7 square is made up of sixteen 1 by 3 tiles and one 1 by 1 tile. Prove that the 1 by 1 tile lies either at the centre of the square or adjoins one of its boundaries.

Discussion

This problem has a rather surprising result and at first sight, with all the combinations possible, seems almost impossible to prove. But an extension of the domino question above, colouring with 3 colors instead of 2 and looking at the resultant way in which a 3 by 1 domino might cover squares of the board, makes the problem accessible.

Solution 9.2

(By my colleague John Campbell)

Label each of the squares as follows.

Each 1 by 3 tile must cover squares labeled A, B and C, because they would be filling adjoining squares. Since there are 17 As and only 16 Bs and 16 Cs, the 1 by 1 square must therefore occupy a square marked A.

However, because the orientation of the square is not relevant, we should eliminate all those occurrences of As which do not remain as As on rotation by, say multiples of 90^o. This leaves only those in the corners, the four along the mid-points of each outer edge, and the one in the centre. This completes the proof.

Discussion

The following diagram show two such tilings, one with the 1 by 1 square in the centre, and the other one with it on the edge.

In fact, by rotating the bottom left 4 by 4 square in the diagram on the right, all three possible positions of the monomino can be achieved (centre side, centre and corner).

Example 9.3

Show that a tiling of a 5 by n rectangle with P-tiles is not possible if n is odd.(A P-tile is a pentomino with the shape below.)

Discussion

• If n is even the tiling is possible because in each successive pair of columns the tiles can be placed vertically with the strokes of the P interlocking in the centre.

• This problem was developed by Mike Newman and me during a maths challenge problems committee meeting in 1998 and in fact made the IMO short list for Romania 1999.
• The following proof was supplied by Professor Andy Liu of Edmonton.

Solution 9.3

Consider the first, third and fifth rows of the rectangle to be coloured black and the others coloured white,, as shown.

No matter where a P-tile is placed, it must cover 3 squares of one colour and 2 squares of the other colour. Since the ratio of black squares to white squares is 3:2, each P-tile must cover 3 black squares and two white squares. It is not possible for a P-tile to cover just one white square in a row. Each P-tile must cover 2 white squares in the one row, so the number of white squares covered in each row is even. But if n is odd there is an odd number of white squares in each row. Therefore the tiling is impossible.