2
$\begingroup$

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$

Answer:-Impossible ,

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)

enter image description here

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I agree, but I want to be 100%sure, that there is no arrangement possible when 'n' is odd and I also want to be sure that (n^2/4) is the minimum number of tiles when its even, any proof for that as well? :-) $\endgroup$ – Firex Firexo Feb 21 at 6:12
  • $\begingroup$ 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. $\endgroup$ – Ross Millikan Feb 21 at 6:25
  • $\begingroup$ 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"? $\endgroup$ – bof Feb 21 at 7:32
  • $\begingroup$ @bof: I had assumed each L had to cover two white squares like in the picture, but I see that is not specified. I will correct it. $\endgroup$ – Ross Millikan Feb 21 at 14:49
  • $\begingroup$ @bof: I still believe it is impossible, but haven't found the proof $\endgroup$ – Ross Millikan Feb 21 at 15:02

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.