Tiling a grid

Covering a region using a set of shapes, without gaps or overlaps, is called TILING. Tangram puzzles are one kind; grids are another, and they let us reason precisely.

Consider a 4 × 6 grid of unit squares — 4 rows and 6 columns. Can it be tiled with copies of a 2 × 1 tile, allowing the tile to be rotated? Yes, and in many ways: one is to fill each column with two vertical tiles.

Now try a 5 × 7 grid. Here is an argument that settles it without any trying. The grid has 5 × 7 = 35 unit squares. Each tile covers exactly 2 squares. So any number of tiles covers an EVEN number of squares — and 35 is odd. No tiling is possible.

That gives general rules. If BOTH m and n are even, the grid is tileable: fill each column with vertical tiles, which works because the number of rows is even. If ONE of them is even, the same idea works along that direction. If BOTH are odd, the total m × n is odd, and by the argument above it can never be tiled.

Now a harder case. Take a 5 × 3 grid — 15 squares, odd, so not tileable — and REMOVE one unit square. Now there are 14 squares, an even number. Is it tileable? Sometimes yes, sometimes no, depending on WHICH square you remove. Counting alone can no longer decide it.

Here is a beautiful way to settle it. COLOUR the grid like a chessboard, so every black square has only white neighbours and every white square has only black. Now a 2 × 1 tile, wherever it is placed, always covers exactly one black square and one white square.

So any region that can be tiled must have EQUAL numbers of black and white squares. If a particular region has 8 white squares and 6 black, it can never be tiled — no matter how long you try. Isn't it surprising that making the problem more complicated, by adding colours, makes it easier to solve?