6
$\begingroup$

I'm trying to figure out the minimum number of rectangles required to cover an $n \times n$ grid, minus the diagonal. What this is means is the following: Suppose we have an $n \times n$ grid, with the diagonal missing. What is the minimum umber of rectangles I need that are contained within the grid such that the union of the rectangles covers the entire grid?

I think the answer should be $\log_2 n$. Attainment is easy, there are two $n^2/4$ squares (by which I mean two squares with area $n^2/4$), four $n^2/16$ squares, 8 $n^2/64$ squares, and so on. Summing this (and assuming $n = 2^m$) you get $$ \sum_{k=1}^{m = \log_2 n} 2^k \cdot n^2/4^k = \sum_{k=1}^m n^2 2^{-k} = n^2(1 - 1/n) = n^2 - n. $$ But I don't see a clean way to argue that this is the best you can do.

$\endgroup$
  • $\begingroup$ log base 2 of n ?? I tried it for n=8 and I get 14 (7 on each side of the diagonal). But log base 2 of n for n=8 gives 3 ??? $\endgroup$ – Vinzent Jan 27 at 4:00
  • $\begingroup$ "there are two n^2/4 squares (by which I mean two squares with area n^2/4), four n^2/16 squares, 8 n^2/64 squares, and so on" This seems to only hold for even values of n.. in all the cases I've tested so far it seems that 2*(n-1) is the best solution. $\endgroup$ – Vinzent Jan 27 at 4:12
  • $\begingroup$ Can those rectangles overlap $\endgroup$ – Maria Mazur Jan 27 at 7:39
4
$\begingroup$

Suppose that each square in the grid has coordinates $i,j$ representing its row and column. Take a look at squares: (1,2), (2,3), (3,4), ..., ($n$-1, $n$) above the diagonal and (2,1), (3,2), ..., ($n$, $n-1$) under the diagonal. There is no rectangle covering any two squares picked from this set at the same time.

So you need at least $2(n-1)$ rectangles just to cover all squares from this set. Fortunately, you can cover the whole board with the same number of rectangles (a set of horizontal rectangles of height 1 will do the job).

So the minimum number of rectangles is really $2(n-1)$.

$\endgroup$

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.