2
$\begingroup$

A tiling of an n × n square grid is formed using 4 × 1 tiles. What are the possible values of n?

A tiling has no gaps or overlaps, and no tile goes outside the region being tiled.

$\endgroup$

1 Answer 1

5
$\begingroup$

I'll generalise it slightly to ask what $m\times n$ grids can be tiled.

The tile has area $4$, so clearly we need $mn$ to be divisible by $4$.

If $m$ or $n$ is divisible by $4$, then the grid tiles in a trivial way, with all the tiles oriented in the same way along that divisible dimension.
The only other case is when $m$ and $n$ are both even but not divisible by $4$. This case is not tileable, which can be proved with a straightforward colouring argument. Split the grid into $2\times 2$ regions, and colour these like a chessboard. This chessboard has $\frac{m}2\times\frac{n}2$ regions, which is odd, so there will be more regions of one colour than the other. Whichever way you place a $1\times4$ tile, it will colour two cells of each colour, so there is no way to cover more of one colour than the other, and in particular there is no way to cover the whole grid.
So the only rectangular (or square) grids that can be covered have at least one dimension divisible by $4$.

$\endgroup$
1
  • $\begingroup$ I just found a different argument in this post where it was about a $10\times10$ grid. $\endgroup$ May 20 at 11:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.