# How do I solve this tile-covering problem? [closed]

Consider an $$n\times n$$ chessboard whose top-left corner is colored white. But Alice likes darkness, so she wants you to cover those white cells for her. The only tool you have are black L-shaped tiles each of which covers $$3$$ unit cells.

Formally, each tile covers unit cells satisfying the following:

1) Two of the cells are adjacent to the third (shares a side).

2) All three of the cells do not lie on the same row or same column.

3) No two tiles should overlap (cover the same cell) or go outside the board.

Since these tiles cost a lot, you have to cover all the white cells using the minimum number tiles.

Example : $$1\times1$$

there's a single cell which is white. Since one tile needs $$3$$ empty cells, there's no way to cover this cell.

Example(2) : $$4\times4$$

Answer : $$4$$ ($$4$$ tiles can be placed as shown)

For any given $$n$$, what will be the minimum number of tiles?

For even $$n$$ the pattern you show can be extended nicely. You need $$\frac {n^2}4$$ tiles.
The below proof assumed that all the Ls had to cover two white and one black squares. I believe it is still impossible for odd $$n$$, but have not found the proof.
For odd $$n$$ you can't do it at all. The proof is by induction. We only need to consider the two leftmost columns. Note that the top and bottom squares on the left column are white. Any piece that covers the corner will cut off a $$2 \times 2$$ square, leaving a $$2 \times (n-2)$$ rectangle that again has white squares at the top left and bottom left. As you cover these corners you will eventually get to a $$1 \times 2$$ rectangle with a white square on the left. You can't cover that square.
• I believe I gave proofs of both. For even $n$, there are $\frac {n^2}2$ white squares and each L can only cover two, so you can't do better than $\frac {n^2}4$. I sketched an induction proof for odd $n$ in my answer. – Ross Millikan Feb 21 '19 at 6:25
• I don't understand the argument for odd $n$. For $k\ge1$ the white squares of a $2\times(2k+1)$ chessboard can be covered by $k+1$ nonoverlapping $L$-trominoes; for instance, the whole $2\times3$ chessboard can be covered by $2$ $L$-trominoes. So just what do you mean by "We only need to consider the two leftmost columns"? – bof Feb 21 '19 at 7:32
• It is possible to completely tile a $n\times n$ board with L-tiles when $n$ is a odd multiple of $3$ for which $n\ge 9$, so it is certainly possible to cover only the white tiles. (Proof: $5\times 6$ and $5\times 9$ rectangles can be tiled. Piece these together to make $5\times n$, then piece that together with many copies of $2\times n$ to make $n\times n$). – Mike Earnest Feb 21 '19 at 19:51