Each of the squares in the following figure are $1m \times 1m$. The figure below needs to be tiled using $2m \times 1m$ tiles. The squares marked $X$ should not be tiled. Is such a tiling possible?
After extensive trial and error experiments I have come to the conclusion that such a tiling is not possible. Is that true? And if so how would one go about proving such a thing?
On
This is a classic case of a tiling proof which is easy by colouring. If the squares are coloured as a checkerboard, consider how many black and white squares you have. And what can you say about the $2\times 1$ tiles in terms of colours?
Although this seems very simple, it can be quite delicate to get the right tiling for a particular case - and in some cases more than two colours come in handy.
On
The clever coloring argument works for squares of any size. However, for the $4\times4$ case, "trial and error" works fine.
First consider the upper right square d4. It must be covered by a horizontal or a vertical tile. By symmetry (the whole figure is symmetric about the diagonal from upper right to lower left), we may assume a horizontal tile, covering the squares {c4,d4}.
Next, the remaining top-row square b4 must be covered by a vertical tile {b3,b4}.
Next, a3 must be covered by a vertical tile {a2,a3}.
Next, the lower left square a1 must be covered by a horizontal time {a1,b1}.
Next, c1 must be covered by a vertical tile {c1,c2}.
But now there is no way to cover b2.
Such a tiling is not possible. To see this, color the square like a chessboard. The upper left and lower right corners have the same color (provided $m$ is even, but otherwise it's trivial), but each $2\times 1$ tile covers exactly one black and one white tile.