5
$\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\times 1$

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: $4\times 4$

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

enter image description here

Example: $7 \times 7$

If each tile can be represented by a number, and each uncovered piece of board can be represented by 'zero', then the answer for a $7 \times 7$ board is $16$:

$$ \begin{bmatrix} 16& 16& 15& 15& 14& 14& 13 \\ 16& 12& 15& 11& 14& 13& 13 \\ 12& 12& 11& 11& 10& 10& 9 \\ 8& 8& 7& 6& 10& 9& 9 \\ 8& 7& 7& 6& 6& 2& 2 \\ 5& 5& 4& 3& 3& 1& 2 \\ 5& 0& 4& 4& 3& 1& 1\\ \end{bmatrix} $$

Question

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

(Note: Answer exists for odd value of $n \geq 7$)

$\endgroup$
2
$\begingroup$

An image of the 7×7 solution as mentioned by OP:

7x7 Solution

And one possible way to extend this to a 9×9 solution (and further):

9×9 Solution

This isn't a complete proof, but since we can extend this pattern by moving the extra tiles diagonally and adding two more on either side — we have $(5,16)$, $(7,16+9)$, $(9,16+9+11)$, $(11,16+9+11+13)$... and you'll find that they are square numbers.

$$ k = \begin{cases} n^2/4 & n \text{ even} \\ (n+1)^2/4 & n \text{ odd} \wedge n\geq 7 \\ \text{not possible} & \text{otherwise} \end{cases} $$

$\endgroup$
  • $\begingroup$ First of all, thank you so much for your contribution. Can you tell me how should I proceed for any n cross n , where 'n' is odd? Like, its really clear what should I do when 'n' is even , but I am not able to find a general pattern for any odd 'n' :( $\endgroup$ – Firex Firexo Feb 24 at 13:34
  • $\begingroup$ @AnanyeAgarwal Don't mark this as correct yet! I don't know whether it's the minimum number yet, but just a way to find a solution. $\endgroup$ – Infiaria Feb 24 at 13:43
  • $\begingroup$ Nope, its correct, for any odd 'n' , the answer is same as (n+1)^2/4 :-) $\endgroup$ – Firex Firexo Feb 24 at 13:45
  • $\begingroup$ I have 2 questions, the minimum 'n' and the configuration! Minimum 'n' part is cleared, now I am focussed on the configuration-part!:-) $\endgroup$ – Firex Firexo Feb 24 at 13:47
  • 1
    $\begingroup$ @AnanyeAgarwal Okay, fair enough! Maybe someone else can give a more rigorous proof. $\endgroup$ – Infiaria Feb 24 at 13:55

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.