# Prove that it is not possible to completely cover a 6 × 6 chessboard by tiles which have dimensions 1 × 4.

I think I have some sort of understanding of how to solve this but I'm not sure.

I would colour the board with 4 colours such that every 1x4 rectangle would cover one of each colour.

Then cover the bottom 4 rows such that we are left with a 2x6 rectangle.

Then fill the 4 leftmost columns so we are left with a 2x2 square which will have 2 tiles of the same colour hence it is impossible to cover the board with 1x4 tiles.

Would that be a correct answer?

Edit: My colouring scheme works like this: The 4 colours will be represented as 0,1,2 and 3.

Working along the top row of the board, we may as well label the first four squares 0, 1, 2 and 3, in that order.

In order to satisfy the property that any 4 × 1 rectangle placed on the board occupies one square of each colour, the next square along must be labelled 0. And the next square along must be labelled 1, and the next square along must be labelled 2, and the next square along must be labelled 3, and so on.

So we see that every square in the first row will be coloured according to the repeating pattern 0, 1, 2, 3, 0, 1, 2, 3, . . .. Since this seems to work along the first row, we can use the same trick to fill the first column.

Then cycle through the rows marking tiles in the same pattern. (The first tile of the second row is 1 so the tile to the left of it is 2, the next one is 3 and so on for every row)

Finally the board will be coloured in such a way that the square in row i and column j is coloured i + j modulo 4.

• I doubt it. Just because you prove that one pattern doesn't work doesn't mean that there isn't another which does. – Tom Collinge Sep 7 '15 at 12:37
• Have you designed a colouring scheme that works in line with your second sentence - so that it works for every orientation of the tiles? – Mark Bennet Sep 7 '15 at 12:38
• @MarkBennet Yes I have, any 1x4 tile would cover 4 different colours in my scheme – Mark S Sep 7 '15 at 12:43
• So can you describe your scheme accurately so we know what it is? – Mark Bennet Sep 7 '15 at 12:48
• @MarkBennet I edited my question to include the description and Gerry provided the board that I designed. – Mark S Sep 7 '15 at 13:11

Color the board like this: $$\matrix{1&2&3&4&1&2\cr2&3&4&1&2&3\cr3&4&1&2&3&4\cr4&1&2&3&4&1\cr1&2&3&4&1&2\cr2&3&4&1&2&3\cr}$$ Show that wherever you put a $4\times1$ it covers one of each color, note that there are 10 2s and only 8 4s to be covered, QED.

• Yes, that is what I had in mind and was wondering if this is sufficient to prove the statement. Thanks. – Mark S Sep 7 '15 at 13:10

Let me assume that my chess board is constructed as follows... my first row starts with red, green and so on... my second row starts with white, black, and so on... and again the next two rows are similar to the first and second rows and so on... now if I tile the chess board of mine it will cover an even number of colors that is two of any and two of other. If we assume that we had tiled with say $X$ tiles then the number of say red colors covered would be even but total number of red colors is $9$ which is odd. Here comes our contradiction to our assumption. So it is not possible to tile a $6\times6$ chess board with $1\times4$ tiles...

In every second row, color every second field black. All other fields remain white. So in total, there are 9 black fields.

w w w w w w
w B w B w B
w w w w w w
w B w B w B
w w w w w w
w B w B w B


Verify that any way to place a 1×4 tile on that board will cover an even number of black fields, either 0 or 2.

Contradiction: A complete tiling would have to cover an odd number of black fields.