Tiling troubles

Perpendicula, the magnificent princess of the rectangle, is admiring her magnificent new bathroom. It's rectangular of course; 10m wide and 20m long. It still needs tiling, though, and Perpendicula has ordered tiles of pure gold to mirror the dimensions of the bathroom: they are 1m wide and 2m long.

There is a problem though: water, milk and honey pipes need to be fitted in two diagonally opposed corners of the bathroom. This means that in each of these two corners a square area of 1m×1m has to remain untiled. Can the rest of the floor area be tiled without cutting any of the 2m×1m tiles?

The solution

Think of the pricess's bathroom as a rectangular chess board consisting of 1m×1m tiles which are alternately black and white. Now remove two diagonally opposed squares. The problem is whether we can tile the remaining area by our 2m×1m tiles.

The clue lies in the colours: say that we have removed the top left and bottom right square, and assume that the top left square is black. Since the number of squares in a row is even (there are ten 1m squares) we know that the top right square is white. The number of squares in a column is also even (twenty 1m squares), so the bottom left square is black. We have therefore removed two black squares. Originally, our board had the same number of black and white squares (100 of each), so the remaining areas has two more white squares than black squares. But each of our 2m×1m tiles covers one black and one white square, so we cannot possibly cover an area with less black squares than white ones — the princess will have to cut the tiles!

This, incidentally, is quite a well-known puzzle which usually goes by the name of the mutilated chess board problem. It's of great interest to computer scientists because it's a classic example of a problem whose solution becomes simple once you've discovered a trick — in this case, the trick is to think about colours. At the moment only humans have the ability to come up with such tricks. Computers can only follow a set of mechanical instructions. The mutilated chess board problem has therefore been a focus of artificial intelligence research — is it possible to program a computer to think creatively?