5

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$)

Community
  • 1
Firex Firexo
  • 295

1 Answers1

2

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} $$

Infiaria
  • 763
  • 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' :( – Firex Firexo Feb 24 '19 at 13:34
  • @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. – Infiaria Feb 24 '19 at 13:43
  • Nope, its correct, for any odd 'n' , the answer is same as (n+1)^2/4 :-) – Firex Firexo Feb 24 '19 at 13:45
  • I have 2 questions, the minimum 'n' and the configuration! Minimum 'n' part is cleared, now I am focussed on the configuration-part!:-) – Firex Firexo Feb 24 '19 at 13:47
  • @AnanyeAgarwal Were you given the answer beforehand? – Infiaria Feb 24 '19 at 13:50
  • nope, but I know the answer to few parts of the problem :-) – Firex Firexo Feb 24 '19 at 13:51
  • 1
    @AnanyeAgarwal Okay, fair enough! Maybe someone else can give a more rigorous proof. – Infiaria Feb 24 '19 at 13:55
  • hey, I've found it!! How to find the configuration, we just need to extend the 9X9 pattern,by, adding those 2 extra layers, again and again ! :-) Tysm :-) – Firex Firexo Feb 24 '19 at 13:57
  • I really liked the way you found such difficult intricate pattern(s), I am new to stack overflow, say, if I ask a question and I want your view(s)/comment(s) on it, how can I ask it to you via stack overflow. Is there some special option for that? Thanks again !:-) Tysm o – Firex Firexo Feb 24 '19 at 14:00
  • @ Infiaria Any ideas on this problem : - https://math.stackexchange.com/questions/3219387/how-do-i-solve-this-chessboard-problem – Firex Firexo May 09 '19 at 06:31